Detect cycle in a directed graph
ฝัง
- เผยแพร่เมื่อ 21 ม.ค. 2020
- This video shows a very elegant and easy method to detect if a directed graph contains cycle or not. This is a basic graph problem which is frequently asked in internship as well as placement interviews. The technique is explained along with code illustration at the end of the video so do watch till the end to get a good grip on this problem. CODE LINK is given below. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
CODE LINK: gist.github.com/SuryaPratapK/...
Thank you Sir. I got a job. Initially I was very scared of graphs but your playlist on graphs really helped me to get out of that fear. And your leetcode problem's explanation on how to go from brute-force to optimal really helped a lot in clearing various concepts.
Dude you are awesome. The only mistake I was doing was not making the visited array to false after every iteration. You made it seem very easy.
Thanks :)
I was doing the same, now I too got it.
Because we never thought that way.
Learned new way of solving the problem, thank you so much TECH DOSE.
a nice clear step-by-step explanation of the algorithm, thank you very much for saving me some time teaching this to myself!
Been watching your videos for a while. The simple and crisp explanations are awesome. Really Appreciate your work (y)
Thanks :)
Another way is to color vertices to white (unvisited), gray (visited and open), and black (visited and done). Any edge to a gray node is a cycle. The upside is that this does not re-process already processed nodes.
A great video though
Yep. That's present in the next video. Thanks
I liked how in the adjacency list '1' is grounded.
:)
Thanks, man, your channel is the go-to video for this content, as soon as I see the blackboard, and your channel name, I instantly click it, Always keep this blackboard thing, it's in people's subconscious now xD. Thanks
👍🏼
Can we use the union Find algorithms for find the cycle right? Both directed and undirected?. Is there any situation like we only have to use this approach rather than Union Find?
Sir this backtracking approach is giving TLE when I am submitting my code in GFG. Sir what to do?
This is taking EV time. Try to use stack or coloring.
I understand that to process multiple components in graph the for loop is given , but we have to redo the whole process starting from every node in the graph ..... is there a way to optimize that tooo ? ( bcz some nodes are traversed during dfs and there is no reason to process them again )
You can color the graph for cycle detection. Once colored, don't revert back to original. That's the trick for O(E+V)
Guys you can optimise this further by assigning white, black and grey colours to the nodes. In the loop which checks vertices one by one, ignore those which are black. This way it will be linear O(V+E)
In neighbors check for only the grey nodes
Yes correct. Follow the explanation of undirected graph cycle detection in next video.
@@techdose4u You already taught "Graph Colouring" method to find cycles in DAG. Why this new algorithm, is this better than "Graph Colouring" or I'm missing something.
I have bookmarked your videos for future reference, using them to re-learn and refresh concepts with 2X speed! You definitely deserve more subs and like..
Great :)
Thank you for explaining so well.
If its a strongly connected acyclic undirected graph, then what could be the time complexity of it?? Can u please make a little bit clear why the time complexity is O(V+E) and not O(VE), as from each vertex we can visit all edges once ?
To detect a cycle in a directed graph we can use Topological Sort too right?? sir?
Can anyone explain why we haven't passed visited array by reference in the utility function as its a recursive function ??
Thanks for this video. Very well explained!
Welcome 😊
Sir, I read your comments about using stack to optimize the code. Can you give the example where there is a need of optimized code. I mean in what cases this implementation will give TLE.(I want to compare both approaches)
He's going DFS recursively. You can optimize this by putting each adjacent node on to a stack, then iterate the stack and pop each node.
stack = [root]
while len(stack) > 0:
node = stack.pop()
for n in node.adjacents:
stack.push(n)
// do whatever you want to do with the current node
Why you can't make visted (curr) to false after the loop end in isCyclic_utill() method.
SIR, IF I WANT TO PRINT THE NODES THAT CREATE THE CYCLE WHAT CODE WILL I HAVE TO ADD EXTRA??
If you are doing cycle detection recursively then maintain a vector (use pass by reference) and pass it during each recursion call. Keep pushing current node to vector as you make calls. Once you detect a cycle then you know what node is being repeated. Let's say your vector contains 1,2,3,4,5,6 and you made a call to next node and let's say it's 3. So, visited of 3 is True and so it is a cycle. Now find position of 3 in your vector. Trim the rest of the elements to the left of 3. So, your cycle will be 3,4,5,6. I hope you understood it. This question was asked in samsung interview.
@@techdose4u And i got this question for my algorithm course
Nice. Which course?
Very nicely explained sir 👍
meanwhile node "1" : you won't let me live you won't let me die😂
This is showing timeout exceeded on geeks for geeks. Is any optimization possible?
Yes. You need to maintain states for visited. Use three values. 0,1,2. 0 means never visited. 1 means visited but not processed. 2 means processed. This code which I provided is actually running in VE time. The algo says to run in V+E. So, optimize it. In my recent videos I have added the optimized approach for this. Watch my video on POSSIBLE BIPARTITION and use that code optimization for cycle finding. It will be easier.
Your explanation are awesome and simple. Thanks Sir
What is the time complexity for this ?
Great video.
If you could tell which software/device do you use to draw on the screen it would be helpful ? The quality is very good.
One Note/ Microsoft Notes/Evergreen etc
thank your sir..I always find your tutorial helpful
Welcome :)
Sir as we are making changes in visited array so it will consume a lot of time .... i think we should carry a new array of ancestors so that we can reduce the time complexity of this program. Thank you
How can I do this using an adjacency matrix insted of an adjacency list?
create a boolean 2 d matrix
use node (u,v) ==> (0,1),(1,2) , node = 3; it gives cycle even if not there in it.
Awesome Buddy you made my day
Thanks :)
Sir,can you give tips to optimize the code. It is showing TLE for some cases
You can also use recursive stack
@@daipayanhati2347 DSU can't be used for directed graph.
Bro,can we do it without using vis[] i.e with out extra space
You need to have extra space for stack in recursion and so your space can never be O(1) using recursion. If you want to remove the visited array then i dont think it will work (though i am not too sure about my statement). Graph coloring too requires same space and pure recursion will also take the same space. So i dont see improvement in space. This technique works efficiently when node labels are dense (i.e., no large gaps Between node numbers). This becomes inefficient for sparse node labels. For those types of graph, you can store them in SET. I hope you understood it :)
What would be the time complexity for this approach?
O(n^2)
dear techdose, why are not you passing visited array by reference in cycle util function?
Because passing such long DS again & again increases time complexity
Nice explanation , Sir as in iscyclicutil too we need to unvisit the node as if not it will showed up in a cycle form without a cycle as always true. Or no need to unvisit im confuse sir?
so dfs is being used V times can this make the total time complexity of O(V(V+E)) ??
@@techdose4u yes sir, i was thinking if that first for loop that calls isCyclicUtil for every node would contribute to the time complexity, also could that one call be the on the last node?
Can you repeat your question. Din't get you.
@@techdose4u No it's okay sir, i got the concept watching your latest video (: thank youuu
@@techdose4u Please tell me how the complexity is O(V+E)
This solution is giving time limit exceeded error, but when i am taking extra recursiveStack and keeping of track of visited nodes then it working fine.
What will be the time complexity ?
This ... might be a stupid question.
I understand that you can initialize the array because you already know how many vertices there are. But what if the input to you is just the root node of the graph (assuming only 1 entry point exists), and we don't know the total number of vertices?
I'm thinking about using set to store the flag information, but I'm not super sure.
Very good question. If you don't know the constraints or you want to save memory in a graph where nodes may be traversed sparsely like (1--200--5M etc) then using visited will be faster but will require memory = Range of node labels. Generally SET is implemented using Red-Black tree and so amortized time is log(N) but for visited array (since it's a hash is O(1). You can make use of a set as well. It will work. But see that when we return back to a node after processing then i was making visited = false. So, you will have to take out the node from SET (which is an expensive operation). So, generally we use visited array instead, if we don't have memory issues (which generally there isn't any). I got to think something new from your question. Thanks for asking :)
@@techdose4u Yeah no problem, and I really appreciate the quick reply!
I agree that if a set is implemented using red-black tree (which is a type of BST), then add and remove will both be O(logN), but I was actually thinking of HashSets (which I think of as HashTable/Dictionary with a constant value). If the hashing algorithm is good and there are no collisions, then insertion/remove should both be O(1) on average.
The problem with using array, as you said, when we approach large graphs with large gaps between adjacent nodes (like 1 --> 50000 --> 3), then you have to allocate memory for all the nodes in between that you won't necessarily use.
Yea true. There won't ever be a collision because node names should be unique. Today is holiday and i am running TH-cam , hence the quick replies :P
@@techdose4u gotcha, thank you so much!
I was reading a long comment just now in finding missing & repeating. Now i cannot find that comment. In that comment, you have an example which was wrong i think. I was trying to verify it. If you want to clarify on it then do let me know.
Thanks man!!
This approach is giving TLE on gfg, although I was able to understand this
This is simple implementation. You can make it much faster.
@@techdose4u how
@@himanshuraj5689 you could use either 2 visited arrays, one to keep track of current visiting order, and one to keep track of all processed nodes.
another approach is to use an integer array, and mark processed ones as 2, and skip the node in the next iteration if it is 2 (graph coloring).
Finally someone made it clear, each and everything word by word 💯❤️
Really!! 😁
Instead of bool visited vector i took bool visited array and it didn't work . Why ??
Please answer my query .
Did you initialise all values to false ?
@@techdose4u yes .
May be because array is passed by address so the actual parameters are always changed with formal parameters so the bool array will be true always which is not the case in vectors as it is passed by value
for me i used bfs to solve this problem . i found backtracking is hard but good to know new methods
Nice :)
Time complexity?
In isCyclicUtil Method, after for loop we have to change visted[curr]=true to false
what is the time complexity of this approach?
Simple VE and optimal V+E.
Very good tutorial , but please tell me how the complexity is O(V+E)?
There is a slight trick which makes time as V+E instead of VE. We need to maintain 3 states otherwise we need to maintain another vector. Somehow we need to preserve 3 states which I have explained in my video COURSE SCHEDULE with CODE. Please follow that.
Super sir.🔥
Correct me if I am wrong. Shouldn't the line 24 be :
return visited[curr] = false;
Reason : We want to remove the node curr from the path otherwise the graph below will return true but it should not.
1 : 2 3
2 : 3
Or are you defining a cycle as having two possible paths between two nodes in a directed graph.
My definition is:
The definition of a cycle in a directed graph is a path with same start and end vertex.
Also even after making this change to correct the solution does not optimise it. For every node we should store a result saying that this node does not have trail ending at itself. This way we will not have to traverse the same tree multiple times leading to O(V + E) time complexity. This is nothing but a memorization of the results for every subproblem where a subproblem is:
F(node) = Is there a trail starting and ending at node?
Best explanation
Thanks
Sir in is_Cyclic function ig u need to keep visited[curr]=false; after the loop!!
Hey is this method using DFS?
Yep
@@techdose4u thanks so much:)))))
Bro, This is wrong. Surprised how no one pointed it out.
But in icCyclic_util, please again assign visited[curr] = false.
Example test case that's failing [1,0],[2,0],[3,1],[3,2]
i was missing that one thing ... if we are going from 2 to 1. then i have to make 1 false again... Arigato
Yokoso
I have watch many videos but I'm bit confusing I watch this only one time I understand very well
Nice 😃 keep going.
Thank you sir
Welcome :)
Your approach is correct but i feel in your approach repeatitive work is being done.Like node 1 is being processed multiple times.Similarly other nodes are also processed multiple times..What we can do is ,we can keep track of nodes we have processed atleast once..and if we get a cycle then good if not that means we are not getting a cycle from that particular node..so we don't need to process that node again.So,next time we get a node that is already visited we will skip that node and check for other unvisited nodes.
no, i also thought of this method and wasted my time ... but it wont work. After not finding cycle from 0 and process 1,that means their is no cycle with 0 through 1. But their could be a cycle from lets say , (1,3,5) .
time complexity??
Simple approach VE. Using graph coloring or stack V+E.
bhaiya this approach is giving TLE, for the course schedule 1 problem of leetcode.
Yea. You need to optimize it. Use stack or graph coloring.
*Disjoint Set is sexier*
True :)
In iscycleutil function, after for loop you need to add visited[curr]=false
❤️🙏
4:57 😂😂
What was that 😅
@@techdose4u if you don't understand - rewind :D
You made the recursion quite complicated. Just make a utility function and pass the current source node to it. Mark it visited the moment you get inside the utility function after checking if it has been visited before. THen go for its neighbors and in postorder just backtrack.
This is O(V*E) approach...Topological Sort method will do it in O(V+E)
understood :)
Nice :)
You forget to make visited[i] = false in the iscyclic utility function also the tc is O(V*E) here.
Basically it's DFS on each vertices.
int sol = 0;
REP(I = 0, v) { sol = DFS(I); if (sol ) break ;}
Cout
The time complexity for this cycle-check is off the charts. The code will run slow
It's a kind of graph colouring technique to find cycle in a directed graph.
Make a video on white background.
I think there is a bug. The util function should also convert the visited array element to false before returning false. Otherwise it will give cyclic even when its not.
Yes , there' s a bug
Yes, there's a bug, its not working without converting the visited element to false in the util function
You missed to make current node false after processing it in util function else it is returning true only
JAVA CODE:
import java.util.*;
class Graph{
private int V;
private static LinkedList[] adj;
Graph(int v){
V = v;
adj = new LinkedList[v];
for(int i=0; i
And how do look for a cycle in an undirected graph?
It's a joke...
Thank you for sharing the video but i have an issue to raise ....please rectify me if i am wrong...
I think while returning you are supposed to make visited[curr] = false in isCyclic_util()as well.....because once node is visited and visited[curr] = true then you are never making the neighbours false again but you are just making the current node visited value false....
It is in recursion, so all the nodes once backtracked will be made false.
Yes, i was stuck at the same issue, tried same code in java, but was getting true for no cycle in graph as well.. so i tried doing visited[curr] = false in util method and it worked,, idk why is it happening, i tried the cpp variant , its working fine over there.. if surya sir could clarify this, it'd be great.
I was thinking the same. Sir, consider the case 0:[1],1:[]. In this case, once you call cyclic_util on 1 it will make visited[1]=true but will never set it back to false. Can you please clarify?
@@techdose4u I am facing the same issue, I think we should make the neighbours false too when we are exploring them. Because in the explaination you are doing that but in the code we are nowhere doing it. At the end of for loop in the isCycle_util we should set visited[curr] = false; so that the process works fine. Please tell me your views.
@@nagarjunreddygaddam5059 What I am thinking, is yes we should do that, but here we are having totally different copy of visited array so even if we are not setting visited[1] = true, it wont reflect in the isCycle function. I am somewhat confused. What are your views
An easy java code based on same approach with TLE avoiding trick.
class Solution {
LinkedList[] adj;
public boolean canFinish(int numCourses, int[][] prerequisites) {
adj = new LinkedList[numCourses];
for(int i = 0; i < numCourses; i++) {
LinkedList list = new LinkedList();
adj[i] = list;
}
int lrCount = 0;
int rlCount = 0;
// create a graph by filling data to adj.
for(int i = 0; i < prerequisites.length; i++) {
int fromCourse = prerequisites[i][0];
int toCourse = prerequisites[i][1];
LinkedList list = adj[fromCourse];
list.add(toCourse);
if(toCourse < fromCourse)
rlCount++;
if(fromCourse < toCourse)
lrCount++;
}
// keep increasing or keep decreasing graph will never be a cycle, so it can always be finished.
// this condition is just to avid TLE and to improve performance.
if(rlCount == prerequisites.length || lrCount == prerequisites.length)
return true;
boolean visited[] = null;
boolean cycleExists = false;
for(int i = 0; i< adj.length; i++) {
visited = new boolean[numCourses];
cycleExists = doesCycleExist(i, visited);
if(cycleExists)
return !cycleExists;
}
return !cycleExists;
}
boolean doesCycleExist(int x, boolean[] visited) {
if(visited[x] == true)
return true;
visited[x] = true;
boolean cycleExists = false;
for(int k : adj[x]) {
cycleExists = doesCycleExist(k, visited);
if(cycleExists)
return true;
visited[k] = false;
}
return false;
}
}
👍🏼
This method gives tle ,,I guess because large size of rec tree
I think this is because it's time complexity is O(V.(V+E)). You can optimize this to solve in O(V) using either stack or coloring.
Pass the visited array by reference in the utility function I guess that is the issue .
Code Link : techdose.co.in/detect-cycle-in-a-directed-graph/
It would have been better if could have explained the logic before explaining the how we are solving this.
its giving tle
very good
insta?
your code is not working in java
11 / 410
Input:
6 5
5 3
3 1
1 2
2 4
4 0
And Your Code's output is:
1
Its Correct output is:
0
Output Difference
1
11 / 410
Input:
6 5
5 3
3 1
1 2
2 4
4 0
And Your Code's output is:
1
Its Correct output is:
0
Output Difference
1
A humble request, instead of just explaining the algorthim please say the intuition behind the alogrthim,how the algorthim is derived..
Sir in this function need correction i guess...
bool isCyclic_util(vector adj[], vector visited, int curr)
{
if(visited[curr]==true)
return true;
visited[curr] = true;
bool FLAG = false;
for(int i=0;i
love u bro, I have implemented this algorithm in c and it wasn't working as it should. I thought there was a problem with how I implemented the code into c, but turns out that there was a problem in his code. Thank you for spotting the mistake!
Very useful but too fast man. Felt more like an overview than a lesson.
There's better approach in terms of understanding
Below is the code:
This is by far the crispiest code
def optimized_eventualSafeNodes(graph):
safe = {}
def dfs(node):
if node in safe:
return safe[node]
safe[node] = False
for nei in graph[node]:
if not dfs(nei):
print("cycle detected in graph : ", nei)
return False
safe[node] = True
return True
output = []
for node in range(len(graph)):
if dfs(node):
output.append(node)
# node with false safe value are in cycle
print(output)
Another Approach is:
try topological sorting:
def my_eventualSafeNodes(graph):
output = []
for index, ele in enumerate(graph):
for inner_ele in ele:
output.append((index, inner_ele))
new_graph = {i: [] for i in range(len(graph))}
for src, dst in output:
new_graph[src].append(dst)
if dst not in new_graph:
new_graph[dst] = []
visited = set()
stack = []
result = {}
def dfs(vertex):
if vertex in result:
return result[vertex]
if vertex in stack:
# we found cycle,
# this approach resonates to topological sort and detect cycle in directed graph
while stack:
vertex = stack.pop()
result[vertex] = False
return False
stack.append(vertex)
visited.add(vertex)
for neighbor in new_graph[vertex]:
if not dfs(neighbor):
return False
if stack:
stack.pop()
result[vertex] = True
return True
final_result = []
for node in new_graph:
if node not in result:
if dfs(node):
final_result.append(node)
elif result[node]:
final_result.append(node)
print(final_result)
3. Use Union Find Approach to detect cycle in directed graph:
def findRedundantConnection(edges):
parent = list(range(len(edges) + 1))
rank = [1] * (len(edges) + 1)
def find_parent(node):
node_parent = parent[node]
while node_parent != parent[node_parent]:
node_parent = parent[node_parent]
return node_parent
def union(at, to):
at_parent = find_parent(at)
to_parent = find_parent(to)
if at_parent == to_parent:
# Cycle detected
return False
if rank[to_parent] > rank[at_parent]:
parent[at_parent] = to_parent
rank[to_parent] = rank[at_parent] + rank[to_parent]
else:
parent[to_parent] = at_parent
rank[at_parent] = rank[at_parent] + rank[to_parent]
return True
for at, to in edges:
if not union(at, to):
return (at, to)
edges = [[1, 2], [1, 3], [2, 3]]
print(findRedundantConnection(edges))