Spanning Tree - Category

• Kruskal - Family of functions

• Prim - Family of functions

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

• Index

• Search Page