# 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);

`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`

[{ "type": "thumb-down", "id": "missingTheInformationINeed", "label":"Missing the information I need" },{ "type": "thumb-down", "id": "tooComplicatedTooManySteps", "label":"Too complicated / too many steps" },{ "type": "thumb-down", "id": "outOfDate", "label":"Out of date" },{ "type": "thumb-down", "id": "samplesCodeIssue", "label":"Samples / code issue" },{ "type": "thumb-down", "id": "otherDown", "label":"Other" }]
[{ "type": "thumb-up", "id": "easyToUnderstand", "label":"Easy to understand" },{ "type": "thumb-up", "id": "solvedMyProblem", "label":"Solved my problem" },{ "type": "thumb-up", "id": "otherUp", "label":"Other" }]