给出详细代码
时间: 2023-11-12 21:13:13 浏览: 30
好的,下面是Prim算法求最小生成树的详细代码。
首先,我们需要定义一个图的类,其中包括节点和边的信息:
```python
class Graph:
def __init__(self, vertices):
self.vertices = vertices
self.adj_matrix = [[float('inf')] * vertices for _ in range(vertices)]
self.visited = [False] * vertices
self.key = [float('inf')] * vertices
self.parent = [-1] * vertices
def add_edge(self, u, v, weight):
self.adj_matrix[u][v] = weight
self.adj_matrix[v][u] = weight
def min_key(self, key):
min_val = float('inf')
min_index = -1
for v in range(self.vertices):
if key[v] < min_val and not self.visited[v]:
min_val = key[v]
min_index = v
return min_index
def prim_mst(self):
self.key[0] = 0
self.parent[0] = -1
for _ in range(self.vertices):
u = self.min_key(self.key)
self.visited[u] = True
for v in range(self.vertices):
if self.adj_matrix[u][v] != float('inf') and not self.visited[v] and self.adj_matrix[u][v] < self.key[v]:
self.key[v] = self.adj_matrix[u][v]
self.parent[v] = u
```
然后,我们需要定义一个主函数来测试我们的代码:
```python
if __name__ == '__main__':
g = Graph(5)
g.add_edge(0, 1, 2)
g.add_edge(0, 3, 6)
g.add_edge(1, 2, 3)
g.add_edge(1, 3, 8)
g.add_edge(1, 4, 5)
g.add_edge(2, 4, 7)
g.add_edge(3, 4, 9)
g.prim_mst()
print("Edge \t Weight")
for i in range(1, g.vertices):
print(g.parent[i], "-", i, "\t", g.adj_matrix[i][g.parent[i]])
```
在主函数中,我们首先创建一个包含5个节点的图,并添加7条边。然后,我们调用prim_mst()函数来求出最小生成树,并打印出每条生成树边的权值。
这就是Prim算法求最小生成树的详细代码。希望对您有所帮助!