演示示例

graph

step 1：
最小权值边为顶点 7、8 形成的边

step 2：
最小权值边为顶点 3、9 形成的边

step 3：
最小权值边为顶点 6、7 形成的边

step 4：
最小权值边为顶点 3、6 形成的边

step 5：
最小权值边为顶点 1、2 形成的边

step 6：
最小权值边为顶点 3、4 形成的边

step 7：
最小权值边为顶点 1、8 形成的边

step 8：
最小权值边为顶点 4、5 形成的边

最小生成树的权值之和为 37

算法示例

这里使用邻接表作为图的存储结构

1. kruskal 算法示例

def kruskal(graph):
    edges, vertices = getEdgesFromAdjacencyList(graph), [i for i in range(graph.number)]
    sort(edges, 0, len(edges) - 1)
    weightSum, edgeNumber = 0, 0
    while edgeNumber < graph.number - 1:
        edge = edges.pop()
        beginOrigin, endOrigin = origin(vertices, edge.begin - 1), origin(vertices, edge.end - 1)        if (beginOrigin != endOrigin): # whether the two vertices belong to same graph
            vertices[beginOrigin] = endOrigin  # identify the two vertices in the same sub graph
            weightSum, edgeNumber = weightSum + edge.weight, edgeNumber + 1  # calculate the total weight

这里使用 getEdgesFromAdjacencyList 函数完成邻接表到边集合的转换，使用快排 sort 完成对边集合的排序，使用 origin 函数返回每个子图的根。

kruskal 算法设定最初每个顶点都是一个子图，每个子图都有一个根，或者称之为出发点，每个加入的顶点都保留一个指向上一个顶点的引用，并最终追溯到该子图的根顶点，所以可以通过判断两个顶点指向的根顶点是否相同，来判断两顶点是否属于同一个子图。

1. 邻接表转边集合

def getEdgesFromAdjacencyList(graph):
    edges = []    for i in range(graph.number):
        node = graph.list[i]        while node:
            edge, node = Edge(i + 1, node.index, node.weight), node.next
            edges.append(edge)    return edges

因为使用邻接表向边进行转化，且后续只对边集合进行处理，所以在测试时候，无向图中的每条边，只需要记录一次即可，不需要对于边的两个顶点，分别记录一次。

1. 判断两个顶点是否属于同一个子图，避免添加边后形成环

def origin(vertices, index):
    while vertices[index] != index:
        index = vertices[index]    return index

该函数返回顶点 index 所属子图的根顶点，其中 vertices[index] 位置上存储的是顶点 index 的上一个顶点，每个子图中，根顶点的上一个顶点为自身。

性能分析

kruskal 算法中使用 getEdgesFromAdjacencyList 函数完成邻接表向边集合的转换，函数内部存在两层循环，访问邻接表中每个顶点的相邻顶点，复杂度为 。使用快排对边集合进行排序，时间复杂度为 ，因为 ，所以快排时间复杂度可以表述为 。kruskal 算法中 while 循环取最小权值边，并对边的两个顶点执行 origin 函数判断是否属于同一个子图，时间复杂度为 。所以 kruskal 算法的时间复杂度为 。

prim 算法

kruskal 算法的过程为不断对子图进行合并，直到形成最终的最小生成树。prim 算法的过程则是只存在一个子图，不断选择顶点加入到该子图中，即通过对子图进行扩张，直到形成最终的最小生成树。

扩张过程中选择的顶点，是距离子图最近的顶点，即与子图中顶点形成的边是权值最小的边。

算法过程

1. 按照距离子图的远近，对顶点集合进行排序

2. 选择最近的顶点加入到子图中，并更新相邻顶点对子图的距离

3. 重复执行步骤 2，直到顶点集合为空

演示示例

graph

这里不妨以顶点 5 作为子图中的第一个顶点

step 1：
距离子图的最近顶点为 4

作者：zhipingChen
链接：https://www.jianshu.com/p/cf21443b3838