Eulerian Path/Circuit algorithm (Hierholzer's algorithm) | Graph Theory

[@SachinYadav-vl2wi]

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 :)

[@mingjunzhang]

this is best video to explain Hierholzer’s Algorithm, thanks!

[@devanshmesson2777]

This is the finest youtube channel which teaches a concept with such clarity and simplicity! Loved it!

[@FrankZChen]

I cannot express how much I appreciate the course on Hierholzer's algorithm and UnionFind.

[@shobhittrivedi435]

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_bam]

yo, this is THE BEST Eulerian Path video. good job and thank you!

[@ankushgupta630]

You are literally the best teacher , please make more !

[@cowbeer0834]

Best explanation for this problem I've seen so far.

[@AbhishekVaid]

To practice: leetcode.com/problems/reconstruct-itinerary/

[@yoyobaby2227]

thank you very much It meant a lot for my interview

[@parthsaraswat9744]

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!

[@vijaykrishnagurunathan3142]

Thank you for your video. The implementation was really neat :D

[@muhammadshakhawathossain7025]

Excellent explanation. Thank you!

[@sakuragi1111]

Bravo! Thank you so much!

[@AnandKumar-kz3ls]

this is soo good just stick to the basics

[@navyasm]

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.

[@xenowits]

the examples and pseudo code u put are awesome!!

[@ashishnarang2751]

Awesome explanation ! Thanks so much !! :)

[@AidarMHTV]

Thanks, that is the best explanation

[@hardikchawla4966]

You just earned a subscriber

[@NJVorwerck]

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.

[@bin2608]

Thank you William!

[@laurent__9032]

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!

[@harveenkaur1257]

Very helpful video! Thanks :)

[@jianingzhuang104]

Great video! Thanks!

[@v_iancu]

Hold on, why are there two edges directed from 2 to 4? Shouldn't one of them be reversed?

[@adameruf3267]

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!

[@BiswarupMukherjeeBCE]

Is it possible to implement hierholzer's algorithm for undirected graph?

[@chinesemimi]

undirected graph is basically a directed graph pointing in both directions, so yes

[@user-eq4oy6bk5p]

@@chinesemimi converting it to directed graph wouldn't work because it would have 2 edges between nodes instead of 1

[@vardhan254]

loved the video!!

[@rebelScience]

At 8:38, the way we go back from 3

[@imwinprn3038]

He went back from 3

[@chenjason2598]

Awesome !

[@akhilumeshmehendale6850]

Wow, the explanation is so good.

[@frazbakht4480]

This is good but you shouldve added an adjacency list so it's easier to understand the code

[@siddharth892]

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.

[@TheUmangTarang]

What a beauty!

[@BipinOli90]

It would be interesting to see you do through rundown of difficult competitive programming or coding problem.

[@asafsh2306]

william. u the man

[@narendrakjha8883]

@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-videos]

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 :)

[@narendrakjha8883]

​@@WilliamFiset-videos Thanks.

[@sailakshmivenkat7790]

Node number 2 has only 2 out degrees. at 3:08, please check the values and confirm.

[@sailakshmivenkat7790]

It is mentioned to have 3 out degrees.

[@vk7261]

@@sailakshmivenkat7790 2 -> 2 is the third edge

[@yjj.7673]

So great!!!

[@luojihencha]

this is magic!!!

[@LegitGamer2345]

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.

[@saurabhmaurya94]

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?

[@sourabhkhandelwal689]

Yes but make sure to remove the edge twice(considering both the nodes at source and destination once).

[@jasskaur8541]

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?

[@SensaiSaturas]

good shit

[@DR.Sailior]

🎉 thx

[@omnidp]

Bravo!

[@harshraj22_]

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 ).

[@tusharrawat8768]

Well, if you look carefully there's still an unvisted edge from 2 -> 4 in the graph.

[@adhishmalviya2408]

Wowwwwww!!!!!!!!

[@Sekaero]

you sound like the Cuber from adventure time

[@tanusreepaul7323]

Node 2 is wrong in the chart!

[@MinecraftMRCentral]

Can a graph with a single node have an Eulerian Path

[@srini2010srini]

If that node has at least one edge it is possible.

[@langli5550]

The path should be a sequence of edges rather than nodes. Sequence of node can't differentiate the edges of the same node.

[@a1988ditya]

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-videos]

Can you please file a bug and provide an adjacency list ordering that breaks this algorithm?

[@goodgoodstudy666]

black magic

[@niksgupta36]

1.25x speed!

[@maalikserebryakov]

Fifteen minutes to teach a simple algorithm?