当前位置： 面试刷题>> 最小生成树 (经典算法题500道)
### 题目描述补充
题目：**最小生成树问题**
给定一个无向连通图 $G = (V, E)$，其中 $V$ 是顶点的集合，$E$ 是边的集合，每条边 $e \in E$ 都有一个权重 $w(e)$。最小生成树（Minimum Spanning Tree, MST）是图 $G$ 的一个子图，它包含图 $G$ 的所有顶点 $V$，并且是一个树（即无环且连通），同时它的边的权重之和是所有这样的子图中最小的。
**要求**：
1. 设计并实现一个算法来找到给定图的最小生成树。
2. 使用PHP、Python、JavaScript中的至少一种语言编写实现代码。
### 示例代码
#### Python 示例（使用Prim算法）
```python
import heapq
class Graph:
def __init__(self, vertices):
self.V = vertices
self.graph = [[] for _ in range(vertices)]
def add_edge(self, u, v, w):
self.graph[u].append((v, w))
# 由于是无向图，所以还需要添加反向边
self.graph[v].append((u, w))
def prim_mst(self):
# 用于存储MST中的边
mst = []
# 用于跟踪已包括在MST中的顶点
in_mst = [False] * self.V
# 选择第一个顶点作为起始点
key = [float('Inf')] * self.V
parent = [-1] * self.V
key[0] = 0
# 使用优先队列（通过heapq实现）来按权重提取边
priority_queue = [(0, 0)]
while priority_queue:
# 提取最小权重的边
u = heapq.heappop(priority_queue)[1]
# 顶点u已经在MST中
in_mst[u] = True
# 遍历所有与u相邻的顶点
for v, weight in self.graph[u]:
if not in_mst[v] and weight < key[v]:
# 更新权重和父节点
key[v] = weight
parent[v] = u
heapq.heappush(priority_queue, (weight, v))
# 如果这条边是MST的一部分，则添加到mst列表中
mst.append((u, v, weight))
return mst
# 示例
g = Graph(5)
g.add_edge(0, 1, 10)
g.add_edge(0, 2, 6)
g.add_edge(0, 3, 5)
g.add_edge(1, 3, 15)
g.add_edge(2, 3, 4)
g.add_edge(3, 4, 20)
g.add_edge(2, 4, 8)
mst = g.prim_mst()
print("Edges of MST are:")
for u, v, w in mst:
print(f"{u} -- {v} == {w}")
# 码小课网站中有更多关于算法和数据结构的相关内容分享给大家学习。
```
#### 注意
- 上述代码实现了Prim算法来找到图的最小生成树。
- 使用了Python的`heapq`模块来高效地处理边的权重。
- `Graph`类用于构建图，并通过`add_edge`方法添加边。
- `prim_mst`方法实现了Prim算法，并返回MST的边列表。
- 输出MST的边时，同时显示了边的权重。
希望这个解答对你有帮助，并欢迎访问码小课网站获取更多学习资源。