17

所以我正在阅读 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 个元素是否为真。如果是，那么我们就有了一个循环。我的问题是，为什么有必要将该布尔数组用于有向图。我刚刚列出的方法不应该更节省内存吗？这种方法是否仅适用于无向图？为什么？

4

1 回答 1

32

您不能使用相同的算法：上面的算法只是探索了图的所有连接组件。如果遇到已经标记的顶点，则必须有两条不同的路径才能到达它，并且在无向图中必须有一个循环。如果没有，您可以继续使用下一个连接的组件 - 无需清理您刚刚完成的组件。

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

于 2012-06-10T20:35:25.070 回答