Space Optimization for Iterative Depth-First-Search (DFS)

Question

Problem

In most academic literature, the preferred DFS algorithm is always recursive, however, for large Graphs, an iterative variation using a Stack seems much more practical to me, without running any stack-overflow dangers.

It seems however somehow daunting to find an iterative implementation that correctly mimics the behaviour of the recursive one, guaranteeing a O(|V|) over the number of verteces.

I have therefore come with my own implementation, and wanted to know if it is correct, and if you would use this implementation, not only in practical applications, but also in technical interviews, when asked for a non-recursive version of DFS.

Definitions:

G(V,E): Connected graph on which the algorithm will be run, with a set V of vertices and a set E of edges.

A[1...n]: Array of adjacency lists for each vertex in graph (A[k] is the linked list containing the adjacent vertices of vertex k)

v[1...n]: Array to track visited vertices

u[1...n]: Array to track active vertices (vertices which have entered the data structure in use)

DFS Iterative without optimized Space, in O(|E|):

DFS-Iterative(A,v,i): // on vertex i
stack <- new Stack()
stack.push(i)
while not stack.empty():
    k <- stack.pop()
    if isNotVisited(v,k): // checks if v[k] = 1
        markVisited(v,k) // sets v[k] = 1
        for j in A[k]:
            if isNotVisited(v,j):
                stack.push(j)

DFS Iterative with optimized Space, in O(|V|):

The Adjacency list here is a pointer to the first element of the list. Each node of the list has two member variables 'next' and 'value'.

DFS-Iterative-Optimized(A,v,i):
stack <- new Stack()
markVisited(V,i)
stack.push(A[i])
while not stack.empty():
    curList <- stack.pop()
    if curList:
        stack.push(curList->next)
        k <- curList->value
        if isNotVisited(V,k):
            markVisited(V,k)
            stack.push(A[k])

Question

Is my implementation correct, and is this the standard iterative implementation for DFS?

Answer 1

Yes, your implementation is correct. I would just change the parameter list. V only needs to exist during the execution of the function itself; there is no need for the caller to provide it: it is much the same situation as for the stack.

Also, you could be more specific about the operations on V, and assume it to be a Set (knowing that you could implement that set with an array of booleans, or whatever other alternative):

So:

DFS-Iterative-Optimized(A, i):
    V <- new Set()  // or Array<bool>
    stack <- new Stack()
    V.add(i)
    stack.push(A[i])
    while not stack.empty():
        curList <- stack.pop()
        if curList:
            stack.push(curList->next)
            k <- curList->value
            if not V.has(k):
                V.add(k)
                stack.push(A[k])