iT邦幫忙

0

【資料結構】圖的表示方式與基本運作

圖的基本定義

圖的表示方式與基本運作

表示方式

  • 相鄰矩陣

    若G(V,E)是含n個頂點的圖,表示圖G的矩陣為mat[n][n]

      存在邊的矩陣為mat[i][j]=1
      不存在邊的矩陣為mat[i][j]=0
    
  • 無向圖

      無向圖的相鄰矩陣為對稱
    
  • 有向圖

      有向圖的相鄰矩陣為非對稱
    
  • 相鄰串鏈

  • 無向圖

  • 有向圖

    一維的表示法

    • 因上述的串鏈表示法空間需求較大,因此可改為一維的方式將圖中所有頂點將圖中所有頂點集合。

    • 陣列的空間表示方式為mat[n+2e+1],n為頂點數,2e為頂點數*分支度。

        以G4為例,索引0~8為陣列的初始位置,9~22為儲存值
      

實作連結:矩陣串鏈表示法

  • 相鄰多重串鏈


    先略

基本運作

追蹤

  • 深度追蹤

    演算法
    #define FALSE 0
    #define TRUE 1
    short int visited[MAX_VERTICES];
    void dfs(int v){
      node_pointer w;
      visited[v]= TRUE;
      printf(“%5d”, v);
      for (w=graph[v]; w; w=w->link)
        if (!visited[w->vertex]){
          dfs(w->vertex);
        }
    }
    
    時間複雜度:
    • 相鄰串鏈:O(e)
    • 相鄰矩陣:O(n^2)
  • 廣度追蹤

    演算法
      typedef struct queue *queue_pointer;
      typedef struct queue {
                      int vertex;
                      queue_pointer link;
      };
      queue_pointer front, rear;
      void addq(int);     // int 為頂點編號
      int deleteq();
      void bfs(int v){
          node_pointer w;
          front = rear = NULL;
          printf(“%5d”, v);
          visited[v] = TRUE;
          addq(v);
          while (front) {
            v= deleteq();
            for (w=graph[v]; w; w=w->link)
                if (!visited[w->vertex]) {
                    printf(“%5d”, w->vertex);
                    addq(w->vertex);
                    visited[w->vertex] = TRUE;
                } 
            }   
      } 
    
    時間複雜度:
    • 相鄰串鏈:O(e)
    • 相鄰矩陣:O(n^2)

實作連結:DFS與BFS追蹤

擴張樹(Spanning Trees)

定義:

  • 1.包含一個圖所有的頂點和部分的邊形成的樹,也稱生成樹
  • 2.若圖形式相連的,從任一節點追蹤都會拜訪到所有的頂點
  • 3.當加入一個非樹之邊時,此擴張樹會形成迴路
  • 4.深度優先擴張樹(Depth First Spanning tree):利用DFS產生的擴張樹
  • 5.廣度優先擴張樹(Breadth First Spanning tree):利用BFS產生的擴張樹
  • 6.一個具有n個頂點的連接圖最少有n-1個邊;具有n-1個邊的連接圖即為樹

最小成本擴張樹(Minimum Cost Spanning Trees)

一個所有邊具有成本權重的無向圖,其最小成本和為最小成本擴張樹

以下為利用貪婪法(greedy method)生成最小成本擴張樹的演算法

  • Kruskal’s 演算法
    一次以最小成本加一個邊,當天家的邊產生迴圈則跳過



    演算法

    T= {};
    while (T 包含少於 n-1 個邊且 E 不是空集合) {
          從E選擇一個最小成本之邊 (v, w) ;
          從E刪除 (v, w)邊;
          若邊(v, w) 不會在T中產生迴圈,則
              將 (v, w)邊加入T中
          否則
              放棄(v, w)邊;
    }
    若T包含少於 n-1個邊,則
          印出”無擴張樹”之訊息;
    
  • Prim’s 演算法
    每次加一個周圍最小成本的邊加入樹中,每一次添加後還是一棵樹,直到這棵樹包含n-1個邊為止

    演算法:

    T={};
    TV={0};  /* 從頂點0開始 */
    while (T包含少於 n-1個邊) {
        令 (u, v) 為最小成本之邊,使得 u ? TV   
                        且 v ? TV
        若無此種邊則停止;否則
        將頂點 v 加入 TV;
        將邊 (u, v) 加入T;
    }
    若T包含少於 n-1個邊,則
          印出”無擴張樹”之訊息;
    
    
  • Sollin’s 演算法
    待補


最短路徑

找出單一來源到所有頂點的最短路徑

圖表法

Dijkstra’s 演算法
步驟:

  • 插入第一個頂點至樹中
    從樹中每一頂點檢查至尚未包括在樹中的每一鄰點總長度,選擇具最小長度邊插入樹中
  • 重複上述步驟,直到所有頂點均包含在樹中為止
  • 此法不得應用於邊具有負權重值之圖形

所有序對時間複雜度:
最短路徑法O(n^2)*執行n次=O(n^3)

AOV網路

  • 有向圖中的工作次序關係

  • 前輩一定出現在繼承者前面

    圖形中的拓樸次序(Topological order)

AOE網路

  • 最早時間(e) :一個活動可以發生的最短時間

  • 最晚時間(l) :一個活動可以發生的最遲時間

  • 臨界程度 (時間伸縮程度):l(i) - e(i) 的差值

    e(i)=l(i)的活動稱為臨界活動
    


尚未有邦友留言

立即登入留言