## ``` pgr_kruskal ```

``` pgr_kruskal ``` - Minimum spanning tree of a graph using Kruskal’s algorithm.

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

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