Spanning Tree - Category - pgRouting Manual (3.3)

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.