@11:54 : It should be "Afterwards loop through all the *nodes* (not edges) of the graph and add all the nodes with an incoming degree of 0" This is a brilliant series. You teach in concise and clear manner. I first studied graphs in 2003 at college but never understood it and had great fear in the mind for graph problems. I found a great teacher after 21 years and I understand it easily. Thank you very much.
Not to undermine William but there’s UA-cam channel “Inside Code”, he explains lot of concepts pretty well. He has dynamic programming content as well. Also a Udemy course on dynamic programming
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.
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.
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.
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.
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 ?
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.
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
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.
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?
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
python3 implementation: graph = [[1, 2, 3], [5], [], [], [2, 3], [2]] queue, in_degree, ordering, index = list(), [0] * len(graph), [-1] * len(graph), 0 for Neighbour in graph: for To in Neighbour: in_degree[To] += 1 for i in range(len(graph)): if in_degree[i] == 0: ordering[index] = i queue.append(i) index += 1 for node in queue: for neighbour in graph[node]: in_degree[neighbour] -= 1 if in_degree[neighbour] == 0: queue.append(neighbour) ordering[index] = neighbour index += 1 print(ordering if index == len(graph) else 'cycle detected')
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.
Repeated the same feat, UA-cam recommendation to the rescue. PS Thanks @WilliamFiset
@@Aldrin32f did the same and now I am here😁
I just now Solved Course Schedule II on leetcode using this algo
My favourite ordering is to Keep Sleeping.
TIL Superman didn't know topological sort
@11:54 : It should be "Afterwards loop through all the *nodes* (not edges) of the graph and add all the nodes with an incoming degree of 0"
This is a brilliant series. You teach in concise and clear manner. I first studied graphs in 2003 at college but never understood it and had great fear in the mind for graph problems. I found a great teacher after 21 years and I understand it easily. Thank you very much.
William, really appreciate your effort in making this Video! Effort behind this Animation is awesome, explanation is awesome too!
Clean and concise explanation. Easy to comprehend and remember. Thank you!
The way you explained is simply superb!! especially the "getting ready for school" example..
Really takes an effort to make it sooooooooooooo
SIMPLE🙏🙏🙏🙏🙏🙌🙌🙌🙌🙌
What an example to start with. Thanks for not starting with gibberish numbers. This makes more sense than all the other videos
Thank you for a very clear explanation. Implementation was easy once I grasped the concept you've laid out in this video.
Was following a course and couldn't understand this concept there but this video was so simple and better explained
This video helped a lot since before I would constantly wake up in the morning and put on my school before my socks
Лучший канал по алгоритмам! Thank you William!
just looking at the playlists you made motivates me
Your videos and your teaching style are amazing!!
Thanks! It is great to see how the algorithm works in practice.
Wow great explanation in only 13 mins!
amazing explanation and visualization of the algorithm! a video unlike no other
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.
That would surely be the best DP course on UA-cam. I love how he explains
Not to undermine William but there’s UA-cam channel “Inside Code”, he explains lot of concepts pretty well. He has dynamic programming content as well. Also a Udemy course on dynamic programming
The freecodecamp video from Alvin Zablan on DP is as good as it gets
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.
Thanks William for the visualization and Animation! I clearly understand the concept now!
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.
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.
Wow. I understood that. Great way of teaching. You’re amazing. Thank you, sir.
great explanation as always. please make a video on segment trees next! such a powerful yet simple data structure
I'm about to binge watch all your videos. Thanks for the awesome content!
Great clarity - quality content.
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
this is 1 on 1 teaching i believe
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)
Easy and simple. Marvelous.
Animation you conduct has heart beat sound as background. I like it :)
That was a great example(dressing up) at the start of video.
10/10 beautifully explained!
Thank you so much, it is the most clear explanation I've found.
thank you so much William! this is extremely helpful for beginners!
Thank you Wiliam, I finally understand what Topological Sort is!
Very nice explanation. please make a video on articulation point and bridges
Keep it up William. May you reach million subs next year !
I recommend this.........to all the before_watching_read_comments_section people 🙌🙌🙌
Thank you so much, I really appreciate your video. Please continue...
amazing explanation!
FANTASTIC. The problem with DFS on topological sort is that the recursion is too expensive, BFS is faster in all other aspects
Alternatively, we can implement the DFS topological sort algo, using stack.
Thanks Mr. Fiset really awesome explanation
this is 100 times better than my algo professor
Nicely explained - thanks for this.
Awesome content! Thank you for putting in so much effort. Appreciate it!
thanks for explaning this so clearly!!
It was clear, thanks again man
Good as always. So easy to understand.
Thanks this video helped me optimize my sort code for leetcode course scheduling
Kahn : Implements Topological Sort.
Superman : Am i a joke to you ? Wears underwear after pants.
This video is a gem, thanks! You have a new fan :)
Very nice explanation. Thanks
Thank you for your video, great explanation!
This was awesome! Subscribed!
Nice animation and great explanation, thank you
Underwear -> pants -> shirt -> hoodie -> socks -> shoes -> school
Thanks, You explained it really perfectly
Best explanation ever, thank you!
Awesome, keep it up!
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.
beautiful explanation .. keep up the good work.. subscribed as well
Thanks a lot man! I really appreciate your work!
Excellent content.!
just realized you have a similar algorithm for the dfs approach as well? , But I really like this, feels intuitive
great video! Thanks man!
Thank you for this awesome video!
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 ?
holy shit this was such a great explanation, tysm!!
wonderful explanation, thanks man:)
You're the best man
Great Video!
Beautiful
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.
Dude just increase ur volume .no other complains .👍
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
very good video
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?
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.
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?
What is run time , O(V+E) ? can someone explain line by line using the pseudocode if possible
최고의 영상
my Saviour
amazing.
Thanks!
Amazing
Nice video, how is this different from another video you have on top sort using dfs?
underwear --> pants --> shirt --> hoodie --> socks --> shoes --> school
great vid
Awsm!
What tool have you used to draw and animate these graphs? Thanks
can u post videos on identifying kadane's algorithm for dynamic programming
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
Regarding the DAG, isn't the (3) also not he DAG as the same reason that (4) one has?
python3 implementation:
graph = [[1, 2, 3], [5], [], [], [2, 3], [2]]
queue, in_degree, ordering, index = list(), [0] * len(graph), [-1] * len(graph), 0
for Neighbour in graph:
for To in Neighbour:
in_degree[To] += 1
for i in range(len(graph)):
if in_degree[i] == 0:
ordering[index] = i
queue.append(i)
index += 1
for node in queue:
for neighbour in graph[node]:
in_degree[neighbour] -= 1
if in_degree[neighbour] == 0:
queue.append(neighbour)
ordering[index] = neighbour
index += 1
print(ordering if index == len(graph) else 'cycle detected')
MAH MANNN
Okay....Now I get it. Superman got his DAG messed up
Those who wear their pants before their underwear - are called Superheros !!
What drawing software to use？ The picture is very nice
Can we get the ppt which is being used in the video?
hi there, quick question, based on the code, how do we make sure that we are not adding vertices that we've already visited?