pgr_prim
¶
pgr_prim
— Minimum spanning forest of a graph using Prim’s algorithm.

Boost Graph Inside¶
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
pgr_prim(Edges SQL) RETURNS SET OF (edge, cost) OR EMPTY SET
- Example
Minimum spanning forest of a subgraph
SELECT edge, cost FROM pgr_prim(
'SELECT id, source, target, cost, reverse_cost FROM edge_table WHERE id < 14'
) ORDER BY edge;
edge | cost
------+------
1 | 1
2 | 1
3 | 1
4 | 1
5 | 1
6 | 1
7 | 1
9 | 1
10 | 1
11 | 1
13 | 1
(11 rows)
Parameters¶
Parameter |
Type |
Description |
---|---|---|
|
Edges SQL as described below. |
Inner query¶
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¶
- include:: pgRouting-concepts.rst
- start-after
r-edge-cost-start
- end-before
r-edge-cost-end
See Also¶
The queries use the Sample Data network.
Indices and tables