hello friends my name is Tushar and today i'm going to talk about how to detect a
cycle in a directed graph. In another video, I talked about how to detect a
cycle in undirected graph. Today, we're going to talk about directed graph. So
the idea is to use a depth first search.
While doing a depth first search, we're going to maintain three sets: a white set, a
gray set and a black set. White set has all the vertices which have not been
visited at all
Gray set has all the vertices which are being visited right now and black set
has all the vertices which have totally been visited meaning that all its
children have also been visited.
so while doing depth first search, if we encounter a vertex in a gray set, it means
that we found a cycle.
Why? because when a vertex is in gray set,
it means that its neighbors, or its neighbor's neighbors or somebody in that
hierarchy is still being explored and that vertex found a path back to the
vertex in the gray set, indicating that there's a presence of a cycle.
So next let's try to apply this algorithm on this graph here.
So first thing we do is we put all the vertices in this white set here, then
we're going to continue to do depth first search till either we find a cycle in this
graph or we have moved all the verttices from white set to black set. if
all the vertices have been moved to black set, it means that there is no cycle in
this graph. So let's start from any random vertex, so let's say we start
from vertex 1, so first thing we do is, we move this vertex to gray set and
also in this DFS map, i am going to indicate that one got introduced by null
because there is no parent of one because one is a start point. Then we're going to
to explore neighbors of one. So one neighbor of one is two. Two is not there in the black
set
Two is not there in the gray set
but two is in the white set so then we're going to take two out of the white
set and then add it into the gray set because now we're going to explore two and
also indicate here that two got introduced by one. So now we're going to
explore neighbors of two. One neighbor of two is three. Three is not in the black set. It means
that it's not visited. Three is not in the gray set, so there's no cycle yet
but three is in the white set, so again we're going to move three from white set to
gray set, indicate that three got introduced by Two and explore neighbors of
three. Three has no more neighbors it means that three is totally explored.
which means that we can move three from gray set to black set.
remember black set has all the vertices which are totally visited.
now we're going to go back from three to two and explore other neighbors of two but
has two more neighbors to be explored.
so we're going to move two from gray set to black set and go back to one. One has one
more neighbor three to be explored but three is already in the Black set. It means that
there is no reason to visit three again
so one doesn't viist three and at this point
one has no more neighbors to be explored so we'll move one to black set. Now at this
point we are done doing the DFS starting with one so we have to go back to the
to the white set and see that white set is still not empty
so pick another random vertex in the white set. So let's say you picked four
and now we're able to do our DFS around four, so we're going to move four from
white set to gray set
so now we'll explore neighbors of four.
so first we're going to say that four got introduced by null because in DFS
four doesn't have a parent
so one neighbor of four is one but one is already in the black set. So we're not
going to explore one again
so we're going to explore other neighbor of four. So another neighbor of four is five
so five is not in the black set, five is not in the gray set but five is in the
white set.
so again we're going to move five to gray set because now we'll explore five and here i am
going to say that five got introduced by four. Now
one neighbor of five is six. Six is not in black set, six is not in gray set, six is in white set
so we're going to move six from white set to gray set and say that
six got introduced by five and now we're going to explore neighbors of six. One neighbor
of six is four. Four is not in the black set but four is in gray set
it means that we found a cycle in this graph. So to figure out that what is
that cycle, we can retrace our steps back.
So we know that 6 5 4, so edge 64 is in the cycle then we go to six and see who
introduced six. So six got introduced by five, so edge 56 is in the cycle and then
we're going to check who introduced five and five was introduced by four so edge
45 is in the cycle and four is the point at which we stopped, so this here is
indicating our cycle. Four to five, five to six and six back to four. So now for
suppose that we did not have this edge 64
if we did not have this edge 64, in that case
what would happen was that six would have no more neighbors to be explored, so we
would move six here and then five would have no neighbors to be explored, so we move five to
black set and then four would have no neighbors to be explored, so we would move four
to black set and in that case we will not find any cycle. So if this edge six to four
does not exist
this graph should return false because there is no cycle and if this edge 64
exists then this graph has a cycle and it should return true.
The time complexity for this algorithm is O(E+V) and the space complexity
is O(V). So next let's look at the code for this algorithm.
main function here is hasCycle, it takes in a graph. First thing we do is
we initialize whiteSet, graySet and blackSet. Then we're going to add all
the vertices to white set. So white set here has all the five vertices.
then while the whiteSet size is greater than zero, it is greater than zero
we are going to take any random vertex from the whiteSet, so let's say we got
one.
So in DFS now we're going to go into DFS with current as one and passing
whiteSet, graySet and blackSet.
So in the DFS first thing we do is we move the current which is one from
whiteSet to graySet because now we're going to explore one. You're
going to get neighbors of one so. one neighbor of one is two. So two is not in the black
set so first thing we check is two in the blackSet and it's not which
means that two can be explored
Two is not in the graySet which means that we haven't found a cycle
yet.
Then we're going to go into the DFS and check and explore two.
So again we go into the recursion, this with value neighbor and neighbor is two
so we come back to the top here
so first thing again we do is we move two from whiteSet to graySet, then we're
going to explore neighbors of two. So two has no neighbors
so what we're going to do is we're done exploring two. So we're going to move two
from graySet to blackSet.
so two moves to black set and then we're going to return false
so when we go back in recursion, we reach to the point here where we went to the
recursion to the two and now the current is one
so if DFS, so since we got false from two
it means that there is no cycle with two involved so we're going to go back
to the top of the for loop and again current here is one and now one has no more
neighbors to be explored
so we come out of the for loop and we're going to move one from graySet to blackSet
and one is also going to return false.
so this returns false to this DFS here.
So again since this is false, so we don't go into this if condition and
then we're going to go back to the top of this while loop. Now the
whiteSet still has three more elements to go
so again we're going to randomly pick another element. let's say we picked four
so then our current becomes four and we're again going to go into
the DFS with four and see if we can find cycle with four as a starting point.
so here first thing we do is we move four from whiteSet to graySet
so here four moved from white to gray and then we're going to explore neighbors of four
one neighbor of four is one, so we come to this if condition but one is already in
a blackSet so we do nothing about one and continue and look for another
neighbor, so another neighbor of four is five. Five is not there in the black set, five is
not there in the graySet so now we're going to explore five
and to do that, we go into the DFS. So now our current is five. So first thing to do
is move five from whiteSet to graySet.
so this is what happens and then now we're going to explore neighbors of five. So one
neighbor of five is six and six is not in blackSet, six is not in graySet so again
we're going to do a DFS with six as the current so we go back to the top of this
function. First thing we do is we move six from whiteSet to graySet
so that's what happens here and now we're going to explore neighbors of six. One
neighbor of six is four. So four is not in blackSet but four is in graySet. Four
here is in graySet which means that we found a cycle because four was being
explored. So this returns true immediately
so what this means that it returns true. so six returns true to its calling
function and six was called from five so five
we return to the point here and this is true so five returns true to its
calling function and five was called from four, so we come to this point where
current is four and this since this is true so four returns true to its
calling function which was here, so we come to this point and since this is
true
this returns true. So since this graph has a cycle it returns true saying that this
has cycle. So this is all I have to talk about this algorithm, link to this
code, Java code and Python code is in the description section of
the video. Please like this video comment on this video, check out my facebook page
and check out my github link. Thanks again for watching this video.