Articles Details
Type: Computer Science Theory
Subject: Linear Programming
Background: Algorithm, Graph.
Prim algorithm is a method that helps to find a Minimum Spanning Tree from a connected undirected weighted graph. In this article we will learn the essential of the Prim algorithm beginning with the intuitive idea behind it and finishing with it computational complexity after a look at the algorithm structure
Intuitive Idea
The intuitive idea is simple. Prim algorithm is greedy (at every step we build the best solution we can) and create the Minimum Spanning Tree one Node at a time. Now, we will take a look to the Algorithm structure
Algorithm Structure
- create a tree containing a single node, chosen arbitrarily from the graph
- create a set containing all the arcs in the graph
- loop until every arc in the set connects two vertices in the tree
Notice that add an arc to the tree means add a node because one node was already on the tree.
Algorithm architecture
We are looking for the execution time in respect with the input size of our problem. Let’s assume we have a graph of n nodes and m arcs.
The step 1 and 2 can be done in a constant time. Let’s consider in more detail the Step 3:
3.1 means to order all arcs in ascending order of their weight. Our set contains at max m arcs, so with a Quicksort, the execution time of this step is O(logm).
3.2 can be execute in constant time (it’s an assignment).
Now we do the step 3 n times (number of nodes) because the algorithm add one node at a time till the last.
So the complexity is O(nlogm).
Conclusion
In this article, we’ve covered the Intuitive idea behind the Prim’s algorithm and his computational complexity. Now if want to see the algorithm in action, you can find some Java applet. I advise to visit this one:
7 Java applets demos for the Kruskal algorithm
Thank you for your time!