Notes►Data Structure

Data Structure - Graph & Network

Graph

圖形(Graph)由頂點(Vertics/Nodes)集合與邊(Edges)集合組成。G=(V,E)
透過頂點儲存資料，透過邊表示頂點間的連通關係，依照有無方向性區分成<有向圖>與(無向圖)。

完全圖: 圖形中的每一個頂點皆與其他頂點相互連接。
無向完全圖: |E| = N(N-1) / 2
有向完全圖: |E| = N(N-1)

有向圖 (Directed Graph)
無向圖 (Undirected Graph)

分支度 (Degree)

  • 有向圖

    • 出分支度 (Out Degree) - 從該頂點指出去的箭頭數
    • 入分支度 (In Degree) - 指向該頂點的箭頭數
    頂點 出分支度 入分支度
    1 1 1
    2 2 1
    3 1 2
    4 1 1

  • 無向圖

    頂點 分支度
    1 2
    2 3
    3 2
    4 3

表示法

相鄰矩陣 (Adjacent Matrix)

若兩頂點互相連通則標示為1，否則標示為0。

有向圖
  • 出分支度為列的總和
  • 入分支度為行的總和
無向圖
  • 此矩陣為一對稱矩陣，透過對稱矩陣中上或下三角形的部分即可表示無向圖。
  • 分支度為列/行的總和

相鄰串列 (Adjacent List)

在相鄰串列中的一節點(node)包含頂點欄(Vertex Field)與鏈結欄(Link Field)。　　
Vertex Field - 儲存非零元素的行值(頂點)
Link Field - 指向同一列右邊非零元素的節點

有向圖 有向圖的相鄰串列表示某一頂點向外連接其他頂點的關係
  • 出分支度為相鄰串列的長度
  • 入分支度為反向相鄰串列的長度
無向圖
  • 分支度為串列長度

圖形追蹤

從某一頂點開始，尋訪其他所有可到達的頂點

方法:

  1. 深度優先搜尋法 DFS
    堆疊
    Ⅰ 將起始頂點設定為拜訪過，並輸出該頂點
    Ⅱ 選擇一與該起始頂點相鄰且尚未拜訪過的頂點
    Ⅲ 將該選擇頂點當成起始頂點重複搜尋直到所有頂點皆被拜訪過為止

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    void dfs(int i) {
      int j;
      int step = 0;
      
      visit[i] = visited;
      printf("step%d: visit v%d\n", ++step, i);
      
      for(j=0; j<vertices; j++)
          if(adj_matrix[i][j]==1 && visit[j]!=visited)
              dfs(j);
    }

  2. 廣度優先搜尋法 BFS
    佇列
    Ⅰ 將起始頂點設定為拜訪過，並輸出該頂點
    Ⅱ 將所有與該起始頂點相鄰且尚未拜訪過的頂點加入queue的尾端
    Ⅲ 當queue不為空，取出queue最前端且尚未拜訪過的頂點
    Ⅳ 將該取出頂點當成起始頂點重複搜尋直到所有頂點皆被拜訪過為止

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
     void bfs(int i) {
      int j;
      int step = 0;
      
      visit[i] = visited;
      printf("step%d: visit v%d\n", ++step, i);
      
      for(j=0; j<vertices; j++) {
          if(adj_matrix[i][j]==1 && visit[j]!=1)
              input_queue(j); // 將頂點加入queue的尾端
      }
      while(rear != front) { // queue is not empty
          i = output_queue(); // 取出最前端的queue
          if(visit[i] != visited)
              bfs(i);
      }
    }

擴張樹 (Spanning Tree)

基本特性:

  1. 不允許迴路(Cycle)存在
  2. 必有一條路徑連接任兩頂點
  3. |E| = |V| - 1
    擴張樹的邊 = 頂點數 - 1

Network

網路(Netework)為在**邊(Edge)上加上成本/權重(weight)**的圖形。依照有無方向性區分成有向網路與無向網路。

花費最小成本擴張樹

花費最小成本擴張樹(Minimum Cost Spanning Tree)為擁有最小邊集合總成本的擴張樹，但兩頂點間的成本不一定是最小的。
建立方法:

  1. Prim’s Method - 循序加入頂點
  2. Kruskal’s Method - 循序加入邊

單一頂點到其他頂點之最短距離

【有向網路】從一起始頂點到其餘每一頂點的最短距離

定義distance[]為儲存起始頂點到其餘每一頂點最短距離的矩陣
定義selected[]為儲存頂點是否被選擇的矩陣

Ⅰ 初始化distance與selected，將起始頂點到其餘每一頂點的最短距離儲存於distance，並將起始頂點標記為select
Ⅱ 選出最小距離的頂點，將其最小距離儲存於distance並標記為select
Ⅲ 將distance中其他尚未被選擇頂點的距離與被選出頂點其最小距離+被選出頂點到該點的原始距離進行比較，若較小則更新

頂點0到其他頂點的最短距離
有向網路-從一起始頂點到其餘每一頂點的最短距離

任兩頂點間之最短距離

【有向網路】任兩頂點間之最短距離
有向網路-任兩頂點間之最短距離
將N個頂點依序編號(0, 1, …, N-1)
Ⅰ 定義A-1為任兩頂點間最原始的距離矩陣
Ⅱ 定義k(0 <= k <= N-1) 限制頂點i到頂點j的路徑不得通過大於編號k的頂點
Ⅲ k-1距離矩陣中的距離與頂點i通過頂點k到頂點j的距離(i-j-k)選擇較小者
當k=N-1，即可得任兩頂點間之最短距離矩陣

AOV (Activity on Vertex) Network

  • 應用於工作規劃
  • 一頂點(Vertex) = 一項工作(Activity)

拓樸排序 (Topology Sort)

AOV-拓樸排序
依序列出AOV Network中的所有頂點，並維持先後順序。
AOV-拓樸排序
Ⅰ 任選一個沒有predecessor(整行為0)的頂點
Ⅱ 將該頂點與其相關的邊刪除(刪除該頂點的欄與列)
Ⅲ 重複執行ⅠⅡ，直到所有頂點都已選擇

在程式中透過selected_ver矩陣標記被選擇的頂點，以刪除該頂點與其相關的邊，避免被重複選擇。