一、最小生成树是什么？

想象你要给一个小区铺设水管，要求所有住户都能通水，但总管道长度最短。这就是最小生成树（Minimum Spanning Tree, MST）的典型场景——在连通图中选出总权重最小的边，连接所有节点且不形成环路。

二、Prim算法：从点出发的“生长式”策略

Prim算法像一棵慢慢长大的树。它从一个起点开始，每次选择当前已连接部分到未连接部分的最短边，逐步扩展。

技术栈：Python

def prim(graph):
    nodes = list(graph.keys())
    visited = {nodes[0]}  # 从第一个节点开始
    edges = []
    while len(visited) < len(nodes):
        min_edge = None
        # 遍历已访问节点的所有邻边
        for node in visited:
            for neighbor, weight in graph[node]:
                if neighbor not in visited:
                    if not min_edge or weight < min_edge[2]:
                        min_edge = (node, neighbor, weight)
        if min_edge:
            edges.append(min_edge)
            visited.add(min_edge[1])  # 标记新节点为已访问
    return edges

# 示例图（邻接表形式）
graph = {
    'A': [('B', 2), ('C', 3)],
    'B': [('A', 2), ('C', 1), ('D', 1)],
    'C': [('A', 3), ('B', 1), ('D', 4)],
    'D': [('B', 1), ('C', 4)]
}
print(prim(graph))  # 输出：[('A', 'B', 2), ('B', 'D', 1), ('B', 'C', 1)]

特点：

  • 适合稠密图（边多），因为每次只处理当前节点的邻边。
  • 时间复杂度为O(V²)，可用优先队列优化到O(E log V)。

三、Kruskal算法：按边排序的“拼图式”策略

Kruskal算法像玩拼图：将所有边按权重从小到大排序，逐个尝试加入，不形成环就保留。

技术栈：Python

def kruskal(graph):
    parent = {}
    def find(node):
        while parent[node] != node:
            node = parent[node]
        return node
    edges = []
    # 初始化父节点（用于检测环路）
    for node in graph:
        parent[node] = node
    # 提取所有边并排序
    all_edges = []
    for node in graph:
        for neighbor, weight in graph[node]:
            all_edges.append((weight, node, neighbor))
    all_edges.sort()  # 按权重升序
    # 遍历边
    for weight, u, v in all_edges:
        root_u, root_v = find(u), find(v)
        if root_u != root_v:  # 不形成环
            edges.append((u, v, weight))
            parent[root_v] = root_u  # 合并集合
    return edges

print(kruskal(graph))  # 输出：[('B', 'D', 1), ('B', 'C', 1), ('A', 'B', 2)]

特点：

  • 适合稀疏图（边少），排序后只需遍历一次。
  • 时间复杂度为O(E log E)，主要来自排序。

四、如何根据图的稀疏度选型？

  1. 稠密图（边数≈节点数²）：

    • 选Prim（尤其是邻接矩阵存储时）。
    • 例如：城市之间的交通网，几乎每两个城市都有直达路线。

  2. 稀疏图（边数≈节点数）：

    • 选Kruskal，排序后处理更高效。
    • 例如：社交网络中，每个人只连接少量好友。

注意事项：

  • Prim需要指定起点，但结果不受起点影响。
  • Kruskal需检测环路，通常用并查集（Union-Find）优化。

五、总结

  • Prim像“滚雪球”，适合边多的场景；Kruskal像“挑积木”，适合边少的场景。
  • 实际应用中，图的存储方式（邻接表或矩阵）也会影响选择。
  • 两种算法结果可能相同（总权重一致），但边顺序不同。