Find a cycle in a directed graph
Software QA/Tests Interview Questions from Microsoft
(Continued from previous question...)
Find a cycle in a directed graph
Question:
find a cycle in a directed graph
maybe an answer:
You need to unmark a vertex after recursion so no false cycles are reported. For instance if your graph looks like this:
a > b > c
> d /
If you don't unmark vertex C after recursion ends there from b, then it will report c involved in a cycle which is incorrect. However if your graph looks like this:
a>b>c>d>a
Then clearly from d you will visit a and find the cycle !
(Continued on next question...)
Other Interview Questions
