求解 log space 中无向图中的循环？

Question

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

设置

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

我的解决方案

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

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

对于V中的每个v_i，对于Neighbor(v_i)中的每个v_j，存储当前的v_i和v_j
遍历边(v_i,v_j)然后使用DFS跟随所有可能的路径通过G。
如果我们在Neighbor(v_i)/{v_j}中遇到v_k这样就有一条边(v_i,v_k) 在 E 中，然后接受。否则拒绝。"

首先我们声明M决定UCYLE。首先，如果 $G$ 中存在循环，则它必须在某个顶点 $v_i$ 开始和结束，$M$ 的第一步会尝试所有这样的 $v_i$，因此必须找到所需的顶点。接下来，假设循环从 $v_i$ 开始，那么必须存在起始边 $(v_i,v_j)$ 这样如果我们沿着循环，我们回到 $ v_i$ 通过不同的边 $(v_k,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)$ space 中的图形执行 DFS。例如，在每个顶点的度数为 $n$ 的最坏情况下，您必须保留一个计数器，记录您在特定路径上采用的顶点，这将需要 $n log(n)$ space。

Answer 1

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

下一个状态是：(v_i, v_j, current, v) 其中 v 是 [=14= 的下一个邻居] 在 prev 之后（如果 prev 是 current 的最后一个邻居，则返回到第一个）。

当 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) space，但需要一些证据来证明该算法终止。

求解 log space 中无向图中的循环？

Solving cycle in undirected graph in log space?

algorithm

graph

cycle