## pgr_kruskal

``` pgr_kruskal ``` - Returns the minimum spanning tree of graph using Kruskal 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.

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