C++ Reference: minimum_spanning_tree

This documentation is automatically generated.



Implementation of Kruskal's mininumum spanning tree algorithm (c.f. https://en.wikipedia.org/wiki/Kruskal%27s_algorithm). Returns the index of the arcs appearing in the tree; will return a forest if the graph is disconnected. Nodes without any arcs will be ignored. Each arc of the graph is interpreted as an undirected arc. Complexity of the algorithm is O(E * log(E)) where E is the number of arcs in the graph. Memory usage is O(E * log(E)).

TODO(user): Add a global Minimum Spanning Tree API automatically switching between Prim and Kruskal depending on problem size.

Version taking sorted graph arcs. Allows somewhat incremental recomputation of minimum spanning trees as most of the processing time is spent sorting arcs. Usage: ListGraph<int, int> graph(...); std::vector<int> sorted_arcs = ...; std::vector<int> mst = BuildKruskalMinimumSpanningTreeFromSortedArcs( graph, sorted_arcs);

Function Type Arguments Comments
BuildKruskalMinimumSpanningTree

Return type: std::vector<typename Graph::ArcIndex>

Arguments: const Graph& graph, const ArcComparator& arc_comparator

BuildKruskalMinimumSpanningTreeFromSortedArcs

Arguments: const Graph& graph, const std::vector<typename Graph::ArcIndex>& sorted_arcs

BuildPrimMinimumSpanningTree

Return type: std::vector<typename Graph::ArcIndex>

Arguments: const Graph& graph, const ArcValue& arc_value

Send feedback about...