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).