|
|
|||||||||
|
|||||||||
| |||||||||
|
|
|
| |||||||||
![]() |
|
|
«
Previous Thread
|
Next Thread
»
|
Thread Tools | Search this Thread | Rate Thread | Display Modes |
|
#1
|
|||
|
|||
|
cycle detection graph
hi folks,
the "?" is how to detect a cycle in a graph. Ofcourse there is this time-tested method of using DFS. I figured a way out by determining the indegree of every vertex in the graph. if there is a cycle , at 1 stage of the algorithm , there will be no vertex of in-degree 0. which wud mean there is a cycle My question is, is there a better way to detect the cycle? |
|
#2
|
||||
|
||||
|
Your way have O(n) as complexity indicator, it's not so bad!
|
|
#3
|
|||
|
|||
|
I'm not shure this is correct,
consider the graph A->B , B->C, C->B Then A's indegree is 0, the cycle is between B and C |
![]() |
| Viewing: Dev Shed Forums > Programming Languages - More > Software Design > cycle detection graph |
| Thread Tools | Search this Thread |
| Display Modes | Rate This Thread |
|
|
|
|