# pgRouting Manual (3.6)

## 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