# pgRouting Manual (3.6)

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