kruskal算法的主要代码
时间: 2024-10-10 20:17:29 浏览: 25
Kruskal算法是一种用于求解最小生成树的贪心算法。它的基本思想是每次选择当前未加入树中且边权值最小的一条边,并检查这条边是否会形成环路,如果没有,则添加到最小生成树中。下面是Kruskal算法的一个简单的Python实现:
```python
# 定义图的结构(无向图)
class Graph:
def __init__(self, vertices):
self.V = vertices
self.graph = []
# 边的表示形式:(起点, 终点, 权重)
def add_edge(self, u, v, w):
self.graph.append([u, v, w])
# Kruskal算法的核心部分
def kruskal_mst(graph):
result = [] # 最小生成树
i, e = 0, 0 # 当前已连接的边数
# 对所有边按权重排序
graph.sort(key=lambda item: item[2])
while i < len(graph) and e < V - 1:
u, v, w = graph[i]
if not is_cyclic(result, u, v): # 检查是否形成环路
result.append([u, v, w])
e += 1
i += 1
return result
# 判断是否存在环路(利用并查集数据结构)
def is_cyclic(parent, u, v):
if parent[u] == parent[v]:
return True
return False
# 示例用法
g = Graph(4) # 假设有4个顶点
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)
mst = kruskal_mst(g.graph)
print("最小生成树:", mst)
```
在这个示例中,`kruskal_mst`函数负责执行算法,而`is_cyclic`则通过并查集判断边的添加是否会形成环。
阅读全文