Oh! I cannot tell you how many hours I scrolled through the different websites and still could not get a clear picture of the algorithm. Thanks to your video, all doubts are clear now. Thanks a lot for the wonderful content :)
Very well explained. There is a precondition though that needs to be mentioned - the graph is connected (the one considered is also disconnected but one of the island does not contain any edge). In the scenario of disconnect graph, only one island is a cluster of vertices and the other islands should not have edges as there would not be any way to reach that.
for ua-cam.com/video/8MpoO2zA2l4/v-deo.html, I don't think directed graph guarantees symmetry. out[i]-in[i] > 1 and in[i] - out[i] > 1 are 2 different cases. I think we need to check them both.
Isn't there an error in the video (or it is a bit confusing) during DFS at 3:36 ? Is it not supposed to backtrack from 6 to 5 and from 5 to 3 and then go from 3 to 2 ... Apart from that your work is amazing and will check your Udemy course!
I believe there is a slight bug with your graphHasEulerianPath() function. Your code assumes that you must have exactly one start and end node, or neither but it would also be valid to have one or the other as well. Simplest counter example is a basic cycle/circle with one node coming off it. That node could either be the starting point if it had an outgoing edge or the ending point if it had an incoming edge.
Think about it. If you add this new point with an outgoing edge, somebody, is getting one extra incoming one, If it has an incoming one somebody has an extra outgoing edge. If it had the same of incoming/outgoing then that one would be the end/start, as now will have one more incoming/outgoing. Of course there could be problems with more than one start/end or maybe a difference greater than 1, therefore the no existance of the path. If I understood what you said was essentially a doble linked list. Meaning vertices pointing to their immediate neighbors, and they to them. Guaranteeing everybody has same degree of outgoing/incoming.
Is it not similar to the Topological sorting using the DFS? Except that there is a cycles that are possible its like a combination of both Kahns algo and DFS for topological sort.
i have a question, what if the graph is disconnected, case where 2 nodes have different in and out degrees, such as 1 is start other is finished, but each of them is on a different part of the disconnected graph? then we execute the program on a graph with no solution and it could bug
@Willian Thanks for this series. quick question: is it possible to store the graph in List and still somehow perform the the line at 13:58 next_edge = g[at].get(--out[at]) in O(1). I believe it is not, but then wouldn't that increase overall time complexity of the algorithm? You said to simply iterate over the list if it is anything other than array/ArrayList, so that got me little confused.
I think you understand correctly, if you cannot do a lookup for the next edge then you need to do a search. The search would of course increase the time it takes the find the edge, but that shouldn't stop you from using a List :)
What will be the adjacency list representation for this graph as there are two edges from node 2 to 4, so do we need to write 2 instead of 1? Will it be like this: {{0, 1, 1, 0, 0, 0}, {0, 1, 0, 2, 0, 0}, {1, 1, 0, 0, 1, 0}, {0, 0, 0, 0, 0, 1}, {0, 0, 1, 0, 0, 0}};
So people have been suggesting changes in this code/ algo for undirected graph but i think for undirected graph lets say that we are given two edges u and v with bidirectional edge and if we make a directed graph either from u->v for from v->u , either one of those , then I think the exact same algorithm should work basically do not consider it a bidirectional edge consider it to be single direction please correct me if I am wrong
A bit late, but that doesn't work because if you create two edges to represent a single undirected edge, the algorithm will think it can use that edge twice when in reality it can only use it once.
So just to confirm, this would work for an undirected graph too right? We'd just have the notion of bidirectional edges instead of in and out edges but we could use that to do a similar approach?
Suppose our DFS takes edges in this sequence : 1 3 1 2 2 4 3 2. Now we are ar node 2 with no unvisited edges. Should we add 2 into solution now ? ( The last element of our solution vector will be 2 in that case ).
7:26 Lets say in DFS you chose path 1-2-2-4-6-3-5-6 , now u hit a deadend so u print 6, now u backtrack to 5 which again is a dead end so you print 5 so i don't think this is the right algo. It so happened that u showed the right dfs path which is the solution. I read - www.geeksforgeeks.org/fleurys-algorithm-for-printing-eulerian-path/
Oh! I cannot tell you how many hours I scrolled through the different websites and still could not get a clear picture of the algorithm. Thanks to your video, all doubts are clear now.
Thanks a lot for the wonderful content :)
this is best video to explain Hierholzer’s Algorithm, thanks!
This is the finest youtube channel which teaches a concept with such clarity and simplicity!
Loved it!
I cannot express how much I appreciate the course on Hierholzer's algorithm and UnionFind.
Very well explained.
There is a precondition though that needs to be mentioned - the graph is connected (the one considered is also disconnected but one of the island does not contain any edge).
In the scenario of disconnect graph, only one island is a cluster of vertices and the other islands should not have edges as there would not be any way to reach that.
yo, this is THE BEST Eulerian Path video. good job and thank you!
You are literally the best teacher , please make more !
Best explanation for this problem I've seen so far.
To practice: leetcode.com/problems/reconstruct-itinerary/
thank you very much
It meant a lot for my interview
great video, complex concept easily explained
At 8:38, the way we go back from 3
He went back from 3
Thank you for your video. The implementation was really neat :D
Thank you, this video helped me a lot!
the examples and pseudo code u put are awesome!!
Excellent explanation. Thank you!
music at the start and end just holded me up
this is soo good just stick to the basics
Thanks, that is the best explanation
Bravo! Thank you so much!
Awesome explanation ! Thanks so much !! :)
You just earned a subscriber
Thank you William!
Very helpful video! Thanks :)
for ua-cam.com/video/8MpoO2zA2l4/v-deo.html, I don't think directed graph guarantees symmetry. out[i]-in[i] > 1 and in[i] - out[i] > 1 are 2 different cases. I think we need to check them both.
loved the video!!
Great video! Thanks!
Isn't there an error in the video (or it is a bit confusing) during DFS at 3:36 ? Is it not supposed to backtrack from 6 to 5 and from 5 to 3 and then go from 3 to 2 ...
Apart from that your work is amazing and will check your Udemy course!
Awesome !
thanks mate!
Is it possible to implement hierholzer's algorithm for undirected graph?
undirected graph is basically a directed graph pointing in both directions, so yes
@@chinesemimi converting it to directed graph wouldn't work because it would have 2 edges between nodes instead of 1
I believe there is a slight bug with your graphHasEulerianPath() function. Your code assumes that you must have exactly one start and end node, or neither but it would also be valid to have one or the other as well. Simplest counter example is a basic cycle/circle with one node coming off it. That node could either be the starting point if it had an outgoing edge or the ending point if it had an incoming edge.
Think about it. If you add this new point with an outgoing edge, somebody, is getting one extra incoming one, If it has an incoming one somebody has an extra outgoing edge. If it had the same of incoming/outgoing then that one would be the end/start, as now will have one more incoming/outgoing. Of course there could be problems with more than one start/end or maybe a difference greater than 1, therefore the no existance of the path.
If I understood what you said was essentially a doble linked list. Meaning vertices pointing to their immediate neighbors, and they to them. Guaranteeing everybody has same degree of outgoing/incoming.
william. u the man
What a beauty!
Is it not similar to the Topological sorting using the DFS? Except that there is a cycles that are possible its like a combination of both Kahns algo and DFS for topological sort.
Wow, the explanation is so good.
i have a question, what if the graph is disconnected, case where 2 nodes have different in and out degrees, such as 1 is start other is finished, but each of them is on a different part of the disconnected graph? then we execute the program on a graph with no solution and it could bug
Hold on, why are there two edges directed from 2 to 4? Shouldn't one of them be reversed?
So great!!!
This is good but you shouldve added an adjacency list so it's easier to understand the code
this is magic!!!
It would be interesting to see you do through rundown of difficult competitive programming or coding problem.
I understand the algorithm, but why does it work?
@Willian Thanks for this series.
quick question: is it possible to store the graph in List and still somehow perform the the line at 13:58
next_edge = g[at].get(--out[at])
in O(1). I believe it is not, but then wouldn't that increase overall time complexity of the algorithm?
You said to simply iterate over the list if it is anything other than array/ArrayList, so that got me little confused.
I think you understand correctly, if you cannot do a lookup for the next edge then you need to do a search. The search would of course increase the time it takes the find the edge, but that shouldn't stop you from using a List :)
@@WilliamFiset-videos Thanks.
Node number 2 has only 2 out degrees. at 3:08, please check the values and confirm.
It is mentioned to have 3 out degrees.
@@sailakshmivenkat7790 2 -> 2 is the third edge
Bravo!
What will be the adjacency list representation for this graph as there are two edges from node 2 to 4, so do we need to write 2 instead of 1? Will it be like this:
{{0, 1, 1, 0, 0, 0},
{0, 1, 0, 2, 0, 0},
{1, 1, 0, 0, 1, 0},
{0, 0, 0, 0, 0, 1},
{0, 0, 1, 0, 0, 0}};
🎉 thx
So people have been suggesting changes in this code/ algo for undirected graph
but i think for undirected graph lets say that we are given two edges u and v with bidirectional edge
and if we make a directed graph either from u->v for from v->u , either one of those , then I think the exact same algorithm should work
basically do not consider it a bidirectional edge consider it to be single direction
please correct me if I am wrong
A bit late, but that doesn't work because if you create two edges to represent a single undirected edge, the algorithm will think it can use that edge twice when in reality it can only use it once.
good shit
So just to confirm, this would work for an undirected graph too right? We'd just have the notion of bidirectional edges instead of in and out edges but we could use that to do a similar approach?
Yes but make sure to remove the edge twice(considering both the nodes at source and destination once).
Suppose our DFS takes edges in this sequence : 1 3 1 2 2 4 3 2. Now we are ar node 2 with no unvisited edges. Should we add 2 into solution now ? ( The last element of our solution vector will be 2 in that case ).
Well, if you look carefully there's still an unvisted edge from 2 -> 4 in the graph.
Wowwwwww!!!!!!!!
you sound like the Cuber from adventure time
Node 2 is wrong in the chart!
Can a graph with a single node have an Eulerian Path
If that node has at least one edge it is possible.
7:26 Lets say in DFS you chose path 1-2-2-4-6-3-5-6 , now u hit a deadend so u print 6, now u backtrack to 5 which again is a dead end so you print 5 so i don't think this is the right algo. It so happened that u showed the right dfs path which is the solution.
I read - www.geeksforgeeks.org/fleurys-algorithm-for-printing-eulerian-path/
Can you please file a bug and provide an adjacency list ordering that breaks this algorithm?
black magic
1.25x speed!
The path should be a sequence of edges rather than nodes. Sequence of node can't differentiate the edges of the same node.
Fifteen minutes to teach a simple algorithm?