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 completeA 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 ;;; ;;;

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