Practical 5
import heapq
def prim(graph, start):
mst, visited = [], set([start])
edges = [(weight, start, v) for weight, v in graph[start]]
while edges:
weight, u, v = heapq.heappop(edges)
if v not in visited:
visited.add(v)
mst.append((u, v, weight))
edges.extend((next_weight, v, next_vertex) for next_weight, next_vertex in
graph[v] if next_vertex not in visited)
heapq.heapify(edges)
return mst
graph = {
0: [(4, 1), (3, 2)],
1: [(4, 0), (1, 2), (2, 3)],
2: [(3, 0), (1, 1), (4, 3)],
3: [(2, 1), (4, 2)]
}
mst = prim(graph, 0)
print("Edges in the Minimum Spanning Tree:")
for u, v, weight in mst:
print(f"{u} - {v}: {weight}")
Output -
Algorithm for Prims Algorithm
function prim(graph, start_vertex):
mst_edges = []
visited = set()
priority_queue = MinHeap()
visited.add(start_vertex)
for each edge in graph.edges[start_vertex]:
priority_queue.insert(edge)
while not priority_queue.is_empty():
min_edge = priority_queue.extract_min()
u = min_edge.source
v = min_edge.destination
if v not in visited:
mst_edges.append(min_edge)
visited.add(v)
for each edge in graph.edges[v]:
if edge.destination not in visited:
priority_queue.insert(edge)
return mst_edges
Prim's algorithm is a greedy algorithm used to find the Minimum Spanning Tree
(MST) of a weighted, undirected graph. The MST is a subset of the edges that
connects all vertices together without cycles and with the minimum possible total
edge weight.
The time complexity of Prim's algorithm depends on the data structure used for
the priority queue:
● Using a simple array: O(V^2)
● Using a binary heap (like in the provided code): O(ElogV) where E is the
number of edges and V is the number of vertices.
