52.219 Depth First Search (dfs)

Just as we had the traversals for trees (pre/in/post-order) we have traversals for graphs. The first such traversal is called depth first search (dfs), and may be considered as a "skeleton" for a number of important algorithms (some of which we will visit) Depth First Search is described informally as follows:


     We have a directed graph G = (A,V) and we assume that all
     vertices have an attribute called (mark v), where (mark v) is set to
     "unvisited" for all vertices v in (V G). 

     Select some vertex of (V G), call it s, as a starting vertex and mark 
     vertex s as visited.

     Each vertex w adjacent to s that has (mark w) equal to "unvisited" is
     then searched in turn using depth first search recursively.

     Once all vertices that can be reached from s have been visited the
     search from s is complete

A scheme implementation of dfs is given in /home/s7/pat/scheme/pub/dfs.scm and contains 2 implementations of dfs, one recursive the other iterative. There is a wee demo function. The recursive implementation is reproduced below.


(define (recursive-dfs s G)
  (let ((mark (make-vector (+ 1 (n G)) #f))                          ;(1)
	(visited '()))                                               ;(2)
  (define (dfs' w)                                                   ;(3)
    (cond ((not (vector-ref mark w))                                 ;(4)
	   (vector-set! mark w #t)                                   ;(5)
	   (set! visited (cons w visited))                           ;(6)
	   (do ((unvisited (adjacent-to w G) (cdr unvisited)))       ;(7)
	       ((null? unvisited))                                   ;(8)
	     (dfs' (first unvisited))))))                            ;(9)
  (dfs' s)                                                           ;(10)
  visited))                                                          ;(11)
;;;
;;; Depth first search from starting vertex s in graph G
;;;
;;; (1) Vector element (vector-ref mark w) is #t if vertex w has been visited
;;;     otherwise (vector-ref mark w) is #f
;;; (2) visited is a list of vertices, giving the vertices in reverse 
;;;     order as visited by a dfs from vertex s in G
;;; (3) Local recursive function dfs' ... this is for cosmetics
;;;     saving us having to pass in the vector mark every call
;;; (4) If we have not already visited the vertex w ...
;;; (5) ... then set w's mark ast true ...
;;; (6) ... push w onto the set of visited vertices ...
;;; (7-9) ... then make recursive calls to dfs' from the vertices 
;;;           adjacent to w in G
;;;
;;;

Complexity of dfs
In the above implementation, on each recursive call to (dfs' w) if the vertex w has not already been visited (line 4) then the vertex w is marked as having been visited (line 5), w is then pushed on to the list of visited vertices (line 6) and we then do a depth first search, in turn, off each of the vertices adjacent to w in G (lines 7 to 9). If vertex w has been visited (ie. line 4 fails) then nothing happens. If vertex w has not been visited we then get all the vertices adjacent to w in G, and this operation takes time of order O(n). At most we can visit each of the n vertices of G once only. Consequently we perform the operation of line 7 (getting the adjacent vertices) at most n times. Therefore, the overall complexity is at worst O(n*n). In fact the complexity is of the order O(a') where a' is the number of directed arcs in G (and that is O(p.n.n) where p is the probability of an arc existing between 2 vertices).