pgr_prim
¶
pgr_prim
— Minimum spanning forest of a graph using Prim’s algorithm.
Availability
Version 3.0.0
New Official function
Description¶
This algorithm finds the minimum spanning forest in a possibly disconnected graph using Prim’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.
Prim’s running time: \(O(E * log V)\)
EMPTY SET is returned when there are no edges in the graph.
Signatures¶
Summary
(edge, cost)
- Example:
Minimum spanning forest of a subgraph
SELECT edge, cost FROM pgr_prim(
'SELECT id, source, target, cost, reverse_cost
FROM edges WHERE id < 14'
) ORDER BY edge;
edge | cost
------+------
1 | 1
2 | 1
3 | 1
4 | 1
6 | 1
7 | 1
8 | 1
9 | 1
10 | 1
12 | 1
13 | 1
(11 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