Minimum Spanning Tree

Finding the minimum spanning tree of an weighted undirected graph is a fundamental problem that applies to many areas. QuickGraph provides 2 implementations to solve this problem: Prim's and Kruskal's.
  • 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> g = ...;
    Func<TEdge, double> edgeWeights = ...;
    IEnumerable<TEdge> mst = g.MinimumSpanningTreePrim(g, edgeWeights);
  • Kruskal's algorithm is based on disjoint-sets. This algorithm can be invoked similarly to MinimumSpanningTreePrim.
    IEnumerable<TEdge> mst = g.MinimumSpanningTreeKruskal(g, edgeWeights);

Last edited Jan 2, 2009 at 10:50 AM by pelikhan, version 3

Comments

No comments yet.