Graphs/Depth First Traversal

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

Also see DFS

Notes

What DFS Gets Us

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.

Pseudocode

Pseudocode for a recursive depth-first search follows. This DFS function takes two arguments: a graph G, and a vertex u from which to begin the depth-first search. The DFS function returns a collection of vertices that are reachable from u.

# Does a depth first search on graph G starting from vertex u
# Returns collection of vertices reachable from u
DFS(G, u):
for each outgoing edge e = (u,v) of u:
	if vertex v not visited:
		mark vertex v as visited
		call DFS(G,v)