In computer science, Prim’s algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph.

The algorithm operates by building this tree one vertex at a time, from an arbitrary starting vertex, at each step adding the cheapest possible connection from the tree to another vertex.

Prim's Algorithm

Prim’s algorithm starting at vertex A. In the third step, edges BD and AB both have weight 2, so BD is chosen arbitrarily. After that step, AB is no longer a candidate for addition to the tree because it links two nodes that are already in the tree.

Minimum Spanning Tree

A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted (un)directed graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. That is, it is a spanning tree whose sum of edge weights is as small as possible. More generally, any edge-weighted undirected graph (not necessarily connected) has a minimum spanning forest, which is a union of the minimum spanning trees for its connected components.

Minimum Spanning Tree

A planar graph and its minimum spanning tree. Each edge is labeled with its weight, which here is roughly proportional to its length.

Minimum Spanning Tree

This figure shows there may be more than one minimum spanning tree in a graph. In the figure, the two trees below the graph are two possibilities of minimum spanning tree of the given graph.

References

Implementations

  • 1

    # TODO: Implement in Python

  • 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

    function prim() {
  // Finds a tree so that there exists a path between
  // every two nodes while keeping the cost minimal
  let minD;

  let minI;
  let minJ;
  let sum = 0;
  const D = [];
  for (let i = 0; i < G.length; i++) D.push(0);
  D[0] = 1; // First node is visited
  for (let k = 0; k < G.length - 1; k++) { // Searching for k edges
    minD = Infinity;
    for (let i = 0; i < G.length; i++) {
      if (D[i]) // First node in an edge must be visited
      {
        for (let j = 0; j < G.length; j++) {
          if (!D[j] && G[i][j]) {
            
            // Second node must not be visited and must be connected to first node
            if (G[i][j] < minD) {
              // Searching for cheapest edge which satisfies requirements
              minD = G[i][j];
              minI = i;
              minJ = j;
            }
            
          }
        }
      }
    }
    
    D[minJ] = 1; // Visit second node and insert it into or tree
    sum += G[minI][minJ];
  }
  
  console.log(`The sum of all edges is: ${sum}`);
  
}

console.log('nodes that belong to minimum spanning tree are: ');

prim();