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

GfG-Problem Link: bit.ly/3PvBfsm
C++/Java/Codes and Notes Link: takeuforward.org/data-structu...
DP Series: • Striver's Dynamic Prog...
SDE Sheet: takeuforward.org/interviews/s...
Check out our Website for curated resources:
Our Second Channel: / @striver_79
In case you are thinking to buy courses, please check below:
Code "takeuforward" for 15% off at GFG: practice.geeksforgeeks.org/co...
Code "takeuforward" for 20% off on sys-design: get.interviewready.io?_aff=takeuforward
Crypto, I use the Wazirx app: wazirx.com/invite/xexnpc4u
Take 750 rs free Amazon Stock from me: indmoney.onelink.me/RmHC/idje...
Earn 100 rs by making a Grow Account for investing: app.groww.in/v3cO/8hu879t0
Linkedin/Instagram/Telegram: linktr.ee/takeUforward
---------------------------------------------------------------------------------------------------------------------------

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

[@thatsharma1066]

stfu

[@cinime]

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

[@tanaysingh5348]

thanks for making the graph series even better

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

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

[@sahllsaharn4664]

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

[@saibunny1253]

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

[@sripriyapotnuru5839]

Thank you, Striver 🙂

[@jatinkumar4410]

Amazing explanation 🙌

[@DevashishJose]

Understood, Thank you so much .

[@sohailulislamalvi8656]

insanely good!

[@vakhariyajay2224]

Thank you very much. You are a genius.

[@stith_pragya]

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

[@ventacode]

thanks striver it helped

[@shyren_more]

understood, thanks!

[@karthiklv29]

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

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

[@CodeMode9313]

Thanks habibi tum acha kaam karti ...understood

[@adebisisheriff159]

Thanks so much!!!

[@santhoshs7028]

understood, thank you

[@kamikaze9245]

Understood bhaiya 🔥

[@ujjalsaha428]

Understood ❤️

[@lonersunited]

Understood 😊

[@loudcapricorn5513]

UNDERSTOOD 🤞🙌

[@sukritinarang5016]

Understood!

[@ashutosh..]

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

[@pranayjain._]

Understood Sir!!

[@ayushsinghchauhan6917]

u are just amazing

[@pawandeepchor89]

Top class content, thanks for all these videos.

[@UECAshutoshKumar]

Thank you sir 😁

[@user-tk2vg5jt3l]

Thank you bhaiya

[@chandantaneja6388]

Understood 👍

[@gautamsaxena4647]

Understood Bhaiya

[@_hulk748]

Understood sir❤🙏🙇‍♂

[@suryakiran2970]

Understood❤

[@sayakghosh5104]

understood!!

[@Chandraprakash-kx4ic]

understood sir❤

[@LoayYounesMusic]

Understood^^

[@cypher7536]

understood ❤️❤️

[@The_Shubham_Soni]

UNDERSTOOD.

[@nikitakeshri9233]

Understood :)

[@sannareddymonesh7598]

Understood!!

[@adarshkumarrao3478]

UNDERSTOOD

[@original_gangsta_]

Understood 😁😁

[@ChutHunter]

understood 👍

[@ishangujarathi10]

amazingg intuition

[@pheonix166]

Understood

[@GungunRamchandani]

understood

[@subee128]

Thanks

[@oqant0424]

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

[@snehiltiwari28]

understood :)

[@therangeplus]

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

[@shreyanshkumarsahu6534]

Understand 🥰🥰

[@avadhut325]

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

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

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

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

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

[@mansisethi8127]

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

[@SanidhyaPatel-q9s]

Which app do u use for teaching DSA in iPad?

[@atifhu]

when did top changed to topo

[@anishraj66]

What will be the time req to find indegree??

[@codingalley6229]

🐐

[@pratyakshhhhhhhhhhhhhhhhhhhhh]

🎉

[@TheSpiritualOne401]

Striver how do you remember all this?

[@aniketambat6334]

understood++

[@vaalarivan_p]

4:00 - 8:30

[@Piyush-yp2po]

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

[@UmeshYadav-qx4hr]

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

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

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

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

[@rayyansyed2998]

"understood"

[@shlokaggarwal7714]

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

[@kushagramishra5638]

"Understood"

[@soicooc3500]

4:00

[@shivamnegi7552]

whats the intuition

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

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

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

[@antassachan1782]

leetcode link for the question?

[@akashkumarsingh8369]

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

[@mdsameer533]

us

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

[@aryankumar3018]

Understood ntr

[@cypher7536]

0:19 kya kaha 🤣🤣...?

[@bemypro8602]

what happened to ur neck

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

[@AnmolSharma-br2eg]

Understood!

[@suhaanbhandary4009]

understood!!

[@mriduljain6809]

Understood Bhaiya

[@dreamyme543]

Understood:)

[@RohitSharma-yc8lm]

UNDERSTOOD

[@user-nb1ye5tf1r]

Understood

[@skblabla]

understood

[@pihus3498]

us

[@soubhikghosh6564]

Understood!

[@AyushSharma-ux4fk]

Understood!