普利姆算法及代码,阅读相应代码并给出相应的解释
时间: 2023-07-10 15:21:36 浏览: 95
普利姆算法是一种用于求解最小生成树的贪心算法。它从任意一个点开始,不断选择当前节点和未加入生成树的节点之间权值最小的边,并将该节点加入生成树中,最终形成一棵生成树。以下是一个基于邻接矩阵的普利姆算法的实现代码:
```python
import sys
class Graph:
def __init__(self, vertices):
self.V = vertices
self.graph = [[0 for column in range(vertices)]
for row in range(vertices)]
# 找到未加入最小生成树的权值最小的边
def minKey(self, key, mstSet):
min = sys.maxsize
for v in range(self.V):
if key[v] < min and mstSet[v] == False:
min = key[v]
min_index = v
return min_index
# 输出最小生成树
def printMST(self, parent):
print("Edge \tWeight")
for i in range(1, self.V):
print(parent[i], "-", i, "\t", self.graph[i][parent[i]])
# 普利姆算法
def primMST(self):
# 用于存放生成树的最小权值
key = [sys.maxsize] * self.V
# 用于存放生成树中对应节点的父节点
parent = [None] * self.V
# 用于记录节点是否已经加入生成树
mstSet = [False] * self.V
# 从第一个节点开始生成
key[0] = 0
parent[0] = -1
for cout in range(self.V):
# 找到未加入最小生成树的权值最小的边
u = self.minKey(key, mstSet)
# 将该节点加入生成树中
mstSet[u] = True
# 更新与该节点相邻的节点的权值
for v in range(self.V):
if self.graph[u][v] > 0 and mstSet[v] == False and key[v] > self.graph[u][v]:
key[v] = self.graph[u][v]
parent[v] = u
# 输出最小生成树
self.printMST(parent)
g = Graph(5)
g.graph = [[0, 2, 0, 6, 0],
[2, 0, 3, 8, 5],
[0, 3, 0, 0, 7],
[6, 8, 0, 0, 9],
[0, 5, 7, 9, 0]]
g.primMST()
```
该代码中,我们首先定义了一个Graph类,其中包含了邻接矩阵表示法的图结构和普利姆算法的实现。在普利姆算法中,我们首先创建了三个数组,分别存放生成树的最小权值、对应节点的父节点和节点是否已经加入生成树。然后,我们从第一个节点开始,不断选择当前节点和未加入生成树的节点之间权值最小的边,并将该节点加入生成树中,最终形成一棵生成树。在选择边的过程中,我们使用了minKey方法来找到未加入最小生成树的权值最小的边,并使用printMST方法输出最终的最小生成树。
阅读全文