Python实现Prim和Kruskal算法：最小生成树构建详解

最小生成树问题在图论中是一个经典问题，目标是在连通网络中找到一棵边权和最小的树，该树包含所有节点但不形成环。本文将介绍两种常用的求解最小生成树的贪心算法：Prim算法和Kruskal算法。 **Prim算法**： Prim算法采用"贪心"策略，从图中的任意一个顶点（称为初始顶点）开始，逐步构建最小生成树。其核心步骤如下： 1. **初始化**：将初始顶点标记为已访问，将其余节点放入候选集。 2. **贪心选择**：在已访问顶点中寻找与候选集节点连接的边，选择具有最小权重的边，这条边的两个端点加入已访问集合，同时从候选集中移除这两个节点。 3. **重复**：继续执行第2步，直到候选集为空，此时已形成的边集合就是最小生成树。 **Prim算法的Python实现**： ```python def cmp(key1, key2): return key1 if key1 < key2 else key2 def prim(graph, init_node): visited = {init_node} candidate = set(graph.keys()) candidate.remove(init_node) # 去除初始节点 tree = [] while len(candidate) > 0: edge_dict = {} # 存储边及其权重 for node in visited: for connected_node, weighting in graph[node].items(): if connected_node in candidate: edge_dict[cmp(connected_node, node)] = weighting # 找到最小权重的边 edge, cost = sorted(edge_dict.items(), key=lambda kv: kv[1])[0] tree.append(edge) visited.add(edge[0]) visited.add(edge[1]) candidate.discard(edge[0]) candidate.discard(edge[1]) return tree ``` **Kruskal算法**： Kruskal算法则采用并查集数据结构，按照边的权重从小到大排序，依次加入边，只有当新加入的边连接的两个集合不相交时（即不存在环），才添加这条边。这个过程确保了构建出的树始终是最小生成树。 Kruskal算法的Python实现通常会使用并查集进行操作，但由于您提供的部分代码并未包含Kruskal算法的具体实现，此处略过。 总结： Prim算法和Kruskal算法都是解决最小生成树问题的有效方法，Prim算法是从一个起点出发逐步扩展，而Kruskal算法则是按边的权重顺序合并无环子集。两者各有优劣，Prim适合稠密图，效率较高；Kruskal适用于稀疏图，通过并查集操作简化了查找边是否形成环的操作。在实际应用中，根据具体情况选择合适的算法能更高效地解决问题。