# pgRouting Manual (3.3)

## pgr_kruskal

- Supported versions: Latest (3.3) 3.2 3.1 3.0

# pgr_kruskal

`pgr_kruskal` — Returns the minimum spanning tree of graph using Kruskal algorithm.

Boost Graph Inside

Availability

- Version 3.0.0

  - New Official function

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

Parameter | Type | Description
--- | --- | ---
Edges SQL | `TEXT` | SQL query described in Inner query.

## Inner query

Column | Type | Default | Description
--- | --- | --- | ---
id | `ANY-INTEGER` |  | Identifier of the edge.
source | `ANY-INTEGER` |  | Identifier of the first end point vertex of the edge.
target | `ANY-INTEGER` |  | Identifier of the second end point vertex of the edge.

cost

`ANY-NUMERICAL`

Weight of the edge (source, target)

- When negative: edge (source, target) does not exist, therefore it’s not part of the graph.

reverse_cost

`ANY-NUMERICAL`

-1

Weight of the edge (target, source),

- When negative: edge (target, source) does not exist, therefore it’s not part of the graph.

Where:

ANY-INTEGER

  SMALLINT, INTEGER, BIGINT

ANY-NUMERICAL

  SMALLINT, INTEGER, BIGINT, REAL, FLOAT

## Result Columns

Returns SET OF `(edge, cost)`

Column | Type | Description
--- | --- | ---
edge | `BIGINT` | Identifier of the edge.
cost | `FLOAT` | Cost to traverse the edge.

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