在无向图中寻找循环与在有向图中寻找循环的区别

Question

在无向图中寻找循环与在有向图中寻找循环的区别

20

我正在阅读Robert Sedgewick的《算法》第4版，其中寻找有向图中的环的方法与寻找无向图中的环的方法不同。

下面是在无向图中查找环的示例代码：

public class Cycle {
   public boolean[] marked;
   public boolean hasCycle;

   public Cycle(Graph G) {
      marked = new boolean[G.V()]; // G.V() is the number of vertices in the graph G
      for (int s = 0; s < G.V(); ++s) {
         if (!marked[s])
            dfs(G, s, s);
      }
   }

   private void dfs(Graph G, int v, int u) {
      marked[v] = true;
      for (int w : G.adj(v)) //iterate through vertices adjacent to v
         if (!marked[w])
            dfs(G, w, v)
         else if (w != u) hasCycle= true;
   }

   public boolean hasCycle() {
      return hasCycle;
   }
}

不过，在尝试在有向图中找到一个环时，Sedgewick使用了一个布尔数组，其中该数组的第i个元素为真，如果在当前调用堆栈期间检查了第i个顶点。对于每个检查的顶点K，我们检查布尔数组的第K个元素是否为true。如果是，则表示存在一个环。我的问题是，在有向图中使用那个布尔数组是为什么必要的？我列出的方法难道不会更节省内存吗？这种方法只适用于无向图吗？为什么？

- gooser

也许他假设有一个自环在有向图中？ - xvatar

它实际上没有假设自环。我认为我刚刚发布的算法可能适用于有向图，但我不确定。 - gooser

下面的答案很有道理。 - xvatar

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Reinstate Monica · Accepted Answer

你不能使用同样的算法：以上算法仅探索图的所有连通分量。如果你遇到一个已标记的顶点，则必须有两条不同的路径到达它，在无向图中必然存在一个循环。如果没有，你可以继续下一个连通分量——没有必要清理刚完成的连通分量。

另一方面，如果你有一个有向图，到达同一个顶点的两条不同路径不构成一个循环。因此，你需要不同的算法（例如，你可能需要清理回溯的任何步骤）。