个人主页:丷从心
系列专栏:贪心算法
Prim
算法Prim
算法的正确性Prim
算法进行二重循环,需要
O
(
n
2
)
O(n^{2})
O(n2)时间Python
实现import sys
class Graph:
def __init__(self, vertices):
self.V = vertices
self.graph = [[0 for _ in range(vertices)] for _ in range(vertices)]
def printMST(self, parent):
print('边\t\t权')
for i in range(1, self.V):
print(f'{parent[i]} - {i}\t{self.graph[i][parent[i]]}')
def minKey(self, key, mstSet):
min_val = sys.maxsize
min_index = None
for v in range(self.V):
if key[v] < min_val and not mstSet[v]:
min_val = key[v]
min_index = v
return min_index
def primMST(self):
key = [sys.maxsize] * self.V
parent = [None] * self.V
mstSet = [False] * self.V
key[0] = 0
parent[0] = -1
for _ 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 not mstSet[v] and self.graph[u][v] < key[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()
边 权
0 - 1 2
1 - 2 3
0 - 3 6
1 - 4 5