如何将 DFS 算法用于隐式图？

Question

我必须找出隐式图中 s 和 t 之间是否存在路径，即具有未知数量顶点的图，仅由函数 NEXT(v) 定义 return s 与 v 相邻的顶点列表。顶点用自然数标识。使用图形的正常表示（邻接列表）我会使用这种 DFS 算法（伪代码）：

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

对于隐式图，函数 NEXT(v) 替代数组 G.adj[v]，因为两者 return 是同一件事。我的问题是：如果我不知道它们的总数，如何在开始时将所有顶点着色为白色？然后，如果我发现一个顶点的数量大于 marked 容量，我就不能标记它。如果我使用列表而不是数组，那么如果不在列表中进行搜索就无法检查 if (G.marked[w] = WHITE)（那是浪费时间）。

Answer 1

使用hash两套，一套是灰节点，一套是黑节点。如果节点不在两者中，则它是白色的。伪代码：

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

现在每当你将一个节点着色为灰色时，将其放入grey_nodes，当你将其着色为黑色时，将其从grey_nodes中取出并放入black_nodes。

这是一个更好的版本，少了一个 contains() 次调用：

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

如何将 DFS 算法用于隐式图？

How can I use DFS algorithm for an implicit graph?

algorithm

graph

pseudocode

implicit

depth-first-search