{"id":20088,"date":"2025-11-27T06:28:55","date_gmt":"2025-11-27T06:28:55","guid":{"rendered":"https:\/\/www.kaashivinfotech.com\/blog\/?p=20088"},"modified":"2025-11-27T06:28:55","modified_gmt":"2025-11-27T06:28:55","slug":"prims-algorithm-explained","status":"publish","type":"post","link":"https:\/\/www.kaashivinfotech.com\/blog\/prims-algorithm-explained\/","title":{"rendered":"Prim\u2019s Algorithm \u2013 Explained with a Pseudocode Example"},"content":{"rendered":"

What Is Prim\u2019s Algorithm?<\/h2>\n
\n

Prim\u2019s Algorithm is a greedy algorithm used to find a Minimum Spanning Tree (MST) from a weighted, connected, undirected graph.<\/strong><\/p>\n<\/blockquote>\n

Yep \u2014 that\u2019s the one-line exam-ready answer. But let\u2019s make it human.<\/p>\n

Think of Prims like building a road network between multiple cities using the minimum cost possible, without creating loops.<\/p>\n

You start from one city (any city), pick the cheapest connection, then from the visited cities pick the next cheapest edge\u2026 and you repeat.<\/p>\n

\"\"<\/p>\n

How Prim\u2019s Algorithm Works (Step-by-Step)<\/strong><\/h2>\n
    \n
  1. \n

    Pick any vertex<\/strong> as a starting point. Mark it \u201cvisited\u201d \/ \u201cin MST\u201d.<\/p>\n<\/li>\n

  2. \n

    Look at all edges from visited vertices<\/strong> that go to unvisited vertices<\/strong>.<\/p>\n<\/li>\n

  3. \n

    Choose the edge with the smallest weight<\/strong> among them. Add that edge + the new vertex to MST (mark visited).<\/p>\n<\/li>\n

  4. \n

    Update the list of \u201ccandidate edges\u201d: now include edges from this newly added vertex (that lead to unvisited vertices).<\/p>\n<\/li>\n

  5. \n

    Repeat steps 2\u20134 until all vertices are visited \/ included<\/strong>.<\/p>\n<\/li>\n<\/ol>\n

    Because we always pick the cheapest available edge that expands the tree \u2014 we ensure the total cost remains minimal.<\/p>\n

    This greedy, \u201cgrow-step-by-step\u201d nature makes Prim\u2019s algorithm efficient and intuitive when you visualize graphs.<\/p>\n

    Pseudocode for Prim\u2019s Algorithm<\/h2>\n
    function Prim(graph):\r\n    MST = empty set of edges\r\n    start = any vertex in graph\r\n    visited = { start }\r\n    candidateEdges = all edges from start\r\n\r\n    while visited does not include all vertices:\r\n        edge = the edge from candidateEdges with minimum weight\r\n        (u, v, w) = edge   \/\/ u: visited side, v: unvisited side\r\n        add edge to MST\r\n        add v to visited\r\n        remove that edge from candidateEdges\r\n        add to candidateEdges all edges from v that lead to unvisited vertices\r\n\r\n    return MST\r\n<\/pre>\n
    (Note: Implementation details \u2014 like how you store edges, pick minimum efficiently \u2014 may vary depending on graph representation.)<\/em><\/p>\n
    This pseudocode aligns with common textbook\/explanation versions of Prim\u2019s algorithm<\/a>.<\/p>\n
    Example Implementation (Python)<\/h2>\n
    import heapq\r\n\r\ndef prim(graph, start):\r\n    visited = set([start])\r\n    edges = [\r\n        (weight, start, to_node)\r\n        for to_node, weight in graph[start]\r\n    ]\r\n    heapq.heapify(edges)\r\n\r\n    mst = []\r\n    while edges:\r\n        weight, frm, to = heapq.heappop(edges)\r\n        if to not in visited:\r\n            visited.add(to)\r\n            mst.append((frm, to, weight))\r\n\r\n            for next_node, next_weight in graph[to]:\r\n                if next_node not in visited:\r\n                    heapq.heappush(edges, (next_weight, to, next_node))\r\n    return mst\r\n<\/pre>\n
    If you define the graph<\/code> as adjacency lists (with nodes mapped to lists of (neighbor, weight)<\/code>), this gives the MST edges as mst<\/code>. This is a common efficient way to implement Prim\u2019s algorithm using a priority queue (heap) \u2014 which improves performance, especially for sparse graphs.<\/p>\n
    \"\"<\/p>\n
    Let\u2019s take a sample weighted graph:<\/h3>\n
        (2)\r\nA ------- B\r\n| \\       |\r\n4   3     5\r\n|     \\   |\r\nC ------- D\r\n     (6)\r\n<\/pre>\n
    Step-by-step using Prim\u2019s:<\/strong><\/p>\n\n\n\n\n\n\n\n\n
    Step<\/th>\nChosen Edge<\/th>\nWeight<\/th>\nMST Nodes<\/th>\n<\/tr>\n<\/thead>\n
    1<\/td>\nStart at A<\/td>\n\u2014<\/td>\nA<\/td>\n<\/tr>\n
    2<\/td>\nA \u2192 B<\/td>\n2<\/td>\nA, B<\/td>\n<\/tr>\n
    3<\/td>\nA \u2192 C<\/td>\n4<\/td>\nA, B, C<\/td>\n<\/tr>\n
    4<\/td>\nB \u2192 D<\/td>\n5<\/td>\nA, B, C, D<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
    Total MST Cost = 2 + 4 + 5 = 11<\/strong><\/h3>\n
    No cycles.
    All nodes connected.<\/p>\n
    Prim\u2019s Algorithm vs Kruskal\u2019s Algorithm<\/h2>\n
    \"\"<\/p>\n\n\n\n\n\n\n\n\n
    Feature<\/th>\nPrim\u2019s<\/th>\nKruskal\u2019s<\/th>\n<\/tr>\n<\/thead>\n
    Approach<\/td>\nGrows from a starting node<\/td>\nSorts & connects edges globally<\/td>\n<\/tr>\n
    Works well with<\/td>\nDense graphs<\/td>\nSparse graphs<\/td>\n<\/tr>\n
    Data structure support<\/td>\nPriority Queue (Binary Heap)<\/td>\nDisjoint Set (Union-Find)<\/td>\n<\/tr>\n
    Initial choice<\/td>\nRandom starting vertex required<\/td>\nNo starting vertex<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
    Real World Applications of Prim\u2019s Algorithm<\/h2>\n