Microsoft Interview Question Software Engineer in Tests
0of 0 votesfind a cycle in a directed graph
It is possible to visit an already visited node in a graph that doesn't have cycles (think about what happens when it finds a cross or forward edge).
A graph has a cycle if a back edge is found during DFS.
Do mark the nodes, as "currently being explored" or "not currently explored". When we see an edge to a "currently being explored" node (i.e to a node currently in call stack), it is a back-edge and hence has a cycle.
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 !
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 !
Mark all nodes "unexplored" at first. Then use depth first search, mark the nodes we visited as "explored". Whenever we meet a node which has already been marked as "explored", a cycle is detected.
- tangqiyuan May 10, 2010