G-22. Kahn's Algorithm | Topological Sort Algorithm | BFS

[@takeUforward]

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

[@GirishJain]

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

[@stl8857]

that means once it becomes 0 next time it will go negative??thats why it will only get into the que once

[@codingalley6229]

@@stl8857 nah bro, once its zero it mean incoming edges to it is 0 so how can it even reduce further?

[@stl8857]

@@codingalley6229 okier

[@Moch117]

Correct. I realized that too after running through the algorithm. In a sense, a visited array here is the inDegree check

[@aadharjain313]

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 !!

[@Amankumar-sb4jn]

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

[@Moch117]

His graph series is impeccable

[@sayandey2492]

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

[@RajeevCanDev]

But to find those nodes we need to traverse the graph first

[@namesurname2223]

@@RajeevCanDev we are already having a loop (V) in starting while checking the inDegree

[@RajeevCanDev]

@@namesurname2223 yes that's what I'm saying.. to find those nodes we first need to traverse all nodes for finding the indegree

[@Stumbleguys-qk6uz]

right

[@visheshagrawal8676]

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

[@hellothere4732]

Your explanation is great and helpful. Wishing your channels great success!

[@vijayanks1714]

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

[@jaishriharivishnu]

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.

[@gayatrichaudhary580]

We are very lucky because we have this amazing playlist of graph . All thanks to you brother.❤❤

[@VarshaSingh-hi2sb]

Why calculating indegree takes O(N) and not O(N^2) ?

[@FooBar-lb5wf]

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

[@CodeMode9313]

Thanks habibi tum acha kaam karti ...understood

[@tanaysingh5348]

thanks for making the graph series even better

[@stith_pragya]

Thank You So Much for this wonderful video............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@saibunny1253]

striver thank you ! i understood this kahn's algorithm using a slightly different bfs

[@sahllsaharn4664]

you've reallly worked on your explanation a great one sir it is a good change and a great teacher

[@jaishriharivishnu]

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

[@googleit2490]

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

[@dhruvdangi8923]

love your videos sir

[@jatinkumar4410]

Amazing explanation 🙌

[@cinime]

Understood! Extremely wonderful explanation as always, thank you very much!!

[@DevashishJose]

Understood, Thank you so much .

[@bablushaw6856]

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.

[@decepticonWave]

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

[@TheOfficialAyush]

@@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

[@shivarajpatil8699]

@@decepticonWave true.

[@whateverittakes7929]

because if u use dfs u hv to do cycle detection also

[@therangeplus]

Bro it is amazing how you explain things so clearly. I learned sm more from this video than others tysm!!

[@sripriyapotnuru5839]

Thank you, Striver 🙂

[@ashutosh..]

At the end of the day... I understood it well :-)

[@vakhariyajay2224]

Thank you very much. You are a genius.

[@kaichang8186]

understood, thanks for the effort

[@AtharvaRao0104]

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

[@atifhu]

when did top changed to topo

[@UECAshutoshKumar]

Thank you sir 😁

[@karthiklv29]

understood, and thank you for the clear cut explanation and the series

[@Piyush-yp2po]

Isn't calculating indegree is O(V*E)??

[@loudcapricorn5513]

UNDERSTOOD 🤞🙌

[@vaalarivan_p]

4:00 - 8:30

[@kulvindersingh5764]

very helpful!

[@ow_aqua8875]

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?

[@kamikaze9245]

Understood bhaiya 🔥

[@sohailulislamalvi8656]

insanely good!

[@Learnprogramming-q7f]

Thank you bhaiya

[@pranayjain._]

Understood Sir!!

[@ayushsinghchauhan6917]

u are just amazing

[@TON-108]

Understood ✨✨

[@ventacode]

thanks striver it helped

[@santhoshs7028]

understood, thank you

[@ujjalsaha428]

Understood ❤️

[@The_Shubham_Soni]

UNDERSTOOD.

[@ishan5033]

Can we say a Directed graph whose none of the indegree is zero has a cycle?

[@rahulmehndiratta3856]

No , That means that is a not connected graph think huh?

[@mriduljain6809]

Understood Bhaiya

[@pawandeepchor89]

Top class content, thanks for all these videos.

[@mansisethi8127]

can we not do a thing that sort the indices in ascending order of indegrees?

[@shlokaggarwal7714]

We dont even need a stack, we can directly add index whose value is zero.

[@avadhut325]

Does kahn's algorithm work for Iterative DFS or does it only work for BFS ?

[@UECSoumyaRay]

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!!!!

[@SanidhyaPatel-q9s]

Which app do u use for teaching DSA in iPad?

[@harshdeepsinghlongia6040]

we can use stack also in this implementation instead of a queue.. why doesnt it make a difference

[@rushidesai2836]

Kahn's is Topo sort with BFS, that's why.

[@_hulk748]

Understood sir❤🙏🙇‍♂

[@anishraj66]

What will be the time req to find indegree??

[@adebisisheriff159]

Thanks so much!!!

[@TheSpiritualOne401]

Striver how do you remember all this?

[@shyren_more]

understood, thanks!

[@Kiruthika_vlogs]

where are you working bro

[@princenagar1686]

Yeah understood

[@sohammukherjee1392]

What if the graph has multiple components???

[@ujwalgupta4508]

then in the beginning, the node will in-degree 0 from each component will be pushed in the queue

[@UmeshYadav-qx4hr]

file not found for -- C++/Java/Codes and Notes Link

[@shivyanshgarg2641]

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.

[@RohitSharma-yc8lm]

UNDERSTOOD

[@gangsta_coder_12]

Understood 😁😁

[@chandantaneja6388]

Understood 👍

[@Chandraprakash-kx4ic]

understood sir❤

[@kushagramishra5638]

"Understood"

[@AnmolSharma-br2eg]

Understood!

[@ishangujarathi10]

amazingg intuition

[@subee128]

Thanks

[@oqant0424]

Understood !!!!!!!!!!!!!

[@LoayThePhrygian]

Understood^^

[@sayakghosh5104]

understood!!

[@cypher7536]

understood ❤️❤️

[@AnkitKumar-ko5tr]

Understood

[@sannareddymonesh7598]

Understood!!

[@shreyanshkumarsahu6534]

Understand 🥰🥰

[@dreamyme543]

Understood:)

[@rayyansyed2998]

"understood"

[@snehiltiwari28]

understood :)

[@teetanrobotics5363]

understood

[@rickk3300]

Why didn't we take a visited array in this code?

[@GirishJain]

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

[@shivamnegi7552]

whats the intuition

[@pratyakshhhhhhhhhhhhhhhhhhhhh]

🎉

[@codingalley6229]

🐐

[@akashkumarsingh8369]

understood lo bhai kr diya comment ye emoji(😞😞😞) mt kra kro yarr

[@aniketambat6334]

understood++

[@vaibhavjangid3112]

:beatin💋💋💋

[@soicooc3500]

4:00

[@antassachan1782]

leetcode link for the question?

[@deepakjain4481]

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

[@cypher7536]

0:19 kya kaha 🤣🤣...?

[@aryankumar3018]

Understood ntr

[@mdsameer533]

us

[@bemypro8602]

what happened to ur neck

[@Harsh-jc2bz]

0:19 gand?

[@pranavkhairnar1290]

Hey can anyone explain why he did not used visited array in this problem??????

[@shivamjain9968]

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.

[@lonersunited]

Understood 😊