Algorithm - 2023.2 English

Vitis Libraries

Release Date
2023-12-20
Version
2023.2 English

The implemented Minimum Spanning Tree algorithm is based on the Prim algorithm. The description of the algorithm is as below:

Given an undirected graph, and a source vertex, print out a MST for the connected subgraph which contains the source vertex.

  1. Start with a set MSTNodes = {source vertex}
  2. 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
  3. Repeat 2 until MSTNodes has no edge linking to any other vertex in the graph.