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
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 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)
Inner Queries¶
Edges SQL¶
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 (
|
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¶
- Spanning Tree - Category
- Prim - Family of functions
- The queries use the Sample Data network.
- Boost: Prim’s algorithm documentation
- Wikipedia: Prim’s algorithm
Indices and tables