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 :)
@mingjunzhang5 жыл бұрын
this is best video to explain Hierholzer’s Algorithm, thanks!
@devanshmesson27773 жыл бұрын
This is the finest youtube channel which teaches a concept with such clarity and simplicity! Loved it!
@FrankZChen6 ай бұрын
I cannot express how much I appreciate the course on Hierholzer's algorithm and UnionFind.
@shobhittrivedi4352 жыл бұрын
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.
@tori_bam3 жыл бұрын
yo, this is THE BEST Eulerian Path video. good job and thank you!
@ankushgupta6303 жыл бұрын
You are literally the best teacher , please make more !
@cowbeer08343 жыл бұрын
Best explanation for this problem I've seen so far.
@AbhishekVaid3 жыл бұрын
To practice: leetcode.com/problems/reconstruct-itinerary/
@yoyobaby22275 ай бұрын
thank you very much It meant a lot for my interview
@parthsaraswat97443 жыл бұрын
music at the start and end just holded me up
@uniquekatnoria5380 Жыл бұрын
great video, complex concept easily explained
@arthurlobo5727 Жыл бұрын
Thank you, this video helped me a lot!
@vijaykrishnagurunathan31425 жыл бұрын
Thank you for your video. The implementation was really neat :D
@muhammadshakhawathossain70252 жыл бұрын
Excellent explanation. Thank you!
@sakuragi11112 жыл бұрын
Bravo! Thank you so much!
@AnandKumar-kz3ls11 ай бұрын
this is soo good just stick to the basics
@navyasm2 жыл бұрын
for kzbin.info/www/bejne/bn7ToIJor6ZlopY, 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.
@xenowits5 жыл бұрын
the examples and pseudo code u put are awesome!!
@ashishnarang27512 жыл бұрын
Awesome explanation ! Thanks so much !! :)
@AidarMHTV3 жыл бұрын
Thanks, that is the best explanation
@hardikchawla49662 жыл бұрын
You just earned a subscriber
@NJVorwerck2 жыл бұрын
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.
@marceorigoni6614 Жыл бұрын
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.
@bin26084 жыл бұрын
Thank you William!
@laurent__90323 жыл бұрын
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!
@harveenkaur12574 жыл бұрын
Very helpful video! Thanks :)
@jianingzhuang1044 жыл бұрын
Great video! Thanks!
@v_iancu3 жыл бұрын
Hold on, why are there two edges directed from 2 to 4? Shouldn't one of them be reversed?
@adameruf32672 жыл бұрын
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
@globallama8094 Жыл бұрын
thanks mate!
@BiswarupMukherjeeBCE3 жыл бұрын
Is it possible to implement hierholzer's algorithm for undirected graph?
@chinesemimi2 жыл бұрын
undirected graph is basically a directed graph pointing in both directions, so yes
@user-eq4oy6bk5p2 жыл бұрын
@@chinesemimi converting it to directed graph wouldn't work because it would have 2 edges between nodes instead of 1
@vardhan254 Жыл бұрын
loved the video!!
@rebelScience4 жыл бұрын
At 8:38, the way we go back from 3
@imwinprn30383 жыл бұрын
He went back from 3
@chenjason2598 Жыл бұрын
Awesome !
@akhilumeshmehendale68505 жыл бұрын
Wow, the explanation is so good.
@frazbakht44804 жыл бұрын
This is good but you shouldve added an adjacency list so it's easier to understand the code
@siddharth8927 ай бұрын
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.
@TheUmangTarang11 ай бұрын
What a beauty!
@BipinOli906 жыл бұрын
It would be interesting to see you do through rundown of difficult competitive programming or coding problem.
@asafsh23064 жыл бұрын
william. u the man
@narendrakjha88834 жыл бұрын
@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.
@WilliamFiset-videos4 жыл бұрын
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 :)
@narendrakjha88834 жыл бұрын
@@WilliamFiset-videos Thanks.
@sailakshmivenkat77903 жыл бұрын
Node number 2 has only 2 out degrees. at 3:08, please check the values and confirm.
@sailakshmivenkat77903 жыл бұрын
It is mentioned to have 3 out degrees.
@vk72612 жыл бұрын
@@sailakshmivenkat7790 2 -> 2 is the third edge
@yjj.76735 жыл бұрын
So great!!!
@luojihencha3 жыл бұрын
this is magic!!!
@LegitGamer23453 жыл бұрын
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
@liaolii Жыл бұрын
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.
@saurabhmaurya944 жыл бұрын
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?
@sourabhkhandelwal6894 жыл бұрын
Yes but make sure to remove the edge twice(considering both the nodes at source and destination once).
@jasskaur85414 жыл бұрын
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}};
@GallaRajesh Жыл бұрын
I understand the algorithm, but why does it work?
@SensaiSaturas4 жыл бұрын
good shit
@DR.Sailior Жыл бұрын
🎉 thx
@omnidp5 жыл бұрын
Bravo!
@harshraj22_5 жыл бұрын
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 ).
@tusharrawat87684 жыл бұрын
Well, if you look carefully there's still an unvisted edge from 2 -> 4 in the graph.
@adhishmalviya24084 жыл бұрын
Wowwwwww!!!!!!!!
@Sekaero2 жыл бұрын
you sound like the Cuber from adventure time
@tanusreepaul7323 Жыл бұрын
Node 2 is wrong in the chart!
@MinecraftMRCentral4 жыл бұрын
Can a graph with a single node have an Eulerian Path
@srini2010srini3 жыл бұрын
If that node has at least one edge it is possible.
@langli55505 жыл бұрын
The path should be a sequence of edges rather than nodes. Sequence of node can't differentiate the edges of the same node.
@a1988ditya4 жыл бұрын
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/
@WilliamFiset-videos4 жыл бұрын
Can you please file a bug and provide an adjacency list ordering that breaks this algorithm?