|
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 un-mark 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 un-mark 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
| 