C++ Reference: minimum_spanning_tree
Note: 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: Arguments: | ||
BuildKruskalMinimumSpanningTreeFromSortedArcs | Arguments: | ||
BuildPrimMinimumSpanningTree | Return type: Arguments: |