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
(edge, cost)
- 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 as described below. |
Inner Queries¶
Edges SQL¶
Column |
Type |
Default |
Description |
---|---|---|---|
|
ANY-INTEGER |
Identifier of the edge. |
|
|
ANY-INTEGER |
Identifier of the first end point vertex of the edge. |
|
|
ANY-INTEGER |
Identifier of the second end point vertex of the edge. |
|
|
ANY-NUMERICAL |
Weight of the edge ( |
|
|
ANY-NUMERICAL |
-1 |
Weight of the edge (
|
Where:
- ANY-INTEGER:
SMALLINT
,INTEGER
,BIGINT
- ANY-NUMERICAL:
SMALLINT
,INTEGER
,BIGINT
,REAL
,FLOAT
Result Columns¶
Returns SET OF (edge, cost)
Column |
Type |
Description |
---|---|---|
|
|
Identifier of the edge. |
|
|
Cost to traverse the edge. |
See Also¶
The queries use the Sample Data network.
Indices and tables