Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Finding a cycle in an undirected graph vs finding one in a directed graph

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.

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

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?

like image 518
gooser Avatar asked Jun 10 '12 20:06

gooser


People also ask

How cycle detection is different in directed and undirected graphs?

The situation of detecting a cycle in an undirected graph is similar to directed graph, but for an undirected graph, we need one more condition: parent. If the adjacent node is not a parent and already visited then it is a cycle.

What is the difference between the directed graph and undirected graph?

Undirected graphs have edges that do not have a direction. The edges indicate a two-way relationship, in that each edge can be traversed in both directions. This figure shows a simple undirected graph with three nodes and three edges. Directed graphs have edges with direction.

How can we detect the cycle in an undirected graph?

Approach: Run a DFS from every unvisited node. Depth First Traversal can be used to detect a cycle in a Graph. DFS for a connected graph produces a tree. There is a cycle in a graph only if there is a back edge present in the graph.

Can there be a cycle in an undirected graph?

An undirected graph is acyclic (i.e., a forest) if a DFS yields no back edges. Since back edges are those edges ( u , v ) connecting a vertex u to an ancestor v in a depth-first tree, so no back edges means there are only tree edges, so there is no cycle.


1 Answers

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

like image 145
Reinstate Monica Avatar answered Nov 19 '22 12:11

Reinstate Monica