import sys
class Graph:
def __init__(self, vertices):
self.V = vertices
self.graph = [[0 for _ in range(vertices)] for _ in
range(vertices)]
def min_key(self, key, mst_set):
min_val = sys.maxsize
min_index = -1
for v in range(self.V):
if key[v] < min_val and mst_set[v] == False:
min_val = key[v]
min_index = v
return min_index
def prim_mst(self):
key = [sys.maxsize] * self.V
parent = [None] * self.V
key[0] = 0
mst_set = [False] * self.V
parent[0] = -1
for _ in range(self.V):
u = self.min_key(key, mst_set)
mst_set[u] = True
for v in range(self.V):
if self.graph[u][v] > 0 and mst_set[v] == False and key[v]
> self.graph[u][v]:
key[v] = self.graph[u][v]
parent[v] = u
self.print_mst(parent)
def print_mst(self, parent):
print("Edge Weight")
for i in range(1, self.V):
print(parent[i], "-", i, " ", self.graph[i][parent[i]])
#
示
例代
码
g = Graph(5)
g.graph = [[0, 2, 0, 6, 0],