DFS - Category

Traversal using Depth First Search.

• pgr_kruskalDFS

• pgr_primDFS

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

• Index

• Search Page