Spanning Tree - Category¶
A spanning tree of an undirected graph is a tree that includes all the vertices of G with the minimum possible number of edges.
For a disconnected graph, there there is no single tree, but a spanning forest, consisting of a spanning tree of each connected component.
Characteristics:
- It’s implementation is only on undirected graph.
- Process is done only on edges with positive costs.
- When the graph is connected
- The resulting edges make up a tree
- When the graph is not connected,
- Finds a minimum spanning tree for each connected component.
- The resulting edges make up a forest.
See Also¶
- Boost: Prim’s algorithm
- Boost: Kruskal’s algorithm
- Wikipedia: Prim’s algorithm
- Wikipedia: Kruskal’s algorithm
Indices and tables