Hierholzer’s Algorithm

Hierholzer’s algorithm is another algorithm to find the Euler Path or Euler circuit in a graph. Fleury’s algorithm can also print the Euler Path in a graph but its time complexity is . Hierholzer’s algorithm can find Euler Path in linear time, .

How it works?

Suppose a graph G containing an Euler Circuit.

If we randomly traverse the graph without repeating edges, we will eventually end up on the same vertex BUT the path taken may or may not include all the edges. For example,

Suppose we traverse the above graph from v1. After some time, we reach v1 again. All edges attached to v1 are visited. We cannot proceed ahead. We found a circuit. But the circuit is not Euler Circuit as all edges are not visited.

Circuit: 1-2-3-4-5-6-1

Remove visited edges from the graph.

After removing the edges, the graph is now split into many components. You may have noticed that all the components contain Euler Circuit. This is because a graph is Euler if it contains all even degree vertices. The degree of every vertex in a cycle is also even. The degree of vertices after removing a cycle remains even.

After that, we find a new Euler Circuit in components with more than one vertex. The new circuit must start from a vertex which was part of the previous cycles, i.e., from v2 or v6.

Let v6 be the starting vertex. The Euler circuit is 6-7-2-6.

Now, we have 2 Euler circuits,

• 1-2-3-4-5-6-1
• 6-7-2-6

On combining them, we get 1-2-3-4-5-(6-7-2-6)-1

In this way, we keep finding and combining the Euler Circuits until all the edges are removed from the graph.

Note: The logic to find Euler Path is similar. The only difference is we must start from an odd degree vertex.

Steps

1. First, make sure that the input graph G is connected and contains exactly 0 or 2 odd degree vertices.
2. Initialize 2 stack. The first stack will store the temporary Euler Path – let’s call it cpath. The second stack will store the final Euler path – let’s call it epath.
3. Let the starting vertex be v. If the graph contains exactly 2 odd degree vertices then one of them should be the starting vertex. If the graph contains exactly 0 odd degree vertices then any vertex can be starting vertex.
4. Push v to cpath.
5. Let u = cpath.TOP.
6. If all the edges from u are visited, pop u from cpath and push it to epath.
7. If all edges from u are not visited, select any random edge (u, x). Push x to cpath and delete the edge (u, x) from G.
8. Repeat steps 5 to 7 until cpath is empty.

The final Euler path will be saved in epath.

Let’s discuss what exactly we are doing in the above steps. Basically, we are doing a depth-first search on the graph but instead of immediately removing the vertices from the stack, we pop the vertices from the stack only if all the edges from that vertex are visited.

By doing so, we are basically finding the simple circuits in the graph and combining them into a single big circuit.

If you are still confused about why the algorithm works, read the How it Works? section again and perform the algorithm on the graph in that section. Also, feel free to comment.

Step by Step Example

We will perform Hierholzer’s Algorithm step by step on the graph below.

1. Initialize 2 stack – cpath and epath.
2. Since the graph contains no odd degree vertices. Any vertex can be a starting vertex. Let the starting vertex be 1.
3. Push 1 to cpath.

1. The top of cpath is 1.
2. Choose any edge from 1.
3. Let (1, 2) be the chosen edge.
4. Push 2 to cpath.
5. Delete edge (1, 2) from the graph.

1. The top of cpath is 2.
2. Choose any edge from 2.
3. Let (2, 3) be the chosen edge.
4. Push 3 to cpath.
5. Delete edge (2, 3) from the graph.

1. The top of cpath is 3.
2. Choose any edge from 3.
3. Let (3, 6) be the chosen edge.
4. Push 6 to cpath.
5. Delete edge (3, 6) from the graph.

1. The top of cpath is 6.
2. Choose any edge from 6.
3. Let (6, 1) be the chosen edge.
4. Push 1 to cpath.
5. Delete edge (6, 1) from the graph.

1. The top of cpath is 1.
2. Choose any edge from 1.
3. No edge is attached to 1.
4. Pop 1 from cpath.
5. Push 1 to epath.

1. The top of cpath is 6.
2. Choose any edge from 6.
3. No edge is attached to 6.
4. Pop 6 from cpath.
5. Push 6 to epath.

1. The top of cpath is 3.
2. Choose any edge from 3.
3. No edge is attached to 3.
4. Pop 3 from cpath.
5. Push 3 to epath.

1. The top of cpath is 2.
2. Choose any edge from 2.
3. Let (2, 4) be the chosen edge.
4. Push 4 to cpath.
5. Delete edge (2, 4) from the graph.

1. The top of cpath is 4.
2. Choose any edge from 4.
3. Let (4, 5) be the chosen edge.
4. Push 5 to cpath.
5. Delete edge (4, 5) from the graph.

1. The top of cpath is 5.
2. Choose any edge from 5.
3. Let (5, 2) be the chosen edge.
4. Push 2 to cpath.
5. Delete edge (5, 2) from the graph.

No edge is left in the graph so the algorithm will simply pop all vertices from cpath and push them to epath.

FInal epath: 1-6-3-2-5-4-2-1 is an Euler Circuit in the given graph.

Program for Undirected Graph

Note: The graph in the above example is taken as the input

#include<iostream>
#include<vector>
#include<stack>
#include<unordered_map>
using namespace std;

class Graph{
	
	int vertex; // number of vertices
	// adjacency list
	// we are using unordered_map to speed up the deletion of edges
	vector<unordered_map<int,int>> adj;
	
	public:
		
		// constructor to initialize graph
		// set number of vertices to v
		// initialize adjacency map for v nodes
		Graph(int v){
			vertex = v;
			adj = vector<unordered_map<int,int>>(v+1);
		}
		
		// add edge (u, v) to graph
		void addEdge(int u, int v){
			adj[u][v] = 1;
			adj[v][u] = 1;
		}
		
		// remove edge (u, v) from the graph
		void removeEdge(int v,int u){
			adj[v].erase(u);
			adj[u].erase(v);
		}
		
		// function checks if the graph contains a euler path/circuit or not
		// if the graph is valid, then it calls another function printEuler()
		// to print Euler Path or circuit
		void printEulerPathCircuit(){
			
			int odd = 0; // number of vertices with odd degree
			int oddVertex = 0; // it stores vertex with odd degree if it exists
			
			for(int i=1;i<=vertex;++i){
				if(adj[i].size()%2==1){
					++odd;
					oddVertex = i;
				}
			}
			
			if(odd==0){
				// if the number of odd degree vertices is 0
				// the graph contains a Euler Circuit
				// we can use any vertex as the starting vertex
				cout<<"Euler Circuit: ";
				// print euler circuit with '1' as the starting vertex
				printEuler(1);
			}
			else if(odd==2){
				// if the number of odd degree vertices is 0
				// the graph contains a Euler Path
				// starting vertex should be of odd degree
				cout<<"Euler Path: ";
				printEuler(oddVertex);
			}
			else{
				cout<<"Euler Path/Circuit Doesn't Exist"<<endl;
			}
			
		}
		
		// the function to print euler path or circuit
		void printEuler(int v){
			
			stack<int> cpath;	// current path
			stack<int> epath;	// euler path
			
			cpath.push(v);		// euler path starts from v
			
			while(!cpath.empty()){
				int u = cpath.top();
				
				if(adj[u].size()==0){
					// if all edges from u are visited
					// pop u and push it to euler path	
					epath.push(u);
					cpath.pop();
				}
				else{
					// if all edges from u are not visited
					// select any edge (u, v)
					// push v to current path and remove edge (u, v) from the graph
					cpath.push(adj[u].begin()->first);
					removeEdge(u,adj[u].begin()->first);
				}	
			}
			
			while(!epath.empty()){
				cout<<" "<<epath.top()<<" ";
				epath.pop();
			}
			
		}
		
};

int main()
{
	// graph G, containing 6 vertices from 1 to 6.
	Graph G(6);
	
	// adding edges to the graph
	// this graph is same as the graph we used in the above example
	// we are assuming graph is connected and undirected
	G.addEdge(1, 6);
	G.addEdge(6, 3);
	G.addEdge(3, 2);
	G.addEdge(2, 1);
	G.addEdge(2, 5);
	G.addEdge(5, 4);
	G.addEdge(4, 2);
	
	// function to print Euler Path or Euler Circuit
	G.printEulerPathCircuit();
}

Output

Euler Circuit: 1 2 5 4 2 3 6 1

Program for Directed Graph

The main difference between an undirected and directed graph program is the way we check if the graph contains Euler Path/Circuit or not.

Note: The final graph in the example section is the input.

#include<iostream>
#include<vector>
#include<stack>
#include<unordered_map>
using namespace std;

class Graph {

	int vertex; // number of vertices
	vector<unordered_map<int, int>> adj; // adjacency list
	// store degree of each vertex
	// negative value means indegree more than outdegree
	// positive value means outdegree more than indegree
	vector<int> degree;

public:

	// constructor to initialize graph
	// set number of vertices to v
	Graph(int v) {
		vertex = v;
		adj = vector<unordered_map<int, int>>(v + 1);
		degree = vector<int>(v + 1, 0);
	}

	// add edge (u, v) to graph
	void addEdge(int u, int v) {
		adj[u][v] = 1;
		degree[u]++;
		degree[v]--;
	}

	// remove edge (u, v) from the graph
	void removeEdge(int u, int v) {
		adj[u].erase(v);
		degree[u]--;
		degree[v]++;
	}

	// function checks if the graph contains a euler path/circuit or not
	// if the graph is valid, then it calls printEuler()
	// to print Euler Path or circuit
	void printEulerPathCircuit() {

		// start : vertex with indegree + 1 = outdegree
		// indeg : number of vertices with indegree 1 more than outdegree
		// outdeg: number of vertices with outdegree 1 more than indegree
		int start, end, indeg, outdeg;
		start = -1;
		indeg = outdeg = 0;

		for (int i = 1; i <= vertex; ++i) {
			if (degree[i] == -1 && indeg == 0) {
				++indeg;
			}
			else if (degree[i] == 1 && outdeg == 0) {
				++outdeg;
				start = i;
			}
			else if (degree[i] != 0) {
				cout << "Euler Path/Circuit Doesn't Exist" << endl;
				return;
			}
		}

		if (indeg == 1 && outdeg == 1) {
			// graph contains 1 vertex with indegree = outdegree + 1
			// and 1 vertex with outdegree = indegree + 1
			// thereforce, the graph must contain a euler path
			cout << "Euler Path: ";
			// the euler path starts from vertex with outdegree = indegree + 1
			printEuler(start);
		}
		else {
			// graphs contains all vectices with indegree == outdegree
			// thereforce, the graph must contain a euler circuit
			cout << "Euler Curcuit: ";
			// euler circuit can start from any edge
			printEuler(1);
		}

	}

	// the function to print euler path or circuit
	void printEuler(int v) {

		stack<int> cpath;	// current path
		stack<int> epath;	// euler path

		cpath.push(v);		// euler path starts from v

		while (!cpath.empty()) {
			int u = cpath.top();

			if (adj[u].size() == 0) {
				// if all edges from u are visited
				// pop u and push it to euler path	
				epath.push(u);
				cpath.pop();
			}
			else {
				// if all edges from u are not visited
				// select any edge (u, v)
				// push v to current path and remove edge (u, v) from the graph
				cpath.push(adj[u].begin()->first);
				removeEdge(u, adj[u].begin()->first);
			}
		}

		while (!epath.empty()) {
			cout << " " << epath.top() << " ";
			epath.pop();
		}

	}

};

int main()
{
	// graph G, containing 6 vertices from 1 to 6.
	Graph G(6);

	// adding edges to the graph
	// this graph is same as the final graph in the example section
	G.addEdge(1, 6);
	G.addEdge(6, 3);
	G.addEdge(3, 2);
	G.addEdge(2, 1);
	G.addEdge(2, 5);
	G.addEdge(5, 4);
	G.addEdge(4, 2);

	// function to print Euler Path or Euler Circuit
	G.printEulerPathCircuit();
}

Output

Euler Curcuit: 1 6 3 2 5 4 2 1

Time Complexity

We are visiting each edge of the graph exactly once. Deleting an edge takes time.

Read
Euler Path and Euler Circuit
Bipartite Graph
Fleury’s algorithm

References
Hierholzer’s algorithm