prim's algorithm

A greedy algorithm that uses a priority queue (like dijkstra’s algorithm) to construct the spanning tree.

• start with arbitrary node
• choose a min-weight edge that adds a new node to the tree

Steps:

1. Initialize a min-heap (priority queue).
2. Initialize a set to track vertices included in the MST.
3. Add an arbitrary vertex to the MST.
4. Push all edges connected to this vertex into the priority queue.
5. While #(vertices in the MST) < V: a. Extract the edge with the minimum weight from the priority queue. b. If the vertex connected by this edge is not in the MST: i. Add this vertex to the MST. ii. Add the edge to the MST. iii. Push all edges connected to this vertex into the priority queue.

def prims_algorithm(graph, start=0):
    n = len(graph)
    mst_cost = 0
    mst_edges = []
    visited = [False] * n
    min_heap = [(0, start, -1)]  # (weight, vertex, parent_vertex)
 
    while min_heap:
        weight, u, parent = heapq.heappop(min_heap)
        if visited[u]:
            continue
        visited[u] = True
        mst_cost += weight
        if parent != -1:
            mst_edges.append((parent, u, weight))
        for v, w in graph[u]:
            if not visited[v]:
                heapq.heappush(min_heap, (w, v, u))
 
    return mst_cost, mst_edges
 
# Example graph as an adjacency list
graph = {
    0: [(1, 4), (2, 1)],
    1: [(0, 4), (2, 2), (3, 1)],
    2: [(0, 1), (1, 2), (3, 5)],
    3: [(1, 1), (2, 5)]
}
 
mst_cost, mst_edges = prims_algorithm(graph)
print("Cost of MST:", mst_cost)
print("Edges in MST:", mst_edges)