tgp07's blog

Cycles in a graph
By tgp07, history, 23 months ago, In English

Let's you have a graph with n nodes and m bi-directional edges. (n, m <= 1e5). How would I get the cycles in this graph in an efficient way using DFS.

BTW, I've linked an image where I drew what I thought is a cycle. If it's not a cycle, please tell me what a cycle actually is.

https://imgur.com/a/Qrrg8DF

  • Vote: I like it
  • -4
  • Vote: I do not like it

Comments Comments (9)
| Write comment?
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by tgp07 (previous revision, new revision, compare).

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by tgp07 (previous revision, new revision, compare).

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by tgp07 (previous revision, new revision, compare).

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I can't open your link. I'm not sure what you mean 'cycle'.

But actually for a graph, there can be 2 ^ v cycles.

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by tgp07 (previous revision, new revision, compare).

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

A graph contains a cycle if during a graph traversal, we find a node whose neighbor (other than the previous node in the current path) has already been visited.

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Do you know how to go about getting the lengths of a cycle?

    → Reply
    • »
      »
      »
      23 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The length of the cycle is the difference in heights of those two nodes on the DFS tree, plus one (for the edge going back up the DFS tree)

      → Reply
      • »
        »
        »
        »
        23 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thanks, this makes sense.

        → Reply