Topological Sort | Kahn's Algorithm | Graph Theory

Подписаться 173 тыс.

Просмотров 116 тыс.

50% 1

Source code repository:
github.com/williamfiset/algor...
Video slides:
github.com/williamfiset/algor...
Website:
www.williamfiset.com
Audio intro/outro composed by Richard Saney (rnsaney@gmail.com)
0:00 Intro
0:22 Topological sort example
2:09 Topological sort motivation
2:37 Topological ordering
3:36 Directed acyclic graphs
4:31 A case against cycles
5:36 Kahn's algorithm intuition
6:05 Kahn's algorithm example1
7:11 Kahn's algorithm example2
11:15 Kahn's algorithm pseudocode
12:57 Outro
===================================
Practicing for interviews? I have used, and recommend `Cracking the Coding Interview` which got me a job at Google. Link on Amazon: amzn.to/3cvMof5
A lot of the content on this channel is inspired by the book `Competitive Programming` by Steven Halim which I frequently use as a resource and reference. Link on Amazon: amzn.to/3wC2nix

Опубликовано:

13 июл 2024

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 135

@shouryasingh2193 3 года назад

I just now Solved Course Schedule II on leetcode using this algo

@williamadams5034 3 года назад

My favourite ordering is to Keep Sleeping.

@njkevlani 3 года назад

TIL Superman didn't know topological sort

@puneetkumarsingh1484 3 года назад

This video is simply great. When I read it first, it took 3-4 hrs to fully understand the algorithm. The video has done the same in 14min.

@Aldrin32f 2 года назад

Repeated the same feat, RU-vid recommendation to the rescue. PS Thanks @WilliamFiset

@1hpdell 2 года назад

William, really appreciate your effort in making this Video! Effort behind this Animation is awesome, explanation is awesome too!

@geniamartynova8844 Год назад

Clean and concise explanation. Easy to comprehend and remember. Thank you!

@abhinavboyed6624 2 года назад

I'm about to binge watch all your videos. Thanks for the awesome content!

@robaczliwy 3 года назад

Thank you for a very clear explanation. Implementation was easy once I grasped the concept you've laid out in this video.

@nehascorpion 2 года назад

Awesome content! Thank you for putting in so much effort. Appreciate it!

@Sunny-vl1ff 3 года назад

Thanks! It is great to see how the algorithm works in practice.

@dheerajgopinath1892 2 года назад

The way you explained is simply superb!! especially the "getting ready for school" example..

@mercyomwoyo985 11 месяцев назад

Thanks William for the visualization and Animation! I clearly understand the concept now!

@mister_mad Год назад

amazing explanation and visualization of the algorithm! a video unlike no other

@zy3749 3 года назад

Thank you so much, it is the most clear explanation I've found.

@przemekbary Год назад

Thanks a lot for the explanation. You've got a great gift of explaining complicated thing easy (which IMO is the sign of a genius mind)

@shnerdz 3 года назад

great explanation as always. please make a video on segment trees next! such a powerful yet simple data structure

@centr0 11 месяцев назад

Wow. I understood that. Great way of teaching. You’re amazing. Thank you, sir.

@m.movsar 6 месяцев назад

Лучший канал по алгоритмам! Thank you William!

@fantasy9960 Год назад

thank you so much William! this is extremely helpful for beginners!

@tanmaykharshikar9419 3 года назад

This video is a gem, thanks! You have a new fan :)

@Junposs 3 года назад

Thank you Wiliam, I finally understand what Topological Sort is!

@hix0071 3 года назад

Keep it up William. May you reach million subs next year !

@m-meier Год назад

This was awesome! Subscribed!

@northridgefield 9 месяцев назад

Great clarity - quality content.

@kevintran6102 3 года назад

Good as always. So easy to understand.

@LUKFUNTV 3 года назад

Really takes an effort to make it sooooooooooooo SIMPLE🙏🙏🙏🙏🙏🙌🙌🙌🙌🙌

@twistedlog24 4 месяца назад

thanks for explaning this so clearly!!

@agnelamodia 3 года назад

Easy and simple. Marvelous.

@leducphuclong Год назад

Thank you so much, I really appreciate your video. Please continue...

@neerajkulkarni6506 3 года назад

10/10 beautifully explained!

@yujianzhao6461 3 года назад

Thanks a lot man! I really appreciate your work!

@mickeynig1 3 года назад

Thanks Mr. Fiset really awesome explanation

@soanonso Год назад

Nicely explained - thanks for this.

@geomichelon 2 года назад

great video! Thanks man!

@justarandomguyofficial1058 2 года назад

just looking at the playlists you made motivates me

@yangli8224 3 года назад

amazing explanation!

@ksenthu 3 года назад

Best explanation ever, thank you!

@lazysky1234 Год назад

Thank you for your video, great explanation!

@KevinDesai 2 года назад

What an example to start with. Thanks for not starting with gibberish numbers. This makes more sense than all the other videos

@mostafaarafa1461 3 года назад

Thanks, You explained it really perfectly

@jisanson 3 года назад

Thank you for this awesome video!

@babumon5351 3 года назад

Very nice explanation. Thanks

@algorithmscasts902 3 года назад

Nice animation and great explanation, thank you

@WebSurfingIsMyPastime Год назад

Great Video!

@ricardo7240 3 года назад

Awesome, keep it up!

@NoName-ip4tt 3 года назад

Animation you conduct has heart beat sound as background. I like it :)

@AbrahamWilson 3 года назад

Hey William, just wanted to say thank you. If it's possible could you make a series on DP like the one you're doing for graph theory.

@vedantsharma5876 2 года назад

That would surely be the best DP course on RU-vid. I love how he explains

@sandeepjnv13 2 года назад

Not to undermine William but there’s RU-vid channel “Inside Code”, he explains lot of concepts pretty well. He has dynamic programming content as well. Also a Udemy course on dynamic programming

@pelvispresley22 Год назад

The freecodecamp video from Alvin Zablan on DP is as good as it gets

@David-fy1sn 2 года назад

Wow great explanation in only 13 mins!

@avipatel1534 2 года назад

Thanks this video helped me optimize my sort code for leetcode course scheduling

@prabhat2342 2 года назад

wonderful explanation, thanks man:)

@abhishektiwari7643 3 месяца назад

Was following a course and couldn't understand this concept there but this video was so simple and better explained

@migzleon4047 2 года назад

Excellent content.!

@VijayKiran225 2 года назад

beautiful explanation .. keep up the good work.. subscribed as well

@shreyashachoudhary480 2 года назад

Awsm!

@njww13 2 года назад

This video helped a lot since before I would constantly wake up in the morning and put on my school before my socks

@akshatmehra3951 11 месяцев назад

You're the best man

@akidanis6984 3 месяца назад

holy shit this was such a great explanation, tysm!!

@kartarsingh7776 3 года назад

That was a great example(dressing up) at the start of video.

@markwillis2336 Год назад

I work from home. Why do I even need this getting dressed algorithm again? What an incredible breakdown, thank you so much for simplifying this complex topic so much for complete beginners like me.

@Learner010 3 года назад

Very nice explanation. please make a video on articulation point and bridges

@pamp3657 11 месяцев назад

very good video

@saralee548 2 года назад

amazing.

@LUKFUNTV 3 года назад

I recommend this.........to all the before_watching_read_comments_section people 🙌🙌🙌

@mnchester 2 года назад

great vid

@droy7528 3 года назад

Thanks a lot, William for all these golden videos. I recently came across Aho- corasick and finding it really difficult to umderstand it properly. So I am commenting on the latest vdo here...hoping u would see my comment. We would be really grateful if u could pull up a vdo on Aho-Corasick. Thanks in advance.

@JeremyIglehart 2 года назад

Great video. Small suggestion - right at the end where you check if index is not equals to n it would be really nice if you also showed an example of what would happen with your code if there was a cycle in the graph.

@jamesbon68 2 года назад

For anyone wondering about this, if you imagine a 3 node cycle, A -> B -> C -> A. Notice that you will never add these nodes to the queue because their indegree will never be 0. This implies that index will also never be larger than n.

@Sauce-ke 3 года назад

I hope all of my professors are teaching the same as you. I really need a data structure 1 on 1 teacher to teach me everything

@yamatolowa2256 3 года назад

this is 1 on 1 teaching i believe

@user-tb8or6ii9v 2 года назад

Kahn : Implements Topological Sort. Superman : Am i a joke to you ? Wears underwear after pants.

@richa2950 2 месяца назад

Best😭❤❤❤❤

@atharvas4399 2 года назад

this is 100 times better than my algo professor

@karankanojiya7672 2 года назад

Respect++

@ameynaik2743 3 года назад

Nice video, how is this different from another video you have on top sort using dfs?

@spicy_wizard 3 года назад

FANTASTIC. The problem with DFS on topological sort is that the recursion is too expensive, BFS is faster in all other aspects

@puneetkumarsingh1484 3 года назад

Alternatively, we can implement the DFS topological sort algo, using stack.

@zappist751 Год назад

MAH MANNN

@cikolatalpudingg1968 6 месяцев назад

muhteşem yaa

@amanbhatia7442 2 месяца назад

just realized you have a similar algorithm for the dfs approach as well? , But I really like this, feels intuitive

@jabir5768 2 года назад

HI ! Really nice explanation but I was wondering about the complexity why is it O(E+V) ? Shouldn't be O(V) since we iteratre of the nodes twice to set the degrees, then the while loop iterates exactly V times ?

@il5083 8 месяцев назад

Nice video. Is there a reason not to use Kahn's algorithm instead of the DFS topological sort in an interview since this is easier to memorize and code?

@akashshirale1927 3 года назад

can u post videos on identifying kadane's algorithm for dynamic programming

@andreyvalverde4780 2 года назад

hi there, quick question, based on the code, how do we make sure that we are not adding vertices that we've already visited?

@shashankbarole 2 года назад

Ohh I love this example 😂

@user-ks2db1nm1b 3 года назад

What drawing software to use？ The picture is very nice

@FaustoCarvalho Год назад

What tool have you used to draw and animate these graphs? Thanks

@nitika9769 8 месяцев назад

my Saviour

@RushOrbit Год назад

Where did you find the intro music for your videos?

@ManishaSingh-yk5en 2 года назад

Can we get the ppt which is being used in the video?

@shantanubapat6937 3 года назад

We have to loop through all vertices to find those who have in degree of zero. Can we optimize this using heap or priority queue?

@WhyAnkurGautam 2 года назад

We have to loop through once to find the vertices which have indegree of zero and put it in queue. After that we just have to pop the element and decrement in-degree of its dependent nodes. When you are decrementing you can check if it is zero or not. If it is zero than you can put that node into queue. This way you dont need priority queue. Only using queue will work in O(N+E) I guess.

@tarunstv796 Год назад

Will this approach also work for cyclic graphs? *When I say it will work, I mean it will let us determine whether the graph is cyclic or not, or if a DAG will provide valid ordering.

@JacksonSmith Год назад

u great

@europebasedvlogs1251 Год назад

WOW

@bullymaguire2335 Год назад

Dude just increase ur volume .no other complains .👍

@cardel-qq6xp 7 месяцев назад

Underwear -> pants -> shirt -> hoodie -> socks -> shoes -> school

@vm7240 2 года назад

What is the time complexity of calculating indegree? O(V^2) or O(V + E)? V = no of vertices E = no of edges Since there are two for loops, ig it should be v^2

@bharat_arora 3 года назад

Those who wear their pants before their underwear - are called Superheros !!

@76lunagogogo 2 месяца назад

Regarding the DAG, isn't the (3) also not he DAG as the same reason that (4) one has?

@benardkong Год назад

My son often puts his pants on before his underwear; sweater before shirt, just to go back to do it all over again. I think I forgot to install the TopSort algorithm for him.

@pankajpanwar9385 2 года назад

Even tho you say that the in-degree array has to be number of nodes the current index is connected to indegree[0] = 0 Actually in code it seems like you're populating the in-degree by adding the number of nodes connected to the current index indegree[0] = 3

@enlgn7050 3 года назад

Okay....Now I get it. Superman got his DAG messed up

@shaunaksharma42 21 день назад

This channel is amazing but youre a sick individual for putting on socks first before anything else

@bxfootballphenom 2 года назад

I've been running into a problem with this algorithm when there is no node 0. In this case, the inDegrees array will always have the 0th index be 0, and since there is no "0" node to add any incoming dependencies it will incorrectly add it to the queue. This also ends up breaking the rest of the algorithm since the true size of the inDegrees array is 1 less than what we were expecting. For example if our vertices are [1,2,3,4] the inDegree array at initialization will be [0,0,0,0] and will only match up to vertex 3, since at iteration it will be expecting i to start at 0. Has anyone else come across this and how have you solved this?

@WilliamFiset-videos 2 года назад

Hey Cesar, when labelling the nodes of the graph you should always label the first node as node 0, the second node as node 1, the third node as node 2 and etc... This should ensure that you always have a node 0, does this resolve your problem?

@bxfootballphenom 2 года назад

@@WilliamFiset-videos Thanks!