最小生成树MST 之 Kruskal及其实现

关于最小生成树以及Prim算法参考上一篇:最小生成树MST 之 Prim及其实现

Kruskal算法

Kruskal算法实际上是 贪心+并查集,贪心用来查找权值最小的边,并查集来检测顶点的连通性(关于并查集不再详述)。

不同于Prim算法,Kruskal不是面向顶点来生成MST的,Kruskal只考察边集,只看当前最小权值的边,所以需要并查集来检测顶点连通的状态(Prim通过已连通的顶点来选择权值最小的边,而Kruskal先去掉所有的点,在总边集中找最小的边)。

Kruskal算法的步骤:

  1. 将边集内的边按权值大小升序排序。
  2. 依次考察每条边,如果边的两顶点不同源(至少有一点未被访问),则将此边纳入生成树。
  3. 执行步骤2,直到每一个点都被访问。

从步骤中可以看出,Kruskal的性能取决于排序算法,需要选择合适的排序算法。

Kruskal的实现(Python)

  • 随机生成5×5-9×9的图(邻接矩阵)
  • 排序使用python自带的sorted()方法
  • 输出访问顺序和总开销
import random, time
father = []
MAX_DISTANCE = 100  # 边的最大权值


def create_map():  # 生成图(邻接矩阵)
    map = []
    size = random.randint(5, 9)
    print("图大小:", size)
    
    for i in range(size):
        row = []
        for j in range(size):
            row.append(random.randint(1, MAX_DISTANCE))
        map.append(row)
    
    print("生成图:")
    for i in range(size):
        print(map[i])
    
    return map


def get_edges(map):
    edges = []
    for i in range(len(map)):
        for j in range(len(map)):
            edges.append([i, j, map[i][j]])
    return len(map), len(edges), edges


def find(n):  # 查找顶点的父亲顶点
    if father[n] == n:
        return n
    father[n] = find(father[n])
    return father[n]


def union(map_size, edge_size, edges):
    global father
    father = [i for i in range(map_size)]  # 并查集,初始情况下顶点的源点为自身
    tol_distance = 0  # 总开销
    visit_order = []  # 记录访问顺序
    
    for i in range(edge_size):
        node1 = find(edges[i][0])  # 边的一个顶点的源点
        node2 = find(edges[i][1])  # 边的令一个顶点的源点
        if node1 != node2:  # 不同源
            visit_order.append(edges[i])
            tol_distance += edges[i][2]
            father[node2] = node1  # 合并,将两顶点的源点合并为一个
            
    return visit_order, tol_distance
    

def kruskal(map_size, edge_size, edges):
    edges = sorted(edges, key=lambda x: x[2])  # 对边进行权值的升序排序
    return union(map_size, edge_size, edges)


def main():
    map_size, edge_size, edges = get_edges(create_map())
    visit_order, tol_distance = kruskal(map_size, edge_size, edges)

    print("访问顺序:[顶点, 顶点, 权值]")
    for each in visit_order:
        print(each)

    print("总开销:", tol_distance)

    
if __name__ == "__main__":
    main()

输出: