Prim's Algorithm

Algorithms

Prim's algorithm finds a minimum spanning tree (MST) for a connected weighted graph by starting from an arbitrary vertex and repeatedly adding the minimum-weight edge that connects a vertex in the MST to a vertex outside it.

Algorithm

The algorithm maintains a priority queue of edges and grows the MST by always adding the minimum-weight edge that connects the current MST to a new vertex.

Time Complexity

With a binary heap, the time complexity is $O (E lo g V)$ , where $E$ is the number of edges and $V$ is the number of vertices.

Implementation

import heapq

def prim(graph, start):
    # Priority queue to store edges (weight, vertex)
    min_heap = [(0, start)]
    mst_set = set()
    total_weight = 0
    mst_edges = []

    while min_heap:
        weight, u = heapq.heappop(min_heap)
        
        if u in mst_set:
            continue
        
        # Add vertex to MST
        mst_set.add(u)
        total_weight += weight
        
        if weight > 0:
            mst_edges.append((prev_vertex, u, weight))
        
        # Explore neighbors
        for v, edge_weight in graph[u]:
            if v not in mst_set:
                heapq.heappush(min_heap, (edge_weight, v))
                prev_vertex = u

    return mst_edges, total_weight

# Example usage
if __name__ == "__main__":
    # Define the graph as an adjacency list with weights
    graph = {{
        'A': [('B', 4), ('C', 2)],
        'B': [('A', 4), ('C', 5), ('D', 10)],
        'C': [('A', 2), ('B', 5), ('D', 3)],
        'D': [('B', 10), ('C', 3)]
    }}
    
    # Run Prim's algorithm
    start_node = 'A'
    mst_edges, total_weight = prim(graph, start_node)
    
    # Print results
    print("Edges in the Minimum Spanning Tree:")
    for u, v, weight in mst_edges:
        print("{} - {}: {}".format(u, v, weight))
    print("Total weight of MST: {}".format(total_weight))