Euler Path in a graph using Hierholzer's algorithm

We will discuss how to find the Euler path(path is a sequence of vertices connected by edges) in a graph. The assumption we are taking in this article is, the given graph is connected and there is a Euler path in the given graph, although we will discuss a criteria which will help us know if there is any Euler path in graph.
Moreover, we will present the pseudo code of one of the algorithm and pick up a problem and solve it using the algorithm discussed in the aricle.

Intro:

Definition: Euler path is a path such that we travel all the edges of the graph exactly once (repetion of vertices is allowed).

Euler path example

In the above example, one of the Euler path is: 1,2,3,4,2,6,2,5
Euler path can be a closed path i.e. a cycle also called Euler circuit or it can be an open path as in the above example aslo called Euler walk.

Prerequisite

Degree of a vertex:

Undirected graph - Number of edges incident on a vertex is the degree of a vertex.
Directed graph - Sum of edges going in and coming out of a vertex. A more granular definition is, indegree which means number edges going in to a vertex and outdegree which means number of edges going out of a vertex

Criteria for existence of Euler path:

Undirected graph - Either all the vertices must have even degree(in this case it is a Euler circuit) if not then exactly two vetices can have odd degree and other with even degrees(in the latter case, the vertices with odd degree are start and end of the Euler path which is also a Euler walk).

Directed graph - For each vertex, outdegrees must be equal to indegrees(in this case it is a Euler circuit) or exactly two vertices must have 1 more outdegree than indegrees.
Proof of the above criteria is not covered as part of this article inorder to stick to the title of the article.

Intuition and algorithm

Intuition:

The Euler path can be either a cycle(called Euler circuit) or not a cycle(called a Euler walk).

In case of a cycle, when tracing a path starting from any vertex, we must come back to the start vertex. This will always be possible in case of a Euler circuit(or cycle) because every vertex has even degree(equal indegree and outdegree in case of a directed graph), which means that we will always be able to exit a vertex if we enter it and cannot get stuck at any intermediate vertex.

In case of not a cycle, we should make sure to start tracing the path from a valid start vertex. The valid start vertex in Euler walk will be the vertices with odd degree(the vertex with 1 extra outdegree in case of a directed graph). The end of the walk will be at the other vertex with odd degree(remember the criteria, there will be exactly two vertices with odd degree incase of undirected graph) (the vertex with 1 extra indegree in case of directed graph).

It is now relatively easy to come up with an approach which can construct a Euler path if it exists in a graph.

Find out the start vertex:
1. Undirected graph:
  1. All the vertices have even degree - any vertex can be a start vertex.
  2. Exactly two vertices have odd degree - either of the two can be a start vertex.
2. Directed graph:
  1. All the vetices have equal number of indegree and outdegree - any vertex can be a start vertex.
  2. There is one vertex for which outdgree == indegree+1, one vertex with outdegree+1 == indegree and all the other vertices with equal number of indegree and outdegree - The vertex with outdegree == indegree+1 will be the start vertex.
After we know the start vertex, we need to find a way to construct Euler path. Refer to the below diagram, there are some observations which we can make. If the graph has degree==2 for every vertex then it will always be of the type as in image: a. If the graph has exactly two vertices with degree==1 and remaining all the vetices with degree==2 then the graph will be of type as in image: b.
In the previous two scenarios we can start from the start vertex and just keep following the current vertex's neighbor to create a Euler path and it would cover all the edges(taking start vertex in image:a as 1 and start vertex in image:b as 1).

Now let's think of a general graph which can have a Euler cycle, these could be represented by the graphs in the image c and d. If we start from the start vertex(i.e. node 1 in both image c and d) and keep visiting its neighbors and mark the current vertex as visited only if all its edges have been used up(i.e. we use an edge to move to a vertex's neightbor).

The order in which the vertices get visited for graph c and d are:
Traversal for graph c: 1, 3, 2, 1, 4, 5, 1
Traversal for graph d: 3, 2, 6, 5, 4, 2, 1

If we reverse these traversals we have following results:
Reversed traversal for graph c: 1, 5, 4, 1, 2, 3, 1
Reversed traversal for graph d: 1, 2, 4, 5, 6, 2, 3

And we just found a Euler path for the graphs under consideration!
(Note: There can be multiple Euler paths, we just mentioned one of them.)
Hierholzer’s Algorithm intuition example images

Also, if we notice, the graph in image: c has a Euler cycle whereas the graph in image: d is a Euler walk.

Why does the above method work?

Let's take an example of an undirected graph which has a Euler walk and except for the start and end vertex all have a degree==2 while the start and end vertex have degree==1. If we start from the start vertex(the vertex with the odd degree) and keep moving by using an unvisited edge, we will finally arrive at the end vertex(the other vertex with the odd degree). Now any other graph with a Euler walk with more complexity(vertices with degree more than 1 or 2) can be create using this minimal graph i.e. graph in image a can be transformed to graph in image c. So if we keep moving forward as much as possible and mark a vertex visited only after all its edges have been visited then order in which the vertices get visited will give a Euler walk in reverse order(there will be cycles originating from some vertex and that vertex will be marked visited only after the cycle originating from it is traversed).

Hierholzer's algorithm:

What we discussed is a well known algorithm to find Euler path in a graph. Following is a psudocode for undirected graph. It is not difficult to write a pseudo code for directed graph if the concept is clear.

Pseudo code

            // graph = take as console input/ read from a file
            assert if graph has a Euler path // easy to write a routine for this
            eulerPath = new LinkedList
            startVertex = findStartVertex(graph) // routine as per the criteria mentioned in point 1
            
            // routine to find euler path
            eulerPathRoutine(graph, curentVertex, eulerPath):
                for(neighbor: graph.getNeighbor(currentVertex)):
                    graph.removeEdge(currentVertex, neighbor)
                    eulerPathRoutine(graph, neighbor)
                eulerPath.addAtFront(currentVertex)

Notice that we did explicitly mark any vertex as visited because all we need was the order in which they were getting visited. Adding to the front of the linkedlist helped us keeping the visted order in reverse order.

Example problem:

Reconstruct Itinerary

Discussion

It has been mentioned that all tickets form atleast one valid formation hinting towards a Euler path existence as a ticket cannot be reused. It is also clearly mentioned what is going to be the start vertex. The only variation from a standard Euler path finding problem is that the question wants an itinerary which is lexicographically ordered. This constraint can be solved if we use a priorty queue in our graph represented as an adjacency list and not just list. Following is the solution for reference:

class Solution {
    public List<String> findItinerary(List<List<String>> tickets) {
        Map<String, PriorityQueue<String>> graph = new HashMap<>();
        for(List<String> ticket: tickets) {
            PriorityQueue<String> l = graph.getOrDefault(ticket.get(0), new PriorityQueue<>());
            l.offer(ticket.get(1));
            graph.put(ticket.get(0), l);
        }
        LinkedList<String> ans = new LinkedList<>();
        dfs("JFK", graph, ans);
        return (List)ans;
    }

    private void dfs(String node, Map<String, PriorityQueue<String>> graph, LinkedList<String> cur) {
        PriorityQueue<String> arrivals = graph.getOrDefault(node, new PriorityQueue<>());
        while(!arrivals.isEmpty()) {
            dfs(arrivals.poll(), graph, cur);
        }
        cur.addFirst(node);
    }
}

Search This Blog

Self Aware Potato