pgr_kruskal - pgRouting Manual (3.0)

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

Example

Minimum Spanning Forest

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:

ANY-INTEGER

SMALLINT, INTEGER, BIGINT

ANY-NUMERICAL

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

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