Let's continue the habit of commenting “understood” if you got the entire video. Please give it a like too, you don't 😞 Do follow me on Instagram: striver_79
FYI - for someone thinking why visited array is not used here Visited array is not required in this case because we are only inserting the node into the queue whenever the degree of that node becomes 0 and this will only happen once. Suppose like in the above example 4 was trying to visit 0 but it did not insert 0 into the queue for the first time as the indegree was not 0. and that;s why when 5 was trying to insert 0 , it did not have to check if 0 was visited earlier
in simple language , an element's indegree will become 0 only when all the parent nodes(nodes pointing to it) are withdrawn that is put into the topo list. Since every possible node (which could have that element as a neighbour) is already taken out of the queue and put into the topo list , so our neighbour node won't be touched again. And for not touching an already touched node , visited array is required , and it purpose is already solved in kahn's algorithm itslef , so no vis list is required here !!
Note: Componentwise checking not required here because every component has at least one node with indeg=0 and hence atleast one node of every component will get included in the queue initially
understood !! ........... Hey he is amazing I learned a new algo (kahn's).... in just 15 mins with its code because of him .... he is a gem guy!!.......
FAQ 1: why we don't use boolean[] visited in Kahn's algo? The standard bfs algo is generic if it is cycle or acyclic or directed or undirected work well the Kahn's only apply on DAG so no cycle, no need to worry about infinite loop condition then what about getting same node twice(it won't happy bcz we reach 0 only one time) so the need to visited not require we process each node once by using indegree array
since, we are only putting in queue when indegree become zero........ so it is not possible for any node later on , that it visit an already visited node again.
FYI - Kahn's algorithm works well even if you replace the queue with a stack. It just produces a different topological sort sequence. Here's an excerpt from Wikipedia article. "...Reflecting the non-uniqueness of the resulting sort, the structure S can be simply a set or a queue or a stack. Depending on the order that nodes n are removed from set S, a different solution is created..."
My laziness raised 1 question that keeps my head scratched: "When easier one algo is there (about DFS) then why this algo exists?". I believe I will get answers and uses in next couple of videos in the series.
The problem with using the dfs approach is that if you are given a directed graph that contains a cycle in the solution. The algorithm wont be able to detect, it will spill out an ordering which is wrong. But when using khans algorithm, you will be able to detect whether top. sort was possible or not. You can do this by checking if the ordering has the same length as the number of nodes. if it is true then top sort was possible. So you have to know this just in case your interviewer adds such an edge case
@@decepticonWave you are absolutely correct ! Just in case anyone Tends to use DFS and still wanna detect CYCLE u must see How to detect Cycle in direted graph using DFS of Striver u just need to add one array which stores Self visited[ ] and boom problem is solved in one line
only similarity between Kahn's Algorithm and BFS is using queue Data Structure.... BFS is when we search in level, but here we are searching when indegree is getting zero. So, we can't relate BFS and Kahn's Algo. ~ Kahn
Everything else is fine. But for someone who watches this video will not understand why we need the vertices in this order. It is not enough to say topological sort gives an ordering of vertices .. we should also know why we need that ordering .. what problems it solves if we process the graph nodes in this ordering.. these basics are missing .. I still feel William Fiset is the best or reading books like Sedgewick will give a very good idea of applications
Sometimes I just want to give up, cuz I feel that remembering so many intuitions is impossible for me! And remembering all of these for a lifetime! I am seriously thinking of shifting to Data Analytics. Salary kam milegi, lekin ek acche company ka tag to mil jayga na!!!!
im a bit confused on the assumed form of this adjacency matrix. are we assuming a 2d array where arr[i][j] = 1 if there is a directed edge from i to j?
I was also thinking the same but I got the reason now. Visited array is not required in this case because we are only inserting the node into the queue whenever the degree of that node becomes 0 and this will only happen once. Suppose like in the above example 4 was trying to visit 0 but it did not insert 0 into the queue for the first time as the indegree was not 0. and that;s why when 5 was trying to insert 0 , it did not have to check if 0 was visited earlier
because here we are storing the no. of incoming edges in the node so it can be 2,3 and so on but visited array is used only to check if the node has been visited or not and it store only 0 & 1.
Let's continue the habit of commenting “understood” if you got the entire video. Please give it a like too, you don't 😞
Do follow me on Instagram: striver_79
FYI - for someone thinking why visited array is not used here
Visited array is not required in this case because we are only inserting the node into the queue whenever the degree of that node becomes 0 and this will only happen once. Suppose like in the above example 4 was trying to visit 0 but it did not insert 0 into the queue for the first time as the indegree was not 0. and that;s why when 5 was trying to insert 0 , it did not have to check if 0 was visited earlier
that means once it becomes 0 next time it will go negative??thats why it will only get into the que once
@@stl8857 nah bro, once its zero it mean incoming edges to it is 0 so how can it even reduce further?
@@codingalley6229 okier
Correct. I realized that too after running through the algorithm. In a sense, a visited array here is the inDegree check
in simple language , an element's indegree will become 0 only when all the parent nodes(nodes pointing to it) are withdrawn that is put into the topo list. Since every possible node (which could have that element as a neighbour) is already taken out of the queue and put into the topo list , so our neighbour node won't be touched again. And for not touching an already touched node , visited array is required , and it purpose is already solved in kahn's algorithm itslef , so no vis list is required here !!
Sir, I only respect a few people for their way of teaching people, and you are among them for sure. Hats off to you and YES "UNDERSTOOD".
His graph series is impeccable
Note: Componentwise checking not required here because every component has at least one node with indeg=0 and hence atleast one node of every component will get included in the queue initially
But to find those nodes we need to traverse the graph first
@@RajeevCanDev we are already having a loop (V) in starting while checking the inDegree
@@namesurname2223 yes that's what I'm saying.. to find those nodes we first need to traverse all nodes for finding the indegree
understood !! ........... Hey he is amazing I learned a new algo (kahn's).... in just 15 mins with its code because of him .... he is a gem guy!!.......
Your explanation is great and helpful. Wishing your channels great success!
We are very lucky because we have this amazing playlist of graph . All thanks to you brother.❤❤
Why calculating indegree takes O(N) and not O(N^2) ?
thanks for making the graph series even better
FAQ 1:
why we don't use boolean[] visited in Kahn's algo?
The standard bfs algo is generic if it is cycle or acyclic or directed or undirected work well
the Kahn's only apply on DAG so no cycle, no need to worry about infinite loop condition then what about getting same node twice(it won't happy bcz we reach 0 only one time)
so the need to visited not require we process each node once by using indegree array
since, we are only putting in queue when indegree become zero........ so it is not possible for any node later on , that it visit an already visited node again.
Thank You So Much for this wonderful video............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Thanks habibi tum acha kaam karti ...understood
striver thank you ! i understood this kahn's algorithm using a slightly different bfs
FYI - Kahn's algorithm works well even if you replace the queue with a stack. It just produces a different topological sort sequence. Here's an excerpt from Wikipedia article.
"...Reflecting the non-uniqueness of the resulting sort, the structure S can be simply a set or a queue or a stack. Depending on the order that nodes n are removed from set S, a different solution is created..."
you've reallly worked on your explanation a great one sir it is a good change and a great teacher
Revision: Forgot everything about indegree, was trying to use bfs the same as dfs and ans.push_back(q.front());
Sep'6, 2023 03:52 pm
Bro it is amazing how you explain things so clearly. I learned sm more from this video than others tysm!!
Understood! Extremely wonderful explanation as always, thank you very much!!
Amazing explanation 🙌
Thank you, Striver 🙂
At the end of the day... I understood it well :-)
Understood, Thank you so much .
Thank you sir 😁
My laziness raised 1 question that keeps my head scratched: "When easier one algo is there (about DFS) then why this algo exists?". I believe I will get answers and uses in next couple of videos in the series.
The problem with using the dfs approach is that if you are given a directed graph that contains a cycle in the solution. The algorithm wont be able to detect, it will spill out an ordering which is wrong. But when using khans algorithm, you will be able to detect whether top. sort was possible or not. You can do this by checking if the ordering has the same length as the number of nodes. if it is true then top sort was possible.
So you have to know this just in case your interviewer adds such an edge case
@@decepticonWave you are absolutely correct ! Just in case anyone Tends to use DFS and still wanna detect CYCLE u must see How to detect Cycle in direted graph using DFS of Striver u just need to add one array which stores Self visited[ ] and boom problem is solved in one line
@@decepticonWave true.
because if u use dfs u hv to do cycle detection also
UNDERSTOOD 🤞🙌
understood, and thank you for the clear cut explanation and the series
insanely good!
Thank you very much. You are a genius.
Understood ❤️
understood, thanks for the effort
UNDERSTOOD.
Understood Sir!!
4:00 - 8:30
Understood bhaiya 🔥
u are just amazing
very helpful!
thanks striver it helped
Top class content, thanks for all these videos.
Understood ✨✨
understood, thank you
Understood sir❤🙏🙇♂
Understood Bhaiya
Understood 👍
Thank you bhaiya
UNDERSTOOD
understood, thanks!
Thanks so much!!!
only similarity between Kahn's Algorithm and BFS is using queue Data Structure.... BFS is when we search in level, but here we are searching when indegree is getting zero. So, we can't relate BFS and Kahn's Algo.
~ Kahn
Understood 😁😁
Understood!
Yeah understood
Understood !!!!!!!!!!!!!
understood sir❤
Everything else is fine. But for someone who watches this video will not understand why we need the vertices in this order.
It is not enough to say topological sort gives an ordering of vertices .. we should also know why we need that ordering .. what problems it solves if we process the graph nodes in this ordering.. these basics are missing .. I still feel William Fiset is the best or reading books like Sedgewick will give a very good idea of applications
Thanks
Understood^^
Understood!!
We dont even need a stack, we can directly add index whose value is zero.
Understood
understood ❤️❤️
Isn't calculating indegree is O(V*E)??
amazingg intuition
understood!!
Understood:)
when did top changed to topo
Understand 🥰🥰
"Understood"
understood
Sometimes I just want to give up, cuz I feel that remembering so many intuitions is impossible for me! And remembering all of these for a lifetime! I am seriously thinking of shifting to Data Analytics. Salary kam milegi, lekin ek acche company ka tag to mil jayga na!!!!
understood :)
Can we say a Directed graph whose none of the indegree is zero has a cycle?
No , That means that is a not connected graph think huh?
we can use stack also in this implementation instead of a queue.. why doesnt it make a difference
Kahn's is Topo sort with BFS, that's why.
im a bit confused on the assumed form of this adjacency matrix. are we assuming a 2d array where arr[i][j] = 1 if there is a directed edge from i to j?
"understood"
What will be the time req to find indegree??
can we not do a thing that sort the indices in ascending order of indegrees?
Striver how do you remember all this?
🐐
Does kahn's algorithm work for Iterative DFS or does it only work for BFS ?
First question in which visited array is not used . And it makes complete sense. But still it feels weird and i can't digest it.
What if the graph has multiple components???
then in the beginning, the node will in-degree 0 from each component will be pushed in the queue
🎉
Which app do u use for teaching DSA in iPad?
where are you working bro
whats the intuition
//here is the code both by bfs and dfs
#include
using namespace std;
void dfs(vector & adj, vector & visited,int node,stack & st);
vector sol(vector adj, vector & visited){
stack st;
for(int i=0;i
4:00
file not found for -- C++/Java/Codes and Notes Link
understood++
Why didn't we take a visited array in this code?
I was also thinking the same but I got the reason now. Visited array is not required in this case because we are only inserting the node into the queue whenever the degree of that node becomes 0 and this will only happen once. Suppose like in the above example 4 was trying to visit 0 but it did not insert 0 into the queue for the first time as the indegree was not 0. and that;s why when 5 was trying to insert 0 , it did not have to check if 0 was visited earlier
:beatin💋💋💋
understood
lo bhai kr diya comment ye emoji(😞😞😞) mt kra kro yarr
Understood ntr
us
leetcode link for the question?
0:19 kya kaha 🤣🤣...?
what happened to ur neck
Hey can anyone explain why he did not used visited array in this problem??????
because here we are storing the no. of incoming edges in the node so it can be 2,3 and so on but visited array is used only to check if the node has been visited or not and it store only 0 & 1.
Understood 😊
Understood Bhaiya
understood