Stay organized with collections
Save and categorize content based on your preferences.
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);
[[["Easy to understand","easyToUnderstand","thumb-up"],["Solved my problem","solvedMyProblem","thumb-up"],["Other","otherUp","thumb-up"]],[["Missing the information I need","missingTheInformationINeed","thumb-down"],["Too complicated / too many steps","tooComplicatedTooManySteps","thumb-down"],["Out of date","outOfDate","thumb-down"],["Samples / code issue","samplesCodeIssue","thumb-down"],["Other","otherDown","thumb-down"]],["Last updated 2024-08-06 UTC."],[[["The C++ library provides an implementation of Kruskal's minimum spanning tree algorithm to identify the minimum set of edges connecting all nodes in a graph."],["It features functions like `BuildKruskalMinimumSpanningTree` and `BuildKruskalMinimumSpanningTreeFromSortedArcs` for computing the minimum spanning tree with varying inputs."],["The algorithm has a time complexity of O(E \\* log(E)), where E represents the number of edges, making it efficient for large graphs."],["Future plans include a global Minimum Spanning Tree API to automatically choose between Prim's and Kruskal's algorithms for optimal performance."]]],["Kruskal's algorithm, with O(E \\* log(E)) complexity, finds the minimum spanning tree or forest in a graph, returning the indices of arcs in the tree. It treats each arc as undirected and ignores nodes without arcs. Two functions are provided: `BuildKruskalMinimumSpanningTree`, which takes a graph and arc comparator, and `BuildKruskalMinimumSpanningTreeFromSortedArcs`, which uses pre-sorted arcs for potentially incremental computations. A `BuildPrimMinimumSpanningTree` function is also available, and a global API for switching between Kruskal and Prim is planned.\n"]]
