最小生成树算法（Prim Kruskal）

**最小生成树算法（Prim Kruskal）**

在计算机科学中，生成树是连接图中所有顶点的边集，使得每个顶点都至少有一个出度为1 的边。最小生成树是指生成树中权值最小的边集。在本文中，我们将介绍 Prim 和 Kruskal 算法，这两种算法都是用于求解最小生成树的问题。

**Prim 算法**

Prim 算法是一种贪婪算法，它通过逐步添加最小权值的边来构建最小生成树。具体来说，Prim 算法从图中任意一个顶点开始，然后不断地选择连接该顶点的最小权值的边，并将其添加到生成树中。

**Kruskal 算法**

Kruskal 算法是一种也贪婪算法，它通过逐步添加最小权值的边来构建最小生成树。不同于 Prim 算法，Kruskal 算法从所有可能的边开始，然后不断地选择连接两个顶点且不形成环的最小权值的边，并将其添加到生成树中。

**算法步骤**

1. **初始化**: 将图中的所有顶点都放入一个集合中，表示它们尚未被包含在生成树中。
2. **选择最小边**: 从图中选择连接两个顶点且不形成环的最小权值的边，并将其添加到生成树中。
3. **更新集合**: 将所选边的两个顶点都从原来的集合中取出，然后将它们放入一个新的集合中，表示它们已经被包含在生成树中。
4. **重复步骤2 和3**: 直到所有顶点都被包含在生成树中。

**代码示例**

### Prim 算法

import heapqdef prim(graph):
 # 初始化 start_vertex = list(graph.keys())[0]
 visited = set()
 visited.add(start_vertex)
 mst = []
 #选择最小边 edges = [(weight, vertex1, vertex2) for vertex1 in graph for vertex2 in graph[vertex1] if vertex1 != vertex2 and (vertex1, vertex2) not in visited]
 heapq.heapify(edges)
 while edges:
 weight, vertex1, vertex2 = heapq.heappop(edges)
 if vertex2 not in visited:
 mst.append((vertex1, vertex2))
 visited.add(vertex2)
 return mst# 示例图graph = {
 'A': {'B':2, 'C':3},
 'B': {'A':2, 'D':4},
 'C': {'A':3, 'F':1},
 'D': {'B':4, 'E':5},
 'E': {'D':5, 'F':6},
 'F': {'C':1, 'E':6}
}

print(prim(graph))

class UnionFind:
 def __init__(self):
 self.parent = {}
 def find(self, x):
 if x not in self.parent:
 self.parent[x] = x return x if self.parent[x] != x:
 self.parent[x] = self.find(self.parent[x])
 return self.parent[x]
 def union(self, x, y):
 root_x = self.find(x)
 root_y = self.find(y)
 if root_x != root_y:
 self.parent[root_x] = root_ydef kruskal(graph):
 # 初始化 mst = []
 edges = [(weight, vertex1, vertex2) for vertex1 in graph for vertex2 in graph[vertex1]]
 heapq.heapify(edges)
 uf = UnionFind()
 while edges:
 weight, vertex1, vertex2 = heapq.heappop(edges)
 if uf.find(vertex1) != uf.find(vertex2):
 mst.append((vertex1, vertex2))
 uf.union(vertex1, vertex2)
 return mst# 示例图graph = {
 'A': {'B':2, 'C':3},
 'B': {'A':2, 'D':4},
 'C': {'A':3, 'F':1},
 'D': {'B':4, 'E':5},
 'E': {'D':5, 'F':6},
 'F': {'C':1, 'E':6}
}

print(kruskal(graph))