Please enable JavaScript.

Coggle requires JavaScript to display documents.

CH6 (Connected Graph(連通圖) (Connected Component (最大的聯通子圖,…

- - - - O(n^2)
      - 說明
        
        選擇下一個頂點 : O(n)
        
        更新距離 : O(n)
        
        Using Fibonacci heap: O(nlogn+e)
- - - - 一個n*n的矩陣
      - A(i,j) = 1 iff (i,j)有通
    - - 對角線必為零(自己跟自己)
      - 對稱性
        
        無向圖 => O
        
        有向圖 => X
    - - 無向圖
        
        (n-1)n/2
        
        說明 : 只需儲存上三角或下三角，並排除對角線
    - - 查詢頂點degree : O(n)
  - - - 無向圖 : 2e
      - 有向圖 : e
- - - - adjacency matrix : O(n^2)
        
        說明
        
        查找每個點有哪些鄰居 : O(n)
        
        總共有n個點 = > O(n*n)
      - adjacency lists : O(e)
    - - 邊多 => 用matrix
      - 點多 => 用list
- - - - Kruskal’s Method
        
        步驟
        
        (1)將每個點各自獨立成一顆樹，形成森林
        
        (2)取出最小成本的邊，放到圖中
        
        (3)若不形成cycle，保留; 若形成cycle，捨棄。
        
        (4)成功取出n-1條邊，串聯起每個頂點且，不含cycle =>完成
        
        說明
        
        如何判斷是否形成cycle : 串連的兩頂點不再同一個component當中，就不會形成cycle
      - Prim’s method (比kruskal快)
        
        步驟
        
        (1)另V = {1,2,3,...,n}, U = {1} //start vertex
        
        (2)挑出最小成本的邊(u,v), 且u屬於U，且v屬於V-U
        
        (3)將(u,v)加到Set當中，直到U=V或E沒有邊為止
        
        (4)若邊數 == v-1 代表有展開樹; 否則，無。
    - - Kruskal’s
        
        方法
        
        將每個點視為獨立root，將最小成本邊加入，若形成cycle，捨棄。否則，保留。
        
        時間複雜度
        
        使用union-find trees : O(n + e log e)
        
        說明 :
        
        初始 : O(n)
        
        移除、取出對小成本邊 : O(e)*O(log e) (邊數、樹高)
      - Prim’s
        
        方法
        
        每次都將最短邊加入(樹中的點可連到的)
        
        時間複雜度
        
        使用Dijkstra’s最短路徑演算法 : O(n^2)
        
        使用Fibonacci heap : O(e + n log n)
      - Sollin’s
        
        步驟
        
        (1)將各頂點視為獨立的tree之root
        
        (2)從各別的樹，選出最小成本的樹邊
        
        (3)刪除重複挑出來的tree edge
        
        (4)重複1~3，直到只剩一顆樹或E為空為止