Description¶

This algorithm finds the minimum spanning forest in a possibly disconnected graph using Kruskal’s algorithm.

The main Characteristics are:

• It’s implementation is only on undirected graph.
• Process is done only on edges with positive costs.
• The total weight of all the edges in the tree or forest is minimized.
• 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.
• Kruskal’s running time: \(O(E * log E)\)

• EMPTY SET is returned when there are no edges in the graph.

Signatures¶

Summary

pgr_kruskal(edges_sql)

RETURNS SET OF (seq, edge, cost)
OR EMPTY SET

SELECT * FROM pgr_kruskal(
    'SELECT id, source, target, cost, reverse_cost
        FROM edge_table ORDER BY id'
) ORDER BY edge;
 edge | cost
------+------
    1 |    1
    2 |    1
    3 |    1
    6 |    1
    7 |    1
   10 |    1
   11 |    1
   12 |    1
   13 |    1
   14 |    1
   15 |    1
   16 |    1
   17 |    1
   18 |    1
(14 rows)

Parameters¶

Inner query¶

Where:

Result Columns¶

Returns SET OF (edge, cost)

See Also¶

• Spanning Tree - Category
• Kruskal - Family of functions
• The queries use the Sample Data network.
• Boost: Kruskal’s algorithm documentation
• Wikipedia: Kruskal’s algorithm

Indices and tables

• Index
• Search Page