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.
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
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.
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.
@@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
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.
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 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.
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.
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
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 ??
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?
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?
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|)?
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.
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.
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
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.
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.
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
"yes, i contain a cycle."
-that graph
Great job! Thanks for taking out time and making all of these videos. These are really helpful and very well communicated.
Thanks a lot for your videos Tushar. Have a Merry Christmas!
your way of explaining concepts is amazing
that smile right at the start has made my day. Beautifully explained. Thank you
Great clear and brief explanation. Thank you.
5:23 where DFS starts
doesn't matter for a connected graph, pick any vertex
@@johnbaker7102 bro you misunderstood 🤣
Very good! I love your explanation.
Your videos are really helpful. Keep uploading more such videos on graphs.
Great Job Tushar . Very clear and crisp
Appreciable. Simple and understandable teaching.
Impressive...!!
So well communicated that the concept looks sooo simple and clear.
Thanks Man.
+Divyanshu Shekhar Now I have subscribed to your channel.
I wish I could have done it earlier.
Great job! Thanks for sharing!
I owe Tushar my Job !! Awesome.Thanks
your videos help me a lot, thanks for your great contribution.
Thank you sir for posting this video..!
7:48 to 8:10 summary of dfs approach to detect cycle in an undirected graph
This is excellent, thank you!
Is it possible to implement this algorithm with BFS as well?
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.
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
great explaining
thank you
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.
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.
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
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 )
Very good explanation!Even fool can understand
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
Shouldn't the same algo work for directed graphs as well?
@@SriramGopalGoli030792 I believe it should.
@@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
This algo does not work for directed graphs. A simple example below.
1 -> [2,3]
2 -> [3]
3 -> []
thank you very much,can you explain about dijikstra's algorithm please
Plain and simple:)
Will this work if we have single node loop??
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.
Great Weedeo!
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.
I had the same thought.
@@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.
Thanks Tushar. well explained. Do I have always to use disjoint set to solve this problem?
Disjoint set is one way to detect cycle. DFS and topological sort are other ways to detect cycle.
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.
You can check his GitHub link in the description section.he had implemented an amazing class for representation of graph .
Hope it helps
Sir...which books are preferred to enhance more knowledge on this concepts
09:22 Where is the class DisjointSet defined? Is this a standard java class? Or was it created somewhere?
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
Can we use white gray black method in undirected graph too???
how you are going to apply topological sort on undirected graph for finding cycle..0:30 ???
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).
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 ??
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?
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?
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|)?
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.
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.
@@ultra_max_pro yea u know what man, I'm just happy I passed the class
is not "for(Edge edge: graph.getAllEdges())" taking O(E) times ?
sir, which mathematics are require for algoritm designer
discrete mathematics
nice explanation!!!!!!
but how to find all cycles that exist in graph....
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
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.
In a directed graph, there exists one path at the maximum from one node to other
if u uploaded the next lesson for me sir....plz
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.
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
Nice work big man... u convey tricky concepts with ease and clarity.. thnx alot ;)
pls do a video of directed graphs also thnx in advance
czcams.com/video/_cS3ZAy85AQ/video.html
You evaluated time complexity, have you considered operation findset's and union's time ?
O(1)
Hi tushar i need pseudo code for dfs for find in cycle in undirected graph
I need using dfs..not disjoints
Thank you..
Graaaafffffffff
thaak about....
in ur video there is problem in loading
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