algorithm - 检查图中的顶点是否属于循环

Question

我有一个无向图(可能有多个边)，我需要在 O(|V|) 中检查给定顶点是否属于某个循环。请注意，图形可以是密集的。

Answer 1

如果您可以走出循环并稍后通过其他顶点返回，则该顶点将属于循环。

算法可以如下:

1. 将当前顶点 V₀ 添加到已访问顶点列表 V。

2. 当 sizeof(V) < N 时，我们将列出 V₁, ..., V_k，您可以从 V_{0 转到}

3. 重复第 2 步，直到在途中找到 V₀ - 这意味着它处于循环中 - 或者直到 sizeof(V) = N 或没有新的顶点可以添加到 V (图可能断开连接)。 注意: 重复第 2 步意味着我们找到可以从最后添加的集合 (V₁, ..., V_k).

通过这个算法，我看到每个顶点只检查一次，所以它是 O(|V|)。