The implemented Minimum Spanning Tree algorithm is based on the Prim algorithm. The description of the algorithm is as follows:
Given an undirected graph, and a source vertex, print out a MST for the connected subgraph, which contains the source vertex.
- Start with a set MSTNodes = {source vertex}
- For all vertices in MSTNodes, find another vertex y in the graph but not MSTNodes, which is connected to a vertex x in MSTNodes such that the weight on the edge e(x,y) is the smallest among all such edges from a vertex in MSTNodes to a vertex not in MSTNodes. Add y to MSTNodes, and add the edge (x,y) to MST.
- Repeat step2 until MSTNodes has an edge linking to any other vertex in the graph.