Cyclic directed and undirected graphs

0
votes

How to detect cycles in a

  1. directed graph
  2. undirected graph.

For an undirected graph .. one of the algorithms which I've thought of is by using disjoint sets.

  • for each vertex v in G
    • Make-set(v)
  • for each edge e(u,v) in G taken one by one
    • if Find-set(u) == Find-set(v)
      • return true // Cycle is present
  • return false
2
algorithmgraphdirected-acyclic-graphscyclic-graph
Your approach is called union-find, and yes, it can be used to find a cycle in an undirected graph. Alternatively, just do a DFS and see whether you encountered a node before. For a directed graph, use a modified DFS that keeps track of what you looked at during the current exploration, and mark those unvisited when you roll back from the DFS. – rafalio
Possible duplicate of Cycles in an Undirected Graph and Best algorithm for detecting cycles in a directed graph. I couldn't find a nice link for disjoint set cycle detection on Stack Overflow, but that works. – Bernhard Barker
You clearly attempted to solve (part of) the problem yourself, so probably not deserving of a downvote, but, personally, I think you should always do a Google search as well before asking a question. – Bernhard Barker

2 Answers

1
votes

For the undirected one, just use a DFS: if a an edge point to an already visited vertex, there's a cycle.

For the directed one have a look at this question.

0
votes

Your approach to find the cycle in a undirected graph should be like that:

  • for each vertex v in G
    • Meke-set(v)
  • for each edge e(u,v) in G taken one by one
    • if Find-set(u) == Find-set(v)
      • return true
    • Union-set(u, v)
  • return false

For the directed graph, you should use the Tarjan's strongly connected components algorithm to get the number of strongly components in the graph. Then, you can check if the strongly connected components number is equal to the vertexes number. Since if there is a cycle in the directed graph, there are at least two vertexes in the same strongly connected components. That means the total number of the strongly connected components should be less than the number of vertexes, if the directed graph has a cycle.