圖的基本定義

圖的表示方式與基本運作

表示方式

• 相鄰矩陣

  若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)的活動稱為臨界活動