Prim’s Algorithm For Minimum Spanning Tree (Mst) :What You Need To Know

by

What is Prim s Algorithm for Minimum Spanning Trees?

A weighted-edge graph can be used to generate a minimum spanning tree using the prim s technique in computer science. Similar to Krsukal’s method, it is a greedy algorithm. Instead of looking for a solution globally, a greedy algorithm uses the most effective method for finding a solution step by step. In general, greedy algorithms may be slower than more optimal, non-greedy algorithms, but they can be good for approaching a globally optimal solution to a problem.

In order to find minimum spanning trees, one uses the Prim algorithm. A type of graph called a minimum spanning tree has all of its vertices connected without forming any cycles, and its overall edge weight is as little as it can be.

In reality, Robert C. Prim and Edsger W. Dijkstra, two computer scientists, independently developed and published Prim’s algorithm in 1957 and 1959, respectively. The original discovery of Prim’s algorithm was made by the Czech mathematician Vojt ch Jarn k in 1930. As a result, the algorithm is often referred to as the Prim Dijkstra algorithm, the Prim Jarnik algorithm, or the DJP algorithm.

How Does Prim s Algorithm Work?

Prim’s algorithm appears to have six steps, but several of them must be repeatedly carried out before the computer program can move on to the next one rationally. However, there are many more steps needed to complete the program when it is coded than the six simple ones needed to finish the algorithm on paper.

The following are the six steps as written:

  1. Determine an arbitrary vertex as the starting point of the minimum spanning tree.
  2. Find the edges with the lowest weights connecting to the starting point of the minimum spanning tree.
  3. Continue connecting vertices using the edges with the lowest weights without creating cycles.
  4. Once there exist fringe vertices that are not connected to the graph, begin finding the edges with the lowest weights that connect the fringe vertices to the minimum spanning tree.
  5. Add the edges that do not create cycles until all vertices are connected.
  6. Complete the minimum spanning tree.

Is Prim s Algorithm Correct? What s the Proof for Prim s Algorithm?

Since Jarnik first discovered Prim’s algorithm in 1930, it has been validated and published numerous times. You may read a lot of published proofs for Prim’s algorithm online. We’re going to use the one from Hein’s Discrete Structures, though.

1st Theorem In the event where S is the spanning tree that Prim’s method chooses for the input graph G = (V, E),

then S is a spanning tree for G with the lowest weight.

Proof: Since the evidence is incongruous, it is safe to believe that S is not the minimum weight. Let ES =

Let the series of edges selected by Prim’s method (in this order) be (e1, e2,, en 1).

Suppose U is a minimum-weight spanning tree with edges coming from the longest prefix of

ES sequence.

Let ei = x, y represent the first edge that Prim’s algorithm adds to S that is not in U.

W is the collection of vertices that are present before choosing “x, y.” Take note that it implies that U

contains edge ei1 but not edge ei2, edges e1, e2, and

Let a, b be the first edge on the path x y that has one edge since there must be a path x y in U.

endpoint (a) inside W and endpoint (b) outside W, as shown in the diagram below:

A diagram to illustrate Prim s Algorithm.

History-Computer.com

Once the set of edges T = U + x, y, a, and b is defined, it becomes clear that T is a spanning tree for

Graph G. Take into account the following three scenarios for the weights of edges “x, y” and “a, b”:

Case 1, where w(a, b) > w(x, y) In this instance, in order to create T, we added an edge that

w(T) = less weight than the one we removed.

Case 2, where w(a, b) = w(x, y) Since w(T) = w(U) in this instance, T is likewise a minimum spanning tree.

tree. Additionally, because Prim’s algorithm hasn’t chosen edge “a, b” yet, that edge

One of e1, e2, or ei 1 cannot be the case. This suggests that T has the edges e1, e2, and ei.

, which

is an extended prefix of ES, longer than U. The definition of tree U is in conflict with this.

Case 3, with “a, b”

The algorithm will choose a and b at this stage. This goes against the idea of edge “x, y.”

Our initial presumption (that S is not minimumweight) must be false because every scenario leads to contradictions. It establishes the theorem.

The following pseudocode can be used to further express the Prim algorithm:

T =  ;
U = { 1 };
while (U   V)
    let (u, v) be the lowest cost edge such that u   U and v   V - U;
    T = T   {(u, v)}
    U = U   {v}

Practical Applications of Prim s Algorithm

Prim’s algorithm and Kruskal’s algorithm, its sister method, are valuable in everyday life and not just in computer programming and higher mathematics. You’ve probably utilized the kinds of graphs that Prim’s and Kruskal’s algorithms use if you’ve ever used Google Maps. Which algorithm will perform better depends on whether the graph is heavily or usually populated. When used to a dense graph, Kruskal’s algorithm will have difficulty and may possibly yield poor results. However, you may verify the outcomes if you apply Kruskal’s method on a dense graph by passing the resulting graph through a computer that uses Prim’s algorithm.

Kruskal’s algorithm is frequently used in the following real-world application cases:

  • TV Networking
  • LAN Networking
  • Networking pipes for water or gas
  • Electrical grids
  • Single-link clusters
  • Tour operations
  • Landing cables

The following real-world usage situations may require additional verification using Prim’s algorithm:

  • Any use case where you would use Kruskal s algorithm can be resolved using Prim s algorithm
  • Game Development
  • Irrigation channels
  • Placing Artificial Intelligence)
  • Cognitive Science
  • Network for roads and Rail tracks connecting all the cities

Practical Examples of Prim s Algorithm in Code

Prim’s algorithm requires computer coding in order to be used efficiently because performing the algorithm’s math by hand is impractical unless the network is quite tiny. Almost any programming language can be used to write a program that executes Prim’s algorithm on a graph, however we’ll provide examples in a few different languages.

Python

INF = 9999999
V = 5
G = [[0, 9, 75, 0, 0],
     [9, 0, 95, 19, 42],
     [75, 95, 0, 51, 66],
     [0, 19, 51, 0, 31],
     [0, 42, 66, 31, 0]]
selected = [0, 0, 0, 0, 0]
no_edge = 0
selected[0] = True
print("Edge : Weight\n")
while (no_edge  G[i][j]:
                        minimum = G[i][j]
                        x = i
                        y = j
    print(str(x) + "-" + str(y) + ":" + str(G[x][y]))
    selected[y] = True
    no_edge += 1

Java

import java.util.Arrays;
class PGraph {
  public void Prim(int G[][], int V) {
    int INF = 9999999;
    int no_edge; // number of edge
    boolean[] selected = new boolean[V];
    Arrays.fill(selected, false);
    no_edge = 0;
    selected[0] = true;
    System.out.println("Edge : Weight");
    while (no_edge  G[i][j]) {
                min = G[i][j];
                x = i;
                y = j;
              }
            }
          }
        }
      }
      System.out.println(x + " - " + y + " :  " + G[x][y]);
      selected[y] = true;
      no_edge++;
    }
  }
  public static void main(String[] args) {
    PGraph g = new PGraph();
    int V = 5;
    int[][] G = { { 0, 9, 75, 0, 0 }, { 9, 0, 95, 19, 42 }, { 75, 95, 0, 51, 66 }, { 0, 19, 51, 0, 31 },
        { 0, 42, 66, 31, 0 } };
    g.Prim(G, V);
  }
}

Final Thoughts

One example of advanced mathematics employed on a regular basis to carry out tasks for our world’s infrastructure and technology is the prim’s algorithm. Prim’s algorithm is probably never going to be useful to the average person, but it never hurts to brush up on higher mathematics. Leave us a comment here or on social media if you liked learning a little bit about this algorithm and how it operates!

Leave a Comment