Interview Questions

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