CODEWITHSUNDEEP
algorithmmathgraph-theoryundirected-graphcycle-detection
Mashrur Kabir Riyan
Mashrur Kabir Riyan

Reputation: 19

Cycle Detection in Undirected Graph

The graph in question

I have this undirected and weighted graph in the above link and I just cannot detect how many cycles are there. I have tried BFS, DFS and Set disjoint method but all of them just goes wrong somewhere while calculating. I can do the code. The problem arises when I try to do it in pen and paper. Is there any algorithm/method by which I can efficiently calculate the no. of cycles?

I have tried BFS, DFS and Set Disjoint methods.

Upvotes: 1

Views: 174

Answers (1)

Dimava
Dimava

Reputation: 10899

To do that, you first need to determine what the "amount of cycles" is.
If I unterstand correctly, that is "amount of different cycles in the graph"

Then you need to define what's "different cycles" is.
Cycles are different if their normalized form is different.
The normalized form I choose is "starts with the lowest node, second node is lesser then last"
e.g. ABDJ is the normalized form for ABDJ, ABJD, BJDA and BADJ

Then all you need is the size of set of unique normalized cycle paths

The optimized algorithm would be DFS with disabling the first node after all cycles through this node were already found. This also forces each cycle to appear exactly twice (in two directions). This redeces the difficulty from O(N!) to O( (N-1)! )

Upvotes: 0

Related Questions