Prim's Minimum Spanning Tree Algorithm

How Prim's Algorithm Works

Prim's algorithm finds a minimum spanning tree for a weighted undirected graph. It starts with an arbitrary node and grows the tree one edge at a time, always adding the lowest-weight edge that connects a tree vertex to a non-tree vertex.

Color representation:

• Blue nodes are not yet in the MST
• Green nodes are in the MST
• Gray edges are not part of the MST
• Yellow edge is the current edge being considered
• Green edges are part of the MST

function prim(graph, startVertex):
    mst = []
    visited = set()
    minHeap = MinHeap()

    visited.add(startVertex)
    addAdjacentEdgesToHeap(graph, startVertex, minHeap)

    while not minHeap.isEmpty() and len(mst) < graph.vertices - 1:
        edge = minHeap.extractMin()
        
        if edge.destination in visited:
            continue
        
        mst.append(edge)
        visited.add(edge.destination)
        addAdjacentEdgesToHeap(graph, edge.destination, minHeap)
        
        visualize(mst, visited, edge)

    return mst

function addAdjacentEdgesToHeap(graph, vertex, minHeap):
    for each neighbor in graph.getNeighbors(vertex):
        if neighbor not in visited:
            minHeap.add(Edge(vertex, neighbor, graph.getWeight(vertex, neighbor)))

function visualize(mst, visited, currentEdge):
    // Update UI to show:
    // 1. Vertices included in the MST so far
    // 2. Edges included in the MST
    // 3. Highlight the current edge being added
    // 4. Show the growing tree as new edges are added