# 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
// we are using unordered_map to speed up the deletion of edges

public:

// constructor to initialize graph
// set number of vertices to v
// initialize adjacency map for v nodes
Graph(int v){
vertex = v;
}

// add edge (u, v) to graph
}

// remove edge (u, v) from the graph
void removeEdge(int v,int u){
}

// 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){
++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 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
}
}

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

// 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
// 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) {
degree[u]++;
degree[v]--;
}

// remove edge (u, v) from the graph
void removeEdge(int u, int 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 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
}
}

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

// 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. References
Hierholzer’s algorithm

### 1 thought on “Hierholzer’s Algorithm”

1. Nurgazy Nazhimidinov

Awesome article! It cleared many things that I didn’t understand from other articles.