我可以只使用一个简单的 Set 在有向图中进行循环检测吗？

Question

我看过相当多的算法来做循环检测，比如Tarjan's strongly connected components algorithm answered in Best algorithm for detecting cycles in a directed graph.

我从没想过检测循环会这么复杂，我一直相信一个简单的 Set 可以帮助解决问题。

所以除了通常的 marker 数组来记录访问过的顶点，我们可以使用额外的 Set 来记录从源开始的路径上的所有顶点。

关键是要记住在完成所有下一个邻居后从集合中删除一个顶点。

一个简单的代码是这样的：

public boolean hasCycle(List<Integer>[] vs) {
  boolean[] marker = new boolean[v.length];
  Set<Integer> tracker = new HashSet<Integer>();

  for(int v = 0;v < vs.length;v++)
    if (explore(v, vs, marker, tracker)) return true;

  return false;
}

private boolean explore(int v, List<Integer>[] vs, boolean[] marker, Set<Integer> tracker) {
  if (tracker.contains(v)) return true;
  else if (!marker[v]) {
    marker[v] = true;
    tracker.add(v); // add current vertex to tracker
    for (int u:vs[v]) if (explore(v, vs, marker, tracker)) return true;
    tracker.remove(v); // remove the vertex from tracker, as it is fully done.
  }
  else return false;
}

这个算法有什么问题吗？

在sasha的回答下，其实连set都不需要，数组就够了。

public boolean hasCycle(List<Integer>[] vs) {
  boolean[] marker = new boolean[v.length];
  boolean[] onPath = new boolean[v.length];

  for(int v = 0;v < vs.length;v++)
    if (explore(v, vs, marker, onPath)) return true;

  return false;
}

private boolean explore(int v, List<Integer>[] vs, boolean[] marker, boolean[] onPath) {
  if (onPath[v]) return true;
  else if (!marker[v]) {
    marker[v] = true;
    onPath[v] = true; // add current vertex to the path
    for (int u:vs[v]) if (explore(v, vs, marker, onPath)) return true;
    onPath[v] = false; // remove the vertex from the path, as it is fully done.
  }
  else return false;
}

Answer 1

我不是 java 方面的专家，但在递归中谈论 C++ 传递集合等并不节省时间。还设置了 inserting/deleting 中的 O(log(n)) 元素。你的逻辑在我看来是正确的。但是，通过保留两个数组 parent[] 和 visited[]，您可以更高效、更轻松地完成此操作。基本上做一个 bfs，下面是伪代码（visited 初始化为全零）。

   /* There are n nodes from 0 to n-1 */
   visited[0]=1
   parent[0]=0
   flag=0
   queue.push(0)
   while the queue is not empty
       top = queue.front()
       queue.pop()
       for all neighbors x of top
           if not visited[top]
              visited[x]=1
              parent[x]=top
              queue.push(x)
           else if visited[x] is 1 and parent[top] is not x
                flag = 1

   if flag is 1 cycle is there otherwise not

因为可能没有必要从 0 开始访问所有节点。如此重复，直到访问完所有节点。复杂度 O(E+V) 比您方法的复杂度 O(E+VlogV) 略好。但是写起来简单，不递归。

我可以只使用一个简单的 Set 在有向图中进行循环检测吗？

Can I use just a simple Set for cycle detection in directed graph?

algorithm

graph

data-structures