Minimum Spanning Tree

Minimum Spanning Tree

Finding the minimum spanning tree of a weighted undirected graph is a fundamental problem that applies to many areas. QuikGraph provides 2 implementations to solve this problem:

• Prim's algorithm is based on Dijkstra shortest path. This algorithm is implemented as an extension method in AlgorithmExtensions. This method returns a sequence of edges that represent the tree.

IUndirectedGraph<TVertex, TEdge> graph = ...;
Func<TEdge, double> edgeWeights = ...;
IEnumerable<TEdge> minimumSpanningTree = graph.MinimumSpanningTreePrim(edgeWeights);

• Kruskal's algorithm is based on disjoint-sets. This algorithm can be invoked similarly to MinimumSpanningTreePrim.

IUndirectedGraph<TVertex, TEdge> graph = ...;
Func<TEdge, double> edgeWeights = ...;
IEnumerable<TEdge> minimumSpanningTree = graph.MinimumSpanningTreeKruskal(edgeWeights);