数据结构与算法 —— 最小生成树Prim算法和Kruskal算法详细图解以及python实现

1. 介绍

2. Prim算法（普里姆算法）

2.1 Prim算法历史

2.2 Prim算法的基本思路

2.3 Prim算法图解

2.4 Prim算法（python）实现

3. Kruskal算法（克鲁斯卡尔算法）

3.1 Kruskal算法的基本思路

3.2 Kruskal算法图解

3.3 Kruskal算法（python）实现

4. 最小生成树和最短路径的区别

5. 结尾

前言

上一章我们整理了最短路径中的 Dijkstra算法。
现在我们整理最小生成树中Prim算法（普里姆算法）和Kruskal算法（克鲁斯卡尔算法）。

1. 介绍

最小生成树也是图论中常见问题，其指的是在一个图中找到一个连通子图，使得所有节点都能够互相到达，且总权值最小。

最小生成树的例子在生活中也很常见，比如城市的公交线路系统需要规划如何走完一趟路径和是最短的，或者快递公司如何给不同住址的客户送货才能是最短的路径。

2. Prim算法（普里姆算法）

2.1 Prim算法历史

普里姆算法最初由捷克数学家沃伊捷赫·亚尔尼克于1930年发现，后来在1957年由美国计算机科学家罗伯特·普里姆独立发现，1959年艾兹格·迪科斯彻也再次发现了该算法。因此，普里姆算法在某些情况下也被称为DJP算法、亚尔尼克算法或普里姆-亚尔尼克算法。

2.2 Prim算法的基本思路

首先选择一个起始节点，以这个节点将图分成两个集合。一个已选集合，一个未选集合。把起始节点加入已选集合。

然后从已选节点集合出发，不断选择权值最小的边连接到未选节点集合中的节点，并将其加入已选节点集合。

不断循环此过程，直到所有节点都被加入到已选节点集合中，形成最小生成树。

这就是Prim算法的基本思路。

简单来说，就是从一个点开始，不断寻找距离最短的边，将其加入最小生成树中，并将与之相连的未访问点所构成的边加入集合中，直到所有节点都被访问过为止。

2.3 Prim算法图解

在下面这个图的基础上，我们可以一步一步来分析Prim 算法的过程。

我们的目的是用此算法判断出构成最小生成树的所有边。

 接下来一样的操作，就不在图中标注文字解释了。

算法完成，我们得到了构成最小生成树的所有边。

2.4 Prim算法（python）实现

def prim_algorithm(graph):
    num_vertices = len(graph)
    
    # 初始化集合
    selected = set()
    selected.add(list(graph.keys())[0])  # 从第一个顶点开始
    unselected = set(graph.keys()) - selected
    
    # 初始化最小生成树结果
    minimum_spanning_tree = []

    while unselected:
        min_weight = float('inf')
        start_vertex = None
        end_vertex = None

        # 遍历已选集合中的每个顶点
        for vertex in selected:
            # 遍历未选集合中的每个顶点
            for neighbor, weight in graph[vertex].items():
                if neighbor in unselected:
                    # 找到权值最小的边
                    if min_weight > weight:
                        min_weight = weight
                        start_vertex = vertex
                        end_vertex = neighbor

        # 将找到的最小权值边添加到最小生成树结果中
        minimum_spanning_tree.append((start_vertex, end_vertex, min_weight))
        selected.add(end_vertex)
        unselected.remove(end_vertex)

    return minimum_spanning_tree

graph = {
    'A': {'B': 2, 'C': 9},
    'B': {'A': 2, 'D': 4, 'E': 8},
    'C': {'A': 9, 'E': 10, 'F': 3},
    'D': {'B': 4, 'E': 1, 'G': 5},
    'E': {'B': 8, 'C': 10, 'D': 1, 'F': 11, 'G': 6, 'H': 12},
    'F': {'C': 3, 'E': 11, 'H': 17},
    'G': {'D': 5, 'E': 6},
    'H': {'E': 12, 'F': 17},
}

result = prim_algorithm(graph)
print(result)

实现了一个上面举例子用的图，运行此程序会打印出：

[('A', 'B', 2), ('B', 'D', 4), ('D', 'E', 1), ('D', 'G', 5), ('A', 'C', 9), ('C', 'F', 3), ('E', 'H', 12)]

前两个字母表示最小生成树中的一条边，后面的数字代表这条边的权值。可以与上面的图解结合起来看。 

3. Kruskal算法（克鲁斯卡尔算法）

3.1 Kruskal算法的基本思路

该算法是先取出所有的边，按其权值从小到大的顺序排列，然后不断取出权值最小的边放入图中，一共取n-1条边（n为节点数）。但是每次放入一条边都要判断是否形成了环。如果没有形成环，则将该边纳入最小生成树中。如果形成了环，则舍弃这条边，继续取下一条边。

3.2 Kruskal算法图解

首先取出图中所有的边，并且按其权值从小到大排序。

此时，边的数量 = n-1，算法结束。同样也得到了一个最小生成树。 

3.3 Kruskal算法（python）实现

def find(parent, vertex):
    if parent[vertex] == vertex:
        return vertex
    return find(parent, parent[vertex])

def union(parent, rank, vertex1, vertex2):
    root1 = find(parent, vertex1)
    root2 = find(parent, vertex2)

    if root1 != root2:
        if rank[root1] > rank[root2]:
            parent[root2] = root1
        else:
            parent[root1] = root2
            if rank[root1] == rank[root2]:
                rank[root2] += 1

def kruskal_algorithm(graph):
    # 初始化结果
    minimum_spanning_tree = []

    # 初始化并查集
    parent = {vertex: vertex for vertex in graph.keys()}
    rank = {vertex: 0 for vertex in graph.keys()}

    # 获取所有的边
    edges = []
    for vertex, neighbors in graph.items():
        for neighbor, weight in neighbors.items():
            edges.append((vertex, neighbor, weight))

    # 按权值排序边
    edges.sort(key=lambda edge: edge[2])

    # 不断取出权值最小的边并判断是否形成环
    for edge in edges:
        vertex1, vertex2, weight = edge
        if find(parent, vertex1) != find(parent, vertex2):
            union(parent, rank, vertex1, vertex2)
            minimum_spanning_tree.append(edge)

        if len(minimum_spanning_tree) == len(graph) - 1:
            break

    return minimum_spanning_tree

graph = {
    'A': {'B': 2, 'C': 9},
    'B': {'A': 2, 'D': 4, 'E': 8},
    'C': {'A': 9, 'E': 10, 'F': 3},
    'D': {'B': 4, 'E': 1, 'G': 5},
    'E': {'B': 8, 'C': 10, 'D': 1, 'F': 11, 'G': 6, 'H': 12},
    'F': {'C': 3, 'E': 11, 'H': 17},
    'G': {'D': 5, 'E': 6},
    'H': {'E': 12, 'F': 17},
}

result = kruskal_algorithm(graph)
print(result)

find(parent, vertex)函数：这个函数的作用是找到给定顶点所属集合的代表元素。

union(parent, rank, vertex1, vertex2)函数：这个函数的作用是将两个不同集合合并成一个集合。 

运行上面程序之后会打印：

[('D', 'E', 1), ('A', 'B', 2), ('C', 'F', 3), ('B', 'D', 4), ('D', 'G', 5), ('A', 'C', 9), ('E', 'H', 12)]

可以发现与我们图解的答案包括Prim算法的答案是一致的。

4. 最小生成树和最短路径的区别

最小生成树和最短路径问题在目标、应用场景和解决方法上都有所不同。最小生成树关注的是连接所有顶点的最小总权值，而最短路径关注的是在带权图中找到顶点之间的最短路径。

结合图解来看会更加清晰（选择节点D为起始节点）：

5. 结尾

到这里为止，我们已经整理了

图的基本结构，

深度优先搜索，广度优先搜素，

最短路径Dijkstra算法，

最小生成树Prim算法和Kruskal算法。

基本上图的内容已经整理的差不多了。下面会整理贪心算法（greedy algorithm）的内容。

如果有地方讲的不对或者大家有什么疑问，欢迎留言或者私信我！