Cycle in Undirected Graph Graph Algorithm

Cycle in undirected graph using DFS and disjoint sets.
/ tusharroy25
github.com/mission-peace/inte...
github.com/mission-peace/inte...

[@fatihsonmez]

"yes, i contain a cycle." -that graph

[@vaibskinikar]

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

[@kapilsharma4434]

5:23 where DFS starts

[@johnbaker7102]

doesn't matter for a connected graph, pick any vertex

[@AkshayKumar-fo3dw]

@@johnbaker7102 bro you misunderstood 🤣

[@shritishaw7510]

that smile right at the start has made my day. Beautifully explained. Thank you

[@AnandPandeyHere]

Your videos are really helpful. Keep uploading more such videos on graphs.

[@XeCloudeX]

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

[@pawankoranga9332]

your way of explaining concepts is amazing

[@aprasad865]

Great Job Tushar . Very clear and crisp

[@vyshnavramesh9305]

7:48 to 8:10 summary of dfs approach to detect cycle in an undirected graph

[@fredsladkey904]

Great clear and brief explanation. Thank you.

[@mclovinf852]

Very good! I love your explanation.

[@ganeshkhirwadkar4127]

Appreciable. Simple and understandable teaching.

[@DivyanshuShekhar]

Impressive...!! So well communicated that the concept looks sooo simple and clear. Thanks Man.

[@DivyanshuShekhar]

+Divyanshu Shekhar Now I have subscribed to your channel. I wish I could have done it earlier.

[@ARYANRAJ-cb4gf]

your videos help me a lot, thanks for your great contribution.

[@Official-tk3nc]

If you are watching this in lockdown believe me you are one of the rarest species on the earth who are willing to acheive something in life. Many students are wasting their time in watching netflix, webseries, playing games, watching movies, ludo, chatting , etc.

[@jeevanraajan3238]

I owe Tushar my Job !! Awesome.Thanks

[@KUSHUTRIVEDI]

Thank you sir for posting this video..!

[@darciogmail]

Great job! Thanks for sharing!

[@AndrewMelnychuk0seen]

This is excellent, thank you!

[@202Aziz]

great explaining thank you

[@shando_tube]

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

[@nilanjanroy8023]

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

[@dheerajpatni9810]

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.

[@user-jl2tz3rq9f]

Very good explanation!Even fool can understand

[@OsafMalik]

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.

[@TheBugWhisperer1]

Find() and Union() is not log(n) , it is O(α (n)). In fact it grows so slowly, that it doesn't exceed 4 for all reasonable n (approximately n

[@kamalsmusic]

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

[@SriramGopalGoli030792]

Shouldn't the same algo work for directed graphs as well?

[@obinnaubah9045]

@@SriramGopalGoli030792 I believe it should.

[@YogeshDarji99]

@@SriramGopalGoli030792 This algo is considering all the edges, I believe in directed graphs, you will have to keep track of correct representative because of directions, this algo would require slight modification

[@SriramGopalGoli030792]

This algo does not work for directed graphs. A simple example below. 1 -> [2,3] 2 -> [3] 3 -> []

[@lkez2]

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.

[@sidharthanrajendran1387]

Plain and simple:)

[@202Aziz]

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 )

[@lpatrasco]

Great Weedeo!

[@talaviss123]

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

[@chamanjhinga3946]

Disjoint set is one way to detect cycle. DFS and topological sort are other ways to detect cycle.

[@ZiadxKabakibi]

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

[@Ronakrktanna]

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.

[@shando_tube]

I had the same thought.

[@shashankprashar1724]

@@shando_tube yes tht is true but tht doesnt mean that less than V wud give no cycle coz may be all nodes mgt not be connected and others might be connected giving cycle in a sub graph formed ex: build graph from edges 0 1 2 3 3 4 4 2 5 nodes 4 edges still cycle exist.

[@ShreyanGoswami]

Thanks for the video. It really helped. The concept of disjoint sets make it easy to find a cycle in the graph. I do have one question though. I have seen different ways that are used to represent the graph. In particular the adjacency list technique. In that if there is an edge between node 0 and node 1 then the adjacency list will have a pointer from node 0 to node 1 as well as from node 1 to node 0. If we apply the algorithm to such a ds it will say that there is a cycle. Even in the matrix representation form I see this as an issue. I am trying to figure out if there is a way to resolve this.

[@GurpreetSingh-nt2os]

You can check his GitHub link in the description section.he had implemented an amazing class for representation of graph . Hope it helps

[@anshulmishra5633]

Nice work big man... u convey tricky concepts with ease and clarity.. thnx alot ;)

[@kartikv3254]

Will this work if we have single node loop??

[@varun__1553]

how you are going to apply topological sort on undirected graph for finding cycle..0:30 ???

[@abhilakshsharma1275]

yeah I also was thinking the same. I guess he mistakenly have said that since topological sorting is applicable only to Directed Acyclic Graph (DAG).

[@mousagang2477]

can I implement the first algorithm with union-find by size and path compression and say that the time complexity is O(n * log_star(n) ) where n is the number of edges ??

[@11m0]

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

[@achilles1.0]

He created it separately. There's also a video on it where he explains the code, you might want to check that out. github.com/mission-peace/interview/blob/master/src/com/interview/graph/DisjointSet.java

[@pusarlaaishwarya5035]

Sir...which books are preferred to enhance more knowledge on this concepts

[@namansingh8648]

Can we use white gray black method in undirected graph too???

[@arijitjash9375]

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

[@kamalsmusic]

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?

[@kamalsmusic]

Ah ok. So in that case, since you have to execute multiple depth first searches, would the runtime be O(|V|(|E|+|V|))? And so, if the graph is connected, starting at any one vertex is sufficient, right?

[@kamalsmusic]

Wait a second, isnt the runtime still O(|V|+|E|)? We still explore every vertex only once since we keep track of the ones we've visited early.. I think I analyzed it wrong. Can you confirm that the runtime is O(|E|+|V|)?

[@SharifKhanitexpart]

sir, which mathematics are require for algoritm designer

[@ajishgoku875]

discrete mathematics

[@vivekr5321]

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

[@treyquattro]

Eventually the DFS will return to the second edge A-B and if the B-C-D-E cycle hadn't been detected, the A-B-A would be. B would be already in the visited set.

[@MrCnareshkumar]

In a directed graph, there exists one path at the maximum from one node to other

[@shando_tube]

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.

[@ultra_max_pro]

This is clearly not true. Consider the graph with two connected components, one is an isolated vertex, and the other is k_4, (complete graph with 4 vertices, 6 edges). Then the inequality you mention holds, but the graph is not connected. Also, if the graph has, say 100 isolated vertices and one cycle with 3 vertices, the equality does not hold, but the graph has a cycle. Basically, you don't know about how the graph is connected.

[@shando_tube]

@@ultra_max_pro yea u know what man, I'm just happy I passed the class

[@surendrapalSingh]

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.

[@puneetkumar-vv9go]

because in the adjacent list of V node, there should be not any other node visited except its parent(because v derived from its parent). if it is , then there is cycle

[@vishwanath501]

nice explanation!!!!!! but how to find all cycles that exist in graph....

[@parasmishra5461]

pls do a video of directed graphs also thnx in advance

[@anandpandey2917]

kzbin.info/www/bejne/lZS2ZI13rp1od7M

[@gauraonandekar5820]

Graaaafffffffff

[@pritamsarkar3371]

is not "for(Edge edge: graph.getAllEdges())" taking O(E) times ?

[@sasipotu9833]

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

[@sasipotu9833]

I need using dfs..not disjoints

[@sasipotu9833]

Thank you..

[@ashirbadbehera5544]

thaak about....

[@Pariharyash]

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

[@overclockinggames2419]

O(1)

[@ankushvirmani9039]

in ur video there is problem in loading

[@dibyendubrinto3051]

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