所以，我读罗伯特·塞奇威克的算法第4版。书和方法用于查找一个循环有向图比所述一个查找周期在无向图中不同的

So I'm reading Robert Sedgewick's Algorithms 4th ed. book and the methods for finding a cycle in a directed graph is different than the one for finding a cycle in an undirected graph.

下面是例子code找到一个无向图中的循环

Here is example code to find a Cycle in an undirected graph

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;
   }
}

然而，试图找到一个循环有向图时，塞奇威克使用Boolean阵列，其中该数组的第i个元素是真实的，如果第i个顶点有当前调用堆栈中被审查。对于每一个顶点ķ检查，我们检查是否布尔数组的第k个元素是真实的。如果是，则我们有一个周期。我的问题是，为什么有必要使用布尔数组有向图。如果不是我刚刚上市的办法是更多的内存效率？而没有这种方法仅适用于无向图的工作？为什么？

However, when trying to find a cycle in a directed graph, Sedgewick uses a boolean array where the ith element of that array is true if the ith vertex has been examined during the current call stack. For every vertex K examined, we check to see if the Kth element of the boolean array is true. If it is, then we have a cycle. My question is, why is it necessary to use that boolean array for a directed graph. Shouldn't the approach I just listed be more memory-efficient? And does this approach only work for undirected graphs? why?

推荐答案

您不能使用相同的算法：上面的算法简单地探讨了图的所有连接的组件。如果你遇到一个已标记的顶点，必须有两条不同的路径，以实现它，并在无向图必须有一个周期。如果没有，你可以继续下一个连接的组件 - 无需清理你刚刚完成了组件

You can't use the same algorithm: The algorithm above simply explores all connected components of the graph. If you encounter an already marked vertex, there must be two different paths to reach it, and in an undirected graph there must be a cycle. If not, you can continue with the next connected component - no need to clean up the component you just finished.

在另一方面，如果你有一个向图，两个不同的路径，以同样的顶点不作循环。所以，你需要一个不同的算法（例如，您可能需要清理任何步骤，你回正轨。）

On the other hand, if you have a directed graph, two different paths to the same vertex don't make a cycle. So you need a different algorithm (for example, you may need to clean up any steps you back track.)