Cycle in Undirected Graph Graph Algorithm

Cycle in Undirected Graph Graph Algorithm


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.

46 thoughts to “Cycle in Undirected Graph Graph Algorithm”

  1. Awesome explanation and a nice way to find if a given undirected graph is a tree or not.Try this http://www.spoj.com/problems/PT07Y/ .

  2. Hi Tushar,Thanks for the video.
    I wanted to ask if you know any algorithm other than DFS to find the longest cycle in undirected graph? I dont want to use DFS as it is very slow for bigger graph.

  3. Can you make a video about cycles in directed graphs? I think directed is a bit more complex and it'd be nice to see a video on that

  4. In the code that you posted for finding a cycle using DFS, you have 2 methods, hasCycleDFS() and hasCycleDFSUtil(). Why do you have to initiate hasCycleDFSUtil() on every vertex in the graph? If we just pick any vertex and run hasCycleDFSUtil(), surely that is enough to figure out if there is a cycle or not?

  5. Do you have the Pseudo-Code for Detecting cycle in Uncorrected graph in BFS algorithm or DFS algorithm and the running time O( m + n )

  6. Great job! Thanks for taking out time and making all of these videos. These are really helpful and very well communicated.

  7. Hi, thanks for your video. Could you please clarify 1 question?

    why can't we replace lines#62-65 here https://github.com/mission-peace/interview/blob/master/src/com/interview/graph/CycleUndirectedGraph.java#L62

    with a simple return hasCycleDFSUtil(adj,visited,vertex);

    Would appreciate your help. Thanks.

  8. i cant understand how the time complexity turn out to be O(V) when find() and union() operations have time complexity of O(log(V)) and number of both of these operations are O(V) in the worst case.

  9. As the first step of detecting a cycle in an undirected graph, why can't we just say that a cycle exists in the graph if the number of edges in the graph are V or above? Since it's an undirected graph, if the number of edges are >=V, wouldn't that result in a cycle?

    If the number of edges < V, a cycle is still possible and then we could go for the Union Find algorithm. Correct me if I'm wrong.

  10. Hi Tushar ,
    I have an another algorithm for this tell me if I'm wrong,

    Firstly we have the hashTable.Here the sense of hashTable is to keep track of visited nodes.Go for DFS or BFS in that traversal we use to check if the element is in the hasTable or not if we found the element is in the hashTable then we got a cycle.

  11. all of your code are in java which are difficult to understand for beginner. if you translate this into c++ then it will be easy

  12. Hi Tushar,

    Thanks for the great video ! Can i get the nodes which are participating in the cycle from this algorithm ? .what i feel is I have to run union find for every node…pls share your thoughts

  13. Hi Tushar,
    Nice explanation. With some help from google I came up with following code to detect cycle in undirected graph using modified DFS. Though I have conceptual clarity but I am failing to understand what does 'else if (temp->dest != parent)' do (marked with ## in code below)?

    bool hasCycleDFSUtil(int v, bool visited[], int parent, struct Graph* graph)
    {
    visited[v] = true;
    struct AdjListNode* temp=graph->array[v].head;
    while(temp!=NULL)
    {
    if(visited[temp->dest] == false)
    {
    if(hasCycleDFSUtil(temp->dest, visited, v, graph))
    return true;
    }
    else if (temp->dest != parent) // ##
    return true;
    temp=temp->next;
    }
    return false;
    }

    Please help.

  14. Hey Tushar, is it possible to also use the DFS method for directed graphs here? Since Undirected graphs are just a special case of directed graph which edges in both directions.

  15. Hi, Tushar. I have a question in your DFS explanation. You said you're passing the parent so that you know you don't have to go in that direction again. This makes sense, but what if there is another edge from the parent to the same child? In this case, this is a genuine loop. In the diagram below, A-B is itself a genuine loop, so if you pass parent A while exploring B, you will not detect it.

    Eg:
    __
    | |
    A —- B —– C
    | | |
    F E——D

  16. Hi , why can't we create nodes with structure
    Struct node
    {
    Int value, visit;
    struct node * next;
    };

  17. Perhaps this sounds naive, but couldn't we just count the number of edges in our undirected graph? If length(E) > |V|-1, then not only is the graph connected, but a cycle also exists.

Leave a Reply

Your email address will not be published. Required fields are marked *