pgr_kruskal¶
pgr_kruskal
— Returns the minimum spanning tree of graph using Kruskal algorithm.
Availability
- Version 3.0.0
- New Official function
Support
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)
|
|
reverse_cost | ANY-NUMERICAL |
-1 | Weight of the edge (target, source),
|
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