CODEWITHSUNDEEP
algorithmgraphdirected-acyclic-graphscyclic-graph
user3533144
user3533144

Reputation: 1

Cyclic directed and undirected graphs

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.

Upvotes: 0

Views: 1434

Answers (2)

Ricky Ye
Ricky Ye

Reputation: 1

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.

Upvotes: 0

MarcoL
MarcoL

Reputation: 9989

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.

Upvotes: 1

Related Questions