Graphs/Depth First Traversal

This page covers depth-first traversal and depth-first search on a graph.

Also see DFS

Notes

A depth first traversal and search algorithm can be used as an algorithmic building block for a large number of problems.

DFS gives us:

• paths
• connectivity
• cycles
• spanning trees

Specifically, we can get different things on directed vs. undirected graphs.

On an undirected graph, DFS can be used to:

• Find the path between two given vertices, or report that none exists
• Test whether a graph is connected
• Compute the spanning tree of a graph (which can, in turn, be used to bootstrap a minimum spanning tree)
• Find the connected components of a graph
• Determine whether a graph has any cycles

On an undirected (connected) graph, to construct a spanning tree, do a DFS!

On a directed graph, DFS can be used to:

• Find a directed path between two given vertices, or report that none exists
• Determine the set of reachable vertices from a source vertex
• Test whether a graph is strongly connected
• Determine whether a graph has any cycles
• Compute the transitive closure of a graph

On a directed graph, to discover vertices reachable from a source vertex, do a DFS! To discover cycles, do a DFS and look for back-edges!

Note that a depth-first search requires that we be able to mark vertices and/or edges are explored, and be able to test if they have been explored in O(1) time. This is easiest to do by augmenting the vertex class, but can also be done by creating a map of vertices to booleans or vertices to edges.