Hello friends my name is Tushar and today I'm going to talk about how to
find the cycle in an undirected graph. So here I have a graph and this graph
contains a cycle so this graph should say that yes I contain a cycle.
If I remove this edge here then this graph doesn't contain a cycle anymore so
it should say that I do not contain a cycle. So there are many ways to find a
cycle in an undirected graphs like using disjont sets,using DFS,using topological
sort and a few other ways.In today's video I'm going to talk about couple of
these techniques. One is using disjoint sets,another is using DFS to find a
cycle in an undirected graph.Let's first talk about how to find a cycle in an
undirected graph using disjoint sets. In another video I talked about how disjoint
sets work and if you have not watched that video ,I highly recommend
you watching that video before continuing on this video.So if you
remember disjoint set supports 3 operation makeSet,
union and findSet. Let's see how we're going to use this disjoint to find a
cycle in an undirected graph. So the idea is very simple. All you have to do is
create as many sets as,as the number of vertices you have and then you have to
pick an edge and you have to see both the ends, both the vertices of this edge
are in the same set or in different set. If they're in a different set then you
have to union those two sets together and if they're in the same set
it means that there is another edge which unioned them together so this
edge must be creating a cycle in the graph. So let's work with this example.
So first I do is I call makeSet on all this 6 vertices.
So I have A,B,C,F,E,D.
So here I have 6,I have 6 sets so then I pick any edge. So let's say I picked this
edge.
So what I'm going to do is I'm going to do a findSet on A that is going to
return me A and then I'm going to call, do a findSet
on F and that is going to return me F. At this point both A and F are not in the
same set it means that adding this edge is not going to create a cycle then what
we do is we do a union of these two sets.
So then they are together now so we'll have A,F and a union.
So they are now in the same set and let's say the set is represented by A. Now
let's pick another edge.
So let's say we picked edge ED.Again we do a findSet on E that returns me E
and then I do a findSet on D and that returns me D and again they are in the
different sets so again adding this edge is not going to create a cycle. So let's
first do and then let's do a union of these two sets.
All right let's pick another edge.
Let's say we picked edge CD. So we do a findSet on
D.Let's, let's say this set is represented by E.
So I do a findSet on D so that returns me E
and then do a findSet on C and that returns me C.
So again this set and this set is different.Again,
so adding this edge is not going to create a cycle,so let's union them,
so something like this and again we say that E represents this entire set.
So next let's pick this edge.
A is represented by A and B is represented by B.Again they are in two
different sets.
So adding this is not going to create a cycle. Let's Union these two sets.
All right let's add edge BE.So B is represented by A so findSet on B
will return A and findSet on E returns E.So A and E are in two different sets right
now. So,so again this edge is not going to create a cycle.
So what we're going to do is we're going to do a union of these two sets so we'll
have something like this and let's say E represents
my entire set.
So finally let's add this edge BC.
So what will happen is B is represented by E, when we do a findSet on B
we get E, when we, when we do a findSet on C we again get E. What that means is that
both these guys are already in the same set.
It means that there must be another way to connect B to C and that edge is not
this edge. So by adding this edge it means that you're going to create a
cycle in the graph so this edge here creates a cycle in the graph and that's
how we find out that there is a cycle in the graph using disjoint sets. In the
next section let's talk about how we find cycle in undirected graph using DFS
algorithm.So in DFS we'll keep a visited set to know which vertices we
have already visited. So we can start from any
vertex. Let's say we start from A. So first thing we do is we put A in the
visited set.
Then we explore the neighbors of A, let's say we explore F first so we go in the
direction of F and we also pass A TO F saying that I'm coming from A and
then F is going to explore its neighbors. So the first neighbor it's going to find
is A and since it's coming from,in the direction of A there is no reason to
continue in that way,direction and then F has no other neighbors.
So we also visited F and then F goes back to A and then A explores its other
neighbour which is B
and again it passes A to that neighbour. So again first thing we do is we put B
into the visited set. Then B explores its neighbours.
So the first neighbour it encounters is A and since it is already coming from A
because you passed A to b it knows that it doesn't need to go in that direction.
So then it explores another neighbour. So let's say that neighbour was C and C is not
in the visited set. It means that it can go in the direction of C. So we go
from B to C and we pass B to,we pass B to C saying that this is where
you're coming from
and we'll also put C in the visited set.C will repeat the same process. C will
explore its neighbours. So first neighbour it sees is B and it knows that it's
already coming from B so there's no reason to go in that direction.
So C explore its other neighbour which is D so we go from C to D and pass C to
it and put D in the visited set. Then D will repeat the process.
So D will not go,not go in the direction of C so D will explore
E and we'll put E in the visited set and then E will not go in the direction of
D.
So what E's going to do is,it's going to try to go in the direction of B but what
happened here is that B is already in a visited set.
What that means was there,there must be another way to reach B from E which
is this way.
So adding this particular edge is going to create a cycle in the graph. So
this is how we know that there is a cycle in the,in the undirected graph.
Remember it's an undirected graph. So all we need to do is maintain a visited set
and then we do a DFS and we pass the parent so that you know that you don't
have to explore in that direction and other than that if you find any
node which is already
if you find any vertex which is already in a visited set it means
that you found a cycle in the undirected graph. So in the next section
let's look at the
code. So let's look at the code to find cycle in undirected graph using
disjoint sets. So I have a very simple graph here and I'm going to run this,run
through this code using this graph as an example.
So first thing we do is we create an object of disjoint set. Then I iterate
through all the vertices of this graph and create that many sets. So I end up
creating like 4 sets A,B,C,D. Then I pick one edge at a time. So let's say
we picked an edge AC. So I find the representative of A,edge
1 vertex of this edge and that is A and then I find the representative 2
of the other vertices of this edge and that's C.
So A and C are not same. So what we do is we union A and C. So A and C are now together and
let's say they are represented by A.Then we go back to the top of this for loop.
Let's take another edge,say BC.
So what we do is we find the representative
Let's say v1 is B so we find representative of B and that's B and
we find representative of C and that's A. So again A and B are different.
So we don't go into this if condition, we come here and we union these two guys
together.
Let's say A continues to be the representative of this set.
Let's pick another edge, say CD. So we go back to the top of the for,for loop,we
pick edge CD,we find the representative of C, that's A and then we find the
representative 2 of D and that's D.Again we don't go into this if condition so we
union this set and this set. So we end up having something like this.
Now we go back to our top of the for loop and find edge AB.
So we find representative of A and that's A and then we find
representative of B and that's also A. So in this case representive1 is
equal to representative2.
So what we do is we instantly return true saying that there is a cycle in this
graph. So basically this, adding this edge is going to create a cycle in this graph.
Let's analyze space and time complexity. So space complexity is pretty
simple.
It's the total number of vertices so that is O(V).
Let's analyze time complexity.
So this for loop here is going to take O(V) time.
Then if you remember,if you remember from disjoint sets,if the total number
of operations are 'm' and if the total number of elements in the disjoint
sets is 'n' and if 'm' is greater than equal to 'n' the amortized time for m
operations is going to be O(m). In this case our total number of elements
in this set is going to be n which is O(V) and total number of operations is
never,is also going to be equal to V
because number of edges we need to look is at max is going to be V
because as soon as we find the Vth edge,as soon as,if the total number of
vertices are V, as soon as we explore the Vth,the Vth number of edge
what will happen is that edge is going to create a cycle in this graph. So this for
loop at max executes V times and so the total number of operations is going
to be,since you are doing findSet multiple times and union 1 so the total number of
operations is going to be three 3m. So in the worst case the time complexity
for this algorithm is going to be O(V).
The time complexity for DFS algorithm is also going to be O(V) where
V is the number of vertices and the space complexity for DFS algorithm
is going to be O(V).
So this is all I have to talk about finding cycle in an undirected graph. The
link to the code is in the description section of the video. Please like this
video,share this video,comment on this video,check out my github page and my
facebook page.
Thanks again for watching this video.