Depth-First Search

Graph Traversal

Systematic traversal of graph are similar to preorder and postorder traversal for trees. There are two graph traversals, depth-first and breadth-first search. Frequently the graph searches start at an arbitrary vertex. The searches are efficient if they are done in O(n + m), where n is the number of vertices and m the number of edges.

Graph traversal can be used to determine the general characteristic of the graph, or to solve a specific problem on a particular graph, for example:

Routing phone calls, or packets
Planning a car trip
Locate a particular vertex, for example a win position in a game.

Depth-first Search

We start the graph traversal at an arbitrary vertices, and go down a particular branch until we reach a dead end. Then we back up and go as deep possible. In this way we visit all vertices, and all edges. Goodrich and Tamassia like to explain the traversal as below:

The search is similar to searching maze of hallways, edges, and rooms, vertices, with a string and paint. We fix the string in the starting we room and mark the room with the paint as visited we then go down the an incident hallway into the next room. We mark that room and go to the next room always marking the rooms as visited with the paint. When we get to a dead end or a room we have already visited we follow the string back a room that has a hall way we have not gone through yet.

This graph traversal is very similar to a tree traversal, either postorder or preorder, in fact if the graph is a tree then the traversal is same. The algorithm is naturally recursive, just as the tree traversal.

Illustrate the traversal on graph example.

Algorithm

Derive a simpler pseudo-code in class.

Algorithm DFS(graph G, Vertex v)
// Recursive algorithm

for all edges e in G.incidentEdges(v) do

if edge e is unexplored then

w = G.opposite(v, e)
if vertex w is unexplored then
    label e as discovery edge
    recursively call DFS(G, w)
else
    label e a a back edge

Edges

Note that all the edge are visited in a connected graph and the edges are marked as discovery or back:

Back edges imply a cycle in the graph.
Also all the vertices are visited (in a connected graph)
And the discovery edges form a spanning-tree.

Label the edges on the example graphs.

Implementation

We need to mark or remember which vertices we have visited.

We can remember the vertices using a container to collect the visited vertices in a Hash Table. The DFS algorithm creates a Container, for example a hash table, to list all the visited vertices and edges. When the search comes to a vertex the container must be searched to determine if the vertex has been visited. Then the corresponding edge can be put in the discovery or back edge container. Naturally we want to search the container quickly, therefore the hash table choice.

We can mark the vertices by decorating the vertices, adding an attributes to vertices and edges.

Decoration:

interface DecoratedVertex extends Vertex{
public void setVisited();
public boolean isVisited;
}

Cost

Assuming that determining and setting visited in constant time then time cost of the traversal is O(n+m)
additional space is O(n+m) for decoration, so in effect not much larger then what is required for the graph

Use

The DFS can:

Testing for connectivity
Finding a Spanning Tree
Finding Paths
Finding a cycle

in O(n+m) time cost.

Iterative DFS Algorithm

The iterative algorithm uses a stack to replace the recursive calls

iterative DFS(Vertex v)
    mark v visited
    make an empty Stack S
    push all vertices adjacent to v onto S
    while S is not empty do
        Vertex w is pop off S
        for all Vertex u adjacent to w do
            if u is not visited then
                mark u visited
                push u onto S