# pgRouting Manual (3.6)

## pgr_kruskal

# `pgr_kruskal`

`pgr_kruskal` — Minimum spanning tree of a graph using Kruskal’s 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.

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

- The total weight of all the edges in the tree or forest is minimized.

- 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 `(edge, cost)`
OR EMPTY SET

Example:

  Minimum spanning forest

    SELECT * FROM pgr_kruskal(
      'SELECT id, source, target, cost, reverse_cost
      FROM edges 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` | Edges SQL as described below.

## Inner Queries

### Edges SQL

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`)

`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

- Wikipedia: Kruskal’s algorithm

Indices and tables

- Index

- Search Page