Prim's MST
This algorithm is another one approach to find the MST - minimum spanning tree. The main idea is to partition a set of vertices into two: included to MST already and excluded. Step by step you’ll replace vertices from the second set to the first by picking the less weighted edge that connects both sets.
So algorithm is next:
- Put the start vertex to the
visited, the rest will beunvisited, i. e. in the second set. - Start adding vertices. Visit all neighbors for all visited vertices and select the edge with least weight, that does not create a cycle. Mark the adjacent vertex as
visited. - Do the 2) until all vertices are visited.
You can find a lot of different implementations, but the main idea is to put all vertices into the visited set step by step.
Task
Swipe to start coding
Complete the primMST() algorithm inside Graph class. Init the graph and call this method. To detect a cycle, use BFS() or DFS() algorithms. You can implement it inside the class.
Solution
from math import inf
class Graph:
def __init__(self, vertices=0):
# init graph with its vertices
self.g = [[0 for _ in range(vertices)] for _ in range(vertices)]
def addEdge(self, u, v, w, o = False):
# u - start vertex, v - end vertex, w - weight of edge, o - is it oriented
self.g[u][v] = w
if not o:
self.g[v][u] = w
def __str__(self):
out = ""
for row in self.g:
out += str(row) + ' '
return out
def primsMST(self):
n = len(self.g)
visited = [False for _ in range(n)]
dist = [inf for _ in range(n)]
parent = [-1 for _ in range(n)]
ans = []
dist[0] = 0
for i in range(n):
v = -1
for j in range(n):
if not visited[j] and (v == -1 or dist[j] < dist[v]):
v = j
if dist[v] == inf: return [] # there is no MST
visited[v] = True
if parent[v] != -1:
ans.append((v, parent[v]))
Everything was clear?
Thanks for your feedback!
Section 3. Chapter 4
from math import inf
class Graph:
def __init__(self, vertices=0):
# init graph with its vertices
self.g = [[0 for _ in range(vertices)] for _ in range(vertices)]
def addEdge(self, u, v, w, o = False):
# u - start vertex, v - end vertex, w - weight of edge, o - is it oriented
self.g[u][v] = w
if not o:
self.g[v][u] = w
def __str__(self):
out = ""
for row in self.g:
out += str(row) + ' '
return out
def primsMST(self):
n = len(self.g)
visited = [False for _ in range(n)] # already in MST
dist = [inf for _ in range(n)] # distance to the closest vertex from i-th
parent = [-1 for _ in range(n)] # parent for each vertex
ans = [] # list of edges
dist[0] = 0
for i in range(n):
v = -1 # looking for the closest unvisited vertex
for j in range(n):
if not _ _ _ and (v == -1 or _ _ _ < _ _ _):
v = _ _ _ # update v
if dist[v] == inf: return [] # there is no MST
visited[v] = _ _ _
if parent[v] != _ _: # if parent exists
ans.append((v, parent[v]))
for j in range(n):
if 0 < self.g[v][j] < dist[j]:
dist[j] = _ _ _
parent[j] = _ _ _
return ans
g = Graph(6)
g.addEdge(0,1,7)
g.addEdge(0,2,9)
g.addEdge(0,5,14)
g.addEdge(1,2,10)
g.addEdge(1,3,15)
g.addEdge(2,3,11)
g.addEdge(2,5,2)
g.addEdge(4,5,9)
g.addEdge(3,4,6)
print(g)
print(g.primsMST())
