How can I use DFS algorithm for an implicit graph?

Question

I have to find out if there is a path between s and t in an implicit graph, i.e. a graph with an unknown number of vertices, defined only by a function NEXT(v) that returns the list of vertices adjacent to v. Vertices are identified with the natural numbers. With a normal representation of the graph (adjacency lists) i would use this kind of DFS algorithm (in pseudocode):

DFS(G: Graph, s: Natural, t: Natural) : Boolean

    for v = 0 to G.adj.length - 1 do
        G.marked[v] = WHITE
    VISIT(G, s)
    if (G.marked[t] = WHITE) then return FALSE
    else return TRUE


VISIT(G: Graph, v: Natural)

    G.marked[v]  = GREY
    for each w : G.adj[v]
        if (G.marked[w] = WHITE)
            VISIT(G, w)
    G.marked[v] = BLACK

With the implicit graph the function NEXT(v) substitutes the array G.adj[v], given that both return the same thing. My problem is: how to color white at the beginning all vertices if I don't know their total number? And then, if I discover a vertice with a number greater than the marked capacity, I cannot mark it. If I use a list instead of an array then I cannot check if (G.marked[w] = WHITE) without a search in the list (that is a waste of time).

Answer 1

Use hash two sets, one for grey nodes, one for black noes. If a node is in neither, it is white. Pseudocode:

grey_nodes = new hash_set()
black_nodes = new hash_set()

if !grey_nodes.contains(v) and !black_nodes.contains(v)
    // do white stuff
else if grey_nodes.contains(v)
    // do grey stuff
else
    // do black stuff

Now whenever you color a node grey, put it into grey_nodes, and when you color it black, take it out of grey_nodes and put it into black_nodes.

Here a better version with one fewer contains() calls:

grey_nodes = new hash_set()
black_nodes = new hash_set()

if grey_nodes.contains(v)
    // do grey stuff
else if black_nodes.contains(v)
    // do black stuff
else
    // do white stuff