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.

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/ .

Thank you sir for posting this video..!

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.

thank you very much,can you explain about dijikstra's algorithm please

nice explanation!!!!!!

but how to find all cycles that exist in graph….

Hi tushar i need pseudo code for dfs for find in cycle in undirected graph

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

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?

pls do a video of directed graphs also thnx in advance

great explaining

thank you

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 )

Great job! Thanks for sharing!

Impressive…!!

So well communicated that the concept looks sooo simple and clear.

Thanks Man.

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

Appreciable. Simple and understandable teaching.

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.

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.

Will this work if we have single node loop??

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.

09:22 Where is the class DisjointSet defined? Is this a standard java class? Or was it created somewhere?

Very good! I love your explanation.

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.

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

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

Thanks Tushar. well explained. Do I have always to use disjoint set to solve this problem?

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.

Nice work big man… u convey tricky concepts with ease and clarity.. thnx alot 😉

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.

Thanks a lot for your videos Tushar. Have a Merry Christmas!

in ur video there is problem in loading

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

Great clear and brief explanation. Thank you.

You evaluated time complexity, have you considered operation findset's and union's time ?

sir, which mathematics are require for algoritm designer

if u uploaded the next lesson for me sir….plz

"yes, i contain a cycle."

-that graph

Hi , why can't we create nodes with structure

Struct node

{

Int value, visit;

struct node * next;

};

Plain and simple:)

https://github.com/golumall/Graph/blob/master/Detect%20Loop%20In%20Undirected%20Graph.java

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.

Is it possible to implement this algorithm with BFS as well?

Very good explanation!Even fool can understand

Great Weedeo!

Great Job Tushar . Very clear and crisp

I owe Tushar my Job !! Awesome.Thanks

your way of explaining concepts is amazing