DFS - Category¶
Traversal using Depth First Search.
Proposed
Warning
Proposed functions for next mayor release.
- They are not officially in the current release.
- They will likely officially be part of the next mayor release:
- The functions make use of ANY-INTEGER and ANY-NUMERICAL
- Name might not change. (But still can)
- Signature might not change. (But still can)
- Functionality might not change. (But still can)
- pgTap tests have being done. But might need more.
- Documentation might need refinement.
- pgr_depthFirstSearch - Proposed - Depth first search traversal of the graph.
In general:
- 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.
See Also¶
- Boost: Prim’s algorithm
- Boost: Kruskal’s algorithm
- Wikipedia: Prim’s algorithm
- Wikipedia: Kruskal’s algorithm
Indices and tables