algorithm - 解决日志空间中无向图中的循环？

Question

一个稍微更理论化的问题，但仍然在这里。

设置

让: UCYLE = { : G 是一个包含简单循环的无向图}。

我的解决方案

我们通过构建算法 M 来证明 UCYLE 在 L 中，该算法使用 $L$ 空间来决定 UCYLE。

M = "在 G = (V,E) 的输入上

1. 对于V中的每个v_i，对于Neighbor(v_i)中的每个v_j，存储当前的v_i和v_j

2. 遍历边 (v_i,v_j)，然后使用 DFS 遵循通过 G 的所有可能路径。

3. 如果我们在 Neighbor(v_i)/{v_j} 中遇到 v_k 使得 E 中有一条边 (v_i,v_k)，则接受。否则拒绝。”

首先我们声明 M 决定 UCYLE。首先，如果在 $G$ 中存在一个循环，那么它必须在某个顶点 $v_i$ 开始和结束，$M$ 的第一步会尝试所有这样的 $v_i$，因此必须找到所需的顶点。接下来，假设循环从 $v_i$ 开始，那么必须存在起始边 $(v_i,v_j)$ 这样如果我们沿着循环，我们通过不同的边 $(v_k,v_i) 回到 $v_i$ $，所以我们在第三步接受。由于图是无向的，我们总是可以通过 $(v_i,v_j)$ 回到 $v_i$，但是 $M$ 不接受这种情况。通过构造，如果我们在 Neighbor(v_i)/{v_j}$ 中遇到一些 $v_k，$M$ 也不会接受，但是从 $v_k$ 到 $v_i$ 没有边。

现在我们证明 M 在 L 中。首先，如果顶点标记为 $1,\ldots,n$，其中 $|\mathbb V| = n$，那么它需要 $log(n)$ 位来指定每个 $v_i$。接下来注意在$\mathcal M$中我们只需要跟踪当前的$v_i$和$v_j$，所以M是$2 log(n) = O(log n)，这在L中

我的问题

我的问题是如何在 $log(n)$ 空间中对图执行 DFS。例如，在每个顶点的度数为 $n$ 的最坏情况下，您必须保留一个计数器，记录您在特定路径上采用的顶点，这将需要 $n log(n)$ 空间。

Answer 1

搜索时保持的状态是四个顶点:(v_i, v_j, prev, current ).

下一个状态是:(v_i, v_j, current, v) 其中v 是 current 的下一个邻居 prev 之后(如果 prev 是 的数字上最后一个邻居，则返回到第一个当前)。

当 current 是 v_i 的邻居时停止，如果不是 v_j 则拒绝。

在伪代码中，是这样的:

for v_i in vertices
    for v_j in neighbours(v_i)
        current, prev = v_j, v_i
        repeat
            idx = neighbours(current).index(v_j)
            idx = (idx + 1) % len(neighbours(current))
            current, prev = neighbours(current)[idx], current
        until current adjacent to v_i
        if current != v_j 
            return FOUND_A_CYCLE
return NO_CYCLES_EXIST

直觉上，这是说对于迷宫中的每个点，以及从该点开始的每条走廊，沿着左边的墙走，如果你能再次看到起点，如果它不通过原来的走廊，那么你'我们找到了一个循环。

虽然很容易看出该算法使用 O(log n) 空间，但有必要证明该算法终止。