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|)。