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
# Results in a collection of vertices reachable from vertex u,
# in the form of (v,e) pairs (vertex v reachable from vertex u via edge e)
DFS(G, u):
	for each outgoing edge e = (u,v) of u:
		if vertex v not visited:
			mark vertex v as visited via edge e
			add (v,e) pair to container
			call DFS(G,v)

DFS Tree

Because of the fact that the depth-first search must proceed in an ordered manner, and cannot re-visit vertices that have already been vertices, we can think of the depth-first search as forming a tree.

A tree is a type of acyclic graph in which each vertex (node) has one ancestor and zero or more children. As we traverse the graph with a depth-first search, we are likewise forming a path in which each vertex we visit has one ancestor (the vertex preceding it, which has now been marked as visited) and zero or more children (zero if we reach a vertex that has only one outgoing edge, or if all of the vertex's edges lead to already-visited edges).

Like a tree, we can wind up with branches when we reach a "dead end" (a leaf node of the DFS tree) and have to backtrack to prior vertices (ancestor nodes in the DFS tree).

Edge Classification

When performing a depth-first search, we are interested in visiting each vertex only once. Thus, when we are considering a given vertex, we only want to consider edges that connect it to other unvisited vertices. This means we need a way of marking vertices as visited.

Thus, it is important to classify the edges that connect to a given vertex as belonging to one of three classes:

• Back edge - connects a vertex to an ancestor vertex in the DFS tree
• Forward edge - connects a vertex to its descendant in the DFS tree
• Cross edge - connects a vertex to a vertex that is not an ancestor or a descendant in the DFS tree

Example: Undirected Graph

Example: Directed Graph

Related

Graphs:

• Graphs#Graph Traversals
• Graphs/Depth First Traversal
• Graphs/Breadth First Traversal
• Graphs/Euler Tour
• Graphs/Euler Circuit

Traversals on trees:

• Trees/Preorder
• Trees/Postorder
• Trees/Inorder

Breadth-first search and traversal on trees:

• BFS - breadth first search
• BFT - breadth first traversal

Depth-first search and traversal on trees:

• DFS - depth first search
• DFT - depth first traversal

OOP design patterns:

• Tree Traversal/Traversal Method Template

Category:Traversal