Prim`s Algorithm

Given a weighted graph, many times we are interested in finding a minimum spanning tree (MST) for that graph. Prim's algorithm is a greedy method which does just this. A spanning tree is a subset of the edges of a graph that connects to every vertex, but contains no cycles. This spanning tree is called a minimum spanning tree if in addition the sum of the weights of the edges included in this tree is less than or equal to the sum of the weights of the edges of any other spanning tree for this graph.

Prim's algorithm works by building an initial tree and continuously growing the tree by adding the edge of least cost that will keep it as a tree. It can be explained with the following procedure.
1. Let Treev be the set of vertices included in the tree, and TreeE be the set of edges included in the tree. Initially TreeV and TreeE are empty.
2. Add an arbitrary vertex to TreeV (TreeE is still empty).
3. Find the edge e of minimum weight such that one vertex is in TreeV and vertex is not in TreeV. Add the associated vertex to TreeV, and add e to TreeE.
4. If edge was found in step 3, goto 5, else go to 6.
5. If the number of vertices in TreeV is less than the number of vertices in the original graph, then the graph is not connected and thus does not contain a minimum spanning tree. Goto 8.
6 If the number of vertices in TreeV is less than the number of vertices in the original graph, go to 2, else go to 7.
7. Output "The Minimum Spanning Tree is ", TreeE.
8. Output "This graph does not have a minimum spanning tree because it is not connected. "

Show Work?
your browser does not support the canvas tag


Recent Updates

  • 08-10-2017 Floyd-Warshall Shortest Paths
  • 08-01-2017 Degree Centrality of a Graph
  • 06-03-2017 Tarjan's Strongly Connected Components Algorithm
  • 03-20-2017 Longest Common Subsequence
  • 10-27-2016 Independent Set Puzzles
  • 06-28-2016 Lets Learn About XOR Encryption
  • 06-15-2016 Discrete-time Markov Chains
  • 03-01-2016 Topological Sort
  • 01-21-2016 The RSA Algorithm
  • 11-20-2015 How To Take Notes in Math Class
  • 10-28-2015 The Depth-First-Search Algorithm
  • 10-28-2015 The Breadth-First-Search Algorithm
  • 09-23-2015 ID3 Algorithm Decision Trees
  • 07-08-2015 Clique Problem Puzzles
  • 06-25-2015 Unidirectional TSP Puzzles
  • 04-04-2015 Learn About Descriptive Statistics
  • 02-19-2015 Slope Formula
  • 01-15-2015 Interactive Midpoint Formula
  • 12-18-2014 Triangle Sum Puzzle
  • 12-02-2014 The Bridge Crossing Problem