資料結構 圖論04 最小生成樹Kruskal克魯斯卡爾算法

克魯斯卡爾（Kruskal）算法

克魯斯卡爾（Kruskal）算法 是求最小生成樹的 了解最小生成樹

普利姆（Prime）算法是以 點 為基礎，挑選與 已有點 相連的最小邊。

克魯斯卡爾（Kruskal）算法是以 邊 為基礎，先将邊從小到大排列，從小到大的添加不構成「環路」的邊。

判斷「環路」使用的是 并查集 的資料結構 學習并查集

1.要點

• 核心：先将邊從小到大排列，從小到大的添加不構成「環路」的邊
• 判斷「環路」：使用 并查集 的資料結構 學習并查集
• 時間複雜度： O ( n l o g n ) O(n logn) O(nlogn) （這是由排序方式實作的）

2.圖解

求下面圖的最小生成樹

首先将邊從小到大排列 如下表所示。

邊	from	to	weight
edges[0]	B	C	2
edges[1]	A	C	3
edges[2]	A	B	3
edges[3]	B	D	4
edges[4]	C	D	6
edges[5]	A	D	7

選取最小的邊 BC，

1. 通過 并查集

   find()

   找到 root 根節點，判斷 B、C 不為同一顆子樹
2. 通過 并查集

   union()

   将 B、C 合并為一顆樹

選取第二小的邊 AC，

1. 通過 并查集

   find()

   找到 root 根節點，判斷 A、C 不為同一顆子樹
2. 通過 并查集

   union()

   将 A、

   {'B','C'}

   合并為一顆樹

選取第三小的邊 AB，

1. 通過 并查集

   find()

   找到 root 根節點，判斷 A、B 為同一顆子樹（被紅色線連接配接的點）
2. 不進行合并操作

選取第四小的邊 BD，

1. 通過 并查集

   find()

   找到 root 根節點，判斷 B、D 不為同一顆子樹
2. 通過 并查集

   union()

   将 D、

   {'A',B','C'}

   合并為一顆樹

我們得到了這個無向圖的 最小生成樹 （如上圖所示）

3.代碼

public ArrayList<Integer> kruskal(){
  //已經連接配接的點
  ArrayList<Integer> connectedVertices = new ArrayList<>();
  //擷取圖中的所有的邊
  List<Edge> edges = getAllEdges();
  //将所有的邊進行排序
  sortEdges(edges);
  //這裡使用并查集尋找出最小生成樹
  for (int i = 0; i < edges.size(); i++) {
    int fromVertexIndex = edges.get(i).from;
    int toVertexIndex = edges.get(i).to;
    boolean sameTree = find(fromVertexIndex) == find(toVertexIndex);
    //如果不是同一個樹
    if (sameTree == false){
      System.out.println(vertices[fromVertexIndex] + " --> " + vertices[toVertexIndex] + " weight:" +graph[fromVertexIndex][toVertexIndex]);
      //合并為同一個樹
      union(find(fromVertexIndex),find(toVertexIndex));
      //包含 to 點就添加 from 點
      if (connectedVertices.contains(toVertexIndex)) {
        connectedVertices.add(fromVertexIndex);
      }
      //包含 from 點 就添加 to 點
      else if (connectedVertices.contains(fromVertexIndex)){
        connectedVertices.add(toVertexIndex);
      }
      // 2 個都不包含就都添加
      else {
        connectedVertices.add(fromVertexIndex);
        connectedVertices.add(toVertexIndex);
      }
    }
    //如果全部點都已經連接配接就退出循環
    if (connectedVertices.size() == vertices.length){
      break;
    }
  }
  return connectedVertices;
}
           

getAllEdges()

、

sortEdges()

、

find()

、

union()

個方法上面就不贅述了，你可以

點選連接配接檢視完整Kruskal代碼

測試效果

B --> C weight:2
A --> C weight:3
B --> D weight:4