Indian Computing Olympiad

Training Material

Basic Graph Algorithms

Depth-first search

The other option for exploring a graph is depth first. Pick an unexplored neighbour, pick one of its unexplored neighbours, &hellip, till you can go no further. Backtrack to the previous node and pick the next unexplored neighbour … 

	DFS(v){
	  mark(v);
	  for each neighbour w of v
	     if (unmarked(w))  /* w is unvisited */
	        DFS(w)
	  }
	}

For example, consider DFS from c1 on the following graph. 

            c1
           /|
         c2-+-c3
           \|/
            c4
      
  DFS(c1): mark(c1)
           DFS(c2)  : mark(c2)
                      DFS(c3)  : mark(c3)
                                 DFS(c4)  : mark(c4)
                                            all nbrs of c4 marked
                                 all nbrs of c3 marked
                      all nbrs of c2 marked
           all nbrs of c1 marked

When a vertex w is marked by DFS, we know that there is a path to w from the start vertex. How do we recover the actual path?

If we mark vertex w from v, we record that we reached w from v, e.g. by setting parent(w) = v 

        DFS(v){
          mark(v);
          for each neighbour w of v
             if (unmarked(w))  /* w is unvisited */
                parent(w) = v;
                DFS(w)
          }

Tracing back via the parent relation, we can recover a path back from any vertex to the start vertex.

DFS numbering

We can assign a DFS number to each vertex --- order in which the vertices are explored. 


        Example:                         DFS starting at a:
              b
             / \                         [1]  a
            /   \                             |
           a     c                       [2]  b
            \   / \                           |
             \ /   \                     [3]  c
              d-----e                         |
             / \    |                    [4]  d----------
            /   \   |                         |          \
           i-----j  |                    [5]  i      [7]  e
                    f                         |           |
                   / \                   [6]  j      [8]  f
                  /   \                                   |
                 g-----h                             [9]  g
                                                          |
                                                    [10]  h

The number in square brackets, the order in which the DFS visited the vertices, is the DFS number of the vertex. (This number depends on the order in which you choose edges to explore.)

The edges that are used in the DFS form a subgraph of the original graph. This subgraph is connected and has no cycles. This is called the DFS tree of the graph.

What about the edges in the original graph that do not form part of the DFS tree. For example, in this graph these edges are (a,d), (c,e), (f,h) and (d,j). 

    	  [1]    .a
    	        . |
    	  [2]   . b
    	        . |
    	  [3]   . c...........
    	        . |           .
    	  [4]    .d----------  .
    	          |.         \ .
    	  [5]     i .    [7]  e
    	          | .         |
    	  [6]     j.     [8]  f.
    	                      | .
    	                 [9]  g .
    	                  |     .
    	                [10]  h.

All these edges go up one of the paths in the DFS tree. The edges cannot cross from one branch to another --- e.g., there cannot be a non-tree edge from g to i in this DFS tree. Had there been such an edge, we would have visited i below g, before backtracking to e. Non tree edges are also called "back edges".

Some observations about DFS numbers of vertices:

  1. DFS number of any vertex is smaller than those that appear in the subtree below.
  2. DFS number of any vertex is smaller than those that appear to its "right" in the DFS tree.
We will use these facts later.

Video material

Video lecture on Depth first search, NPTEL online course on Design and Analysis of Algorithms (Lecture slides)



Basic topics

Advanced topics