数据结构 图论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