Open In App

Hierholzer’s Algorithm for directed graph

Last Updated : 14 Feb, 2023
Improve
Improve
Like Article
Like
Save
Share
Report

Given a directed Eulerian graph, print an Euler circuit. Euler circuit is a path that traverses every edge of a graph, and the path ends on the starting vertex. Examples:

Input : Adjacency list for the below graph

Output : 0 -> 1 -> 2 -> 0 

Input : Adjacency list for the below graph

Output : 0 -> 6 -> 4 -> 5 -> 0 -> 1 
         -> 2 -> 3 -> 4 -> 2 -> 0 
Explanation:
In both the cases, we can trace the Euler circuit 
by following the edges as indicated in the output.

We have discussed the problem of finding out whether a given graph is Eulerian or not. In this post, an algorithm to print the Eulerian trail or circuit is discussed. The same problem can be solved using Fleury’s Algorithm, however, its complexity is O(E*E). Using Hierholzer’s Algorithm, we can find the circuit/path in O(E), i.e., linear time. Below is the Algorithm: ref ( wiki ). Remember that a directed graph has a Eulerian cycle if the following conditions are true (1) All vertices with nonzero degrees belong to a single strongly connected component. (2) In degree and out-degree of every vertex is the same. The algorithm assumes that the given graph has a Eulerian Circuit.

  • Choose any starting vertex v, and follow a trail of edges from that vertex until returning to v. It is not possible to get stuck at any vertex other than v, because indegree and outdegree of every vertex must be same, when the trail enters another vertex w there must be an unused edge leaving w. The tour formed in this way is a closed tour, but may not cover all the vertices and edges of the initial graph.
  • As long as there exists a vertex u that belongs to the current tour, but that has adjacent edges not part of the tour, start another trail from u, following unused edges until returning to u, and join the tour formed in this way to the previous tour.

Thus the idea is to keep following unused edges and removing them until we get stuck. Once we get stuck, we backtrack to the nearest vertex in our current path that has unused edges, and we repeat the process until all the edges have been used. We can use another container to maintain the final path. Let’s take an example:

Let the initial directed graph be as below


Let's start our path from 0.
Thus, curr_path = {0} and circuit = {}
Now let's use the edge 0->1 

Now, curr_path = {0,1} and circuit = {}
similarly we reach up to 2 and then to 0 again as

Now, curr_path = {0,1,2} and circuit = {}
Then we go to 0, now since 0 haven't got any unused
edge we put 0 in circuit and back track till we find
an edge

We then have curr_path = {0,1,2} and circuit = {0}
Similarly, when we backtrack to 2, we don't find any 
unused edge. Hence put 2 in the circuit and backtrack 
again.

curr_path = {0,1} and circuit = {0,2}

After reaching 1 we go to through unused edge 1->3 and 
then 3->4, 4->1 until all edges have been traversed.

The contents of the two containers look as:
curr_path = {0,1,3,4,1} and circuit = {0,2} 

now as all edges have been used, the curr_path is 
popped one by one into the circuit.
Finally, we've circuit = {0,2,1,4,3,1,0}

We print the circuit in reverse to obtain the path followed.
i.e., 0->1->3->4->1->1->2->0

Below is the implementation for the above approach: 

C++




// A C++ program to print Eulerian circuit in given
// directed graph using Hierholzer algorithm
#include <bits/stdc++.h>
using namespace std;
 
void printCircuit(vector< vector<int> > adj)
{
    // adj represents the adjacency list of
    // the directed graph
    // edge_count represents the number of edges
    // emerging from a vertex
    unordered_map<int,int> edge_count;
 
    for (int i=0; i<adj.size(); i++)
    {
        //find the count of edges to keep track
        //of unused edges
        edge_count[i] = adj[i].size();
    }
 
    if (!adj.size())
        return; //empty graph
 
    // Maintain a stack to keep vertices
    stack<int> curr_path;
 
    // vector to store final circuit
    vector<int> circuit;
 
    // start from any vertex
    curr_path.push(0);
    int curr_v = 0; // Current vertex
 
    while (!curr_path.empty())
    {
        // If there's remaining edge
        if (edge_count[curr_v])
        {
            // Push the vertex
            curr_path.push(curr_v);
 
            // Find the next vertex using an edge
            int next_v = adj[curr_v].back();
 
            // and remove that edge
            edge_count[curr_v]--;
            adj[curr_v].pop_back();
 
            // Move to next vertex
            curr_v = next_v;
        }
 
        // back-track to find remaining circuit
        else
        {
            circuit.push_back(curr_v);
 
            // Back-tracking
            curr_v = curr_path.top();
            curr_path.pop();
        }
    }
 
    // we've got the circuit, now print it in reverse
    for (int i=circuit.size()-1; i>=0; i--)
    {
        cout << circuit[i];
        if (i)
           cout<<" -> ";
    }
}
 
// Driver program to check the above function
int main()
{
    vector< vector<int> > adj1, adj2;
 
    // Input Graph 1
    adj1.resize(3);
 
    // Build the edges
    adj1[0].push_back(1);
    adj1[1].push_back(2);
    adj1[2].push_back(0);
    printCircuit(adj1);
    cout << endl;
 
    // Input Graph 2
    adj2.resize(7);
    adj2[0].push_back(1);
    adj2[0].push_back(6);
    adj2[1].push_back(2);
    adj2[2].push_back(0);
    adj2[2].push_back(3);
    adj2[3].push_back(4);
    adj2[4].push_back(2);
    adj2[4].push_back(5);
    adj2[5].push_back(0);
    adj2[6].push_back(4);
    printCircuit(adj2);
 
    return 0;
}


Java




// Java code for above approach
import java.util.*;
public class Program {
    public static void
    PrintCircuit(List<List<Integer> > adj)
    {
        // adj represents the adjacency list of
        // the directed graph
        // edge_count represents the number of edges
        // emerging from a vertex
        Map<Integer, Integer> edge_count
            = new HashMap<Integer, Integer>();
        for (int i = 0; i < adj.size(); i++) {
            // find the count of edges to keep track
            // of unused edges
            edge_count.put(i, adj.get(i).size());
        }
        if (adj.size() == 0) {
            return; // empty graph
        }
        // Maintain a stack to keep vertices
        Stack<Integer> curr_path = new Stack<Integer>();
 
        // vector to store final circuit
        List<Integer> circuit = new ArrayList<Integer>();
 
        // start from any vertex
        curr_path.push(0);
        int curr_v = 0; // Current vertex
        while (curr_path.size() != 0) {
 
            // If there's remaining edge
            if (edge_count.get(curr_v) != 0) {
 
                // Push the vertex
                curr_path.push(curr_v);
 
                // Find the next vertex using an edge
                int next_v = adj.get(curr_v).get(
                    adj.get(curr_v).size() - 1);
 
                // and remove that edge
                edge_count.put(curr_v,
                               edge_count.get(curr_v) - 1);
                adj.get(curr_v).remove(
                    adj.get(curr_v).size() - 1);
 
                // Move to next vertex
                curr_v = next_v;
            }
 
            // back-track to find remaining circuit
            else {
                circuit.add(curr_v);
 
                // Back-tracking
                curr_v = curr_path.pop();
            }
        }
 
        // we've got the circuit, now print it in reverse
        for (int i = circuit.size() - 1; i >= 0; i--) {
            System.out.print(circuit.get(i));
            if (i != 0) {
                System.out.print(" -> ");
            }
        }
    }
 
    // Driver program to check the above function
    public static void main(String[] args)
    {
        List<List<Integer> > adj1
            = new ArrayList<List<Integer> >();
        List<List<Integer> > adj2
            = new ArrayList<List<Integer> >();
 
        // Input Graph 1
        adj1.add(new ArrayList<Integer>());
        adj1.add(new ArrayList<Integer>());
        adj1.add(new ArrayList<Integer>());
 
        // Build the edges
        adj1.get(0).add(1);
        adj1.get(1).add(2);
        adj1.get(2).add(0);
        PrintCircuit(adj1);
        System.out.println();
 
        // Input Graph 2
        adj2.add(new ArrayList<Integer>());
        adj2.add(new ArrayList<Integer>());
        adj2.add(new ArrayList<Integer>());
        adj2.add(new ArrayList<Integer>());
        adj2.add(new ArrayList<Integer>());
        adj2.add(new ArrayList<Integer>());
        adj2.add(new ArrayList<Integer>());
        adj2.get(0).add(1);
        adj2.get(0).add(6);
        adj2.get(1).add(2);
        adj2.get(2).add(0);
        adj2.get(2).add(3);
        adj2.get(3).add(4);
        adj2.get(4).add(2);
        adj2.get(4).add(5);
        adj2.get(5).add(0);
        adj2.get(6).add(4);
        PrintCircuit(adj2);
    }
}


Python3




# Python3 program to print Eulerian circuit in given
# directed graph using Hierholzer algorithm
def printCircuit(adj):
 
    # adj represents the adjacency list of
    # the directed graph
    # edge_count represents the number of edges
    # emerging from a vertex
    edge_count = dict()
 
    for i in range(len(adj)):
 
        # find the count of edges to keep track
        # of unused edges
        edge_count[i] = len(adj[i])
 
    if len(adj) == 0:
        return # empty graph
 
    # Maintain a stack to keep vertices
    curr_path = []
 
    # vector to store final circuit
    circuit = []
 
    # start from any vertex
    curr_path.append(0)
    curr_v = 0 # Current vertex
 
    while len(curr_path):
 
        # If there's remaining edge
        if edge_count[curr_v]:
 
            # Push the vertex
            curr_path.append(curr_v)
 
            # Find the next vertex using an edge
            next_v = adj[curr_v][-1]
 
            # and remove that edge
            edge_count[curr_v] -= 1
            adj[curr_v].pop()
 
            # Move to next vertex
            curr_v = next_v
 
        # back-track to find remaining circuit
        else:
            circuit.append(curr_v)
 
            # Back-tracking
            curr_v = curr_path[-1]
            curr_path.pop()
 
    # we've got the circuit, now print it in reverse
    for i in range(len(circuit) - 1, -1, -1):
        print(circuit[i], end = "")
        if i:
            print(" -> ", end = "")
 
# Driver Code
if __name__ == "__main__":
 
    # Input Graph 1
    adj1 = [0] * 3
    for i in range(3):
        adj1[i] = []
 
    # Build the edges
    adj1[0].append(1)
    adj1[1].append(2)
    adj1[2].append(0)
    printCircuit(adj1)
    print()
 
    # Input Graph 2
    adj2 = [0] * 7
    for i in range(7):
        adj2[i] = []
 
    adj2[0].append(1)
    adj2[0].append(6)
    adj2[1].append(2)
    adj2[2].append(0)
    adj2[2].append(3)
    adj2[3].append(4)
    adj2[4].append(2)
    adj2[4].append(5)
    adj2[5].append(0)
    adj2[6].append(4)
    printCircuit(adj2)
    print()
 
# This code is contributed by
# sanjeev2552


C#




// C# code for above approach
using System;
using System.Collections.Generic;
public class Program {
  public static void PrintCircuit(List<List<int> > adj)
  {
 
    // adj represents the adjacency list of
    // the directed graph
    // edge_count represents the number of edges
    // emerging from a vertex
    Dictionary<int, int> edge_count
      = new Dictionary<int, int>();
    for (int i = 0; i < adj.Count; i++)
    {
 
      // find the count of edges to keep track
      // of unused edges
      edge_count[i] = adj[i].Count;
    }
    if (adj.Count == 0)
      return; // empty graph
    // Maintain a stack to keep vertices
    Stack<int> curr_path = new Stack<int>();
 
    // vector to store final circuit
    List<int> circuit = new List<int>();
 
    // start from any vertex
    curr_path.Push(0);
    int curr_v = 0; // Current vertex
    while (curr_path.Count != 0)
    {
 
      // If there's remaining edge
      if (edge_count[curr_v] != 0)
      {
 
        // Push the vertex
        curr_path.Push(curr_v);
 
        // Find the next vertex using an edge
        int next_v
          = adj[curr_v][adj[curr_v].Count - 1];
 
        // and remove that edge
        edge_count[curr_v]--;
        adj[curr_v].RemoveAt(adj[curr_v].Count - 1);
 
        // Move to next vertex
        curr_v = next_v;
      }
 
      // back-track to find remaining circuit
      else
      {
        circuit.Add(curr_v);
 
        // Back-tracking
        curr_v = curr_path.Pop();
      }
    }
 
    // we've got the circuit, now print it in reverse
    for (int i = circuit.Count - 1; i >= 0; i--) {
      Console.Write(circuit[i]);
      if (i != 0)
        Console.Write(" -> ");
    }
  }
 
  // Driver program to check the above function
  public static void Main()
  {
    List<List<int> > adj1 = new List<List<int> >();
    List<List<int> > adj2 = new List<List<int> >();
 
    // Input Graph 1
    adj1.Add(new List<int>());
    adj1.Add(new List<int>());
    adj1.Add(new List<int>());
 
    // Build the edges
    adj1[0].Add(1);
    adj1[1].Add(2);
    adj1[2].Add(0);
    PrintCircuit(adj1);
    Console.WriteLine();
 
    // Input Graph 2
    adj2.Add(new List<int>());
    adj2.Add(new List<int>());
    adj2.Add(new List<int>());
    adj2.Add(new List<int>());
    adj2.Add(new List<int>());
    adj2.Add(new List<int>());
    adj2.Add(new List<int>());
    adj2[0].Add(1);
    adj2[0].Add(6);
    adj2[1].Add(2);
    adj2[2].Add(0);
    adj2[2].Add(3);
    adj2[3].Add(4);
    adj2[4].Add(2);
    adj2[4].Add(5);
    adj2[5].Add(0);
    adj2[6].Add(4);
    PrintCircuit(adj2);
  }
}
 
// This code is contributed by ishankhandelwals.


Javascript




function printCircuit(adj) {
  // adj represents the adjacency list of
  // the directed graph
  // edge_count represents the number of edges
  // emerging from a vertex
  const edge_count = new Map();
 
  for (let i = 0; i < adj.length; i++) {
    //find the count of edges to keep track
    //of unused edges
    edge_count.set(i, adj[i].length);
  }
 
  if (!adj.length) return; //empty graph
 
  // Maintain a stack to keep vertices
  const curr_path = [];
 
  // array to store final circuit
  const circuit = [];
 
  // start from any vertex
  curr_path.push(0);
  let curr_v = 0; // Current vertex
 
  while (curr_path.length) {
    // If there's remaining edge
    if (edge_count.get(curr_v)) {
      // Push the vertex
      curr_path.push(curr_v);
 
      // Find the next vertex using an edge
      const next_v = adj[curr_v][adj[curr_v].length - 1];
 
      // and remove that edge
      edge_count.set(curr_v, edge_count.get(curr_v) - 1);
      adj[curr_v].pop();
 
      // Move to next vertex
      curr_v = next_v;
    } else {
      // back-track to find remaining circuit
      circuit.push(curr_v);
 
      // Back-tracking
      curr_v = curr_path[curr_path.length - 1];
      curr_path.pop();
    }
  }
 
  // we've got the circuit, now print it in reverse
  for (let i = circuit.length - 1; i >= 0; i--) {
    console.log(circuit[i]);
    if (i) console.log(" -> ");
  }
}
 
// Test the function
 
// Input Graph 1
const adj1 = [[1], [2], [0]];
printCircuit(adj1);
console.log();
 
// Input Graph 2
const adj2 = [  [1, 6],
  [2],
  [0, 3],
  [4],
  [2, 5],
  [0],
  [4]
];
printCircuit(adj2);
 
// This code is contributed by ishankhandelwals.


Output:

0 -> 1 -> 2 -> 0
0 -> 6 -> 4 -> 5 -> 0 -> 1 -> 2 -> 3 -> 4 -> 2 -> 0

Time complexity : O(V+E), where V is the number of vertices in the graph and E is the number of edges. This is because the code uses a stack to store the vertices and the stack operations push and pop have a time complexity of O(1).

Space complexity : O(V+E), as the code uses a stack to store the vertices and a vector to store the circuit, both of which take up O(V) space. Additionally, the code also uses an unordered_map to store the count of edges for each vertex, which takes up O(E) space.

Alternate Implementation: Below are the improvements made from the above code 

The above code kept a count of the number of edges for every vertex. This is unnecessary since we are already maintaining the adjacency list. We simply deleted the creation of edge_count array. In the algorithm we replaced `if edge_count[current_v]` with `if adj[current_v]` 

The above code pushes the initial node twice to the stack. Though the way he coded the result is correct, this approach is confusing and inefficient. We eliminated this by appending the next vertex to the stack, instead of the current one. 

In the main part, where the author tests the algorithm, the initialization of the adjacency lists `adj1` and `adj2`were a little weird. That potion is also improved. 

C++




// C++ program to print Eulerian circuit in given
// directed graph using Hierholzer algorithm
#include <bits/stdc++.h>
using namespace std;
 
// Function to print Eulerian circuit
void printCircuit(vector<int> adj[], int n)
{
    // adj represents the adjacency list of
    // the directed graph
 
    if (n == 0)
        return; // empty graph
 
    // Maintain a stack to keep vertices
    // We can start from any vertex, here we start with 0
    vector<int> curr_path;
    curr_path.push_back(0);
 
    // list to store final circuit
    vector<int> circuit;
 
    while (curr_path.size() > 0) {
        int curr_v = curr_path[curr_path.size() - 1];
 
        // If there's remaining edge in adjacency list
        // of the current vertex
        if (adj[curr_v].size() > 0) {
            // Find and remove the next vertex that is
            // adjacent to the current vertex
            int next_v = adj[curr_v].back();
            adj[curr_v].pop_back();
 
            // Push the new vertex to the stack
            curr_path.push_back(next_v);
        }
 
        // back-track to find remaining circuit
        else {
            // Remove the current vertex and
            // put it in the circuit
            circuit.push_back(curr_path.back());
            curr_path.pop_back();
        }
    }
 
    // we've got the circuit, now print it in reverse
    for (int i = circuit.size() - 1; i >= 0; i--) {
        cout << circuit[i];
        if (i)
            cout << " -> ";
    }
}
 
// Driver Code
int main()
{
    // Input Graph 1
    int n1 = 3;
    vector<int> adj1[n1];
 
    // Build the edges
    adj1[0].push_back(1);
    adj1[1].push_back(2);
    adj1[2].push_back(0);
    printCircuit(adj1, n1);
    cout << endl;
 
    // Input Graph 2
    int n2 = 7;
    vector<int> adj2[n2];
 
    adj2[0].push_back(1);
    adj2[0].push_back(6);
    adj2[1].push_back(2);
    adj2[2].push_back(0);
    adj2[2].push_back(3);
    adj2[3].push_back(4);
    adj2[4].push_back(2);
    adj2[4].push_back(5);
    adj2[5].push_back(0);
    adj2[6].push_back(4);
    printCircuit(adj2, n2);
    cout << endl;
    return 0;
}
 
// This code is contributed by sanjanasikarwar24


Java




// Java code for above approach
import java.util.*;
public class Program {
  public static void
    PrintCircuit(List<List<Integer> > adj)
  {
 
    // adj represents the adjacency list of
    // the directed graph
    // edge_count represents the number of edges
    // emerging from a vertex
    Map<Integer, Integer> edge_count
      = new HashMap<Integer, Integer>();
    for (int i = 0; i < adj.size(); i++)
    {
 
      // find the count of edges to keep track
      // of unused edges
      edge_count.put(i, adj.get(i).size());
    }
    if (adj.size() == 0) {
      return; // empty graph
    }
 
    // Maintain a stack to keep vertices
    Stack<Integer> curr_path = new Stack<Integer>();
 
    // vector to store final circuit
    List<Integer> circuit = new ArrayList<Integer>();
 
    // start from any vertex
    curr_path.push(0);
    int curr_v = 0; // Current vertex
    while (curr_path.size() != 0) {
 
      // If there's remaining edge
      if (edge_count.get(curr_v) != 0) {
 
        // Push the vertex
        curr_path.push(curr_v);
 
        // Find the next vertex using an edge
        int next_v = adj.get(curr_v).get(
          adj.get(curr_v).size() - 1);
 
        // and remove that edge
        edge_count.put(curr_v,
                       edge_count.get(curr_v) - 1);
        adj.get(curr_v).remove(
          adj.get(curr_v).size() - 1);
 
        // Move to next vertex
        curr_v = next_v;
      }
 
      // back-track to find remaining circuit
      else {
        circuit.add(curr_v);
 
        // Back-tracking
        curr_v = curr_path.pop();
      }
    }
 
    // we've got the circuit, now print it in reverse
    for (int i = circuit.size() - 1; i >= 0; i--) {
      System.out.print(circuit.get(i));
      if (i != 0) {
        System.out.print(" -> ");
      }
    }
  }
 
  // Driver program to check the above function
  public static void main(String[] args)
  {
    List<List<Integer> > adj1
      = new ArrayList<List<Integer> >();
    List<List<Integer> > adj2
      = new ArrayList<List<Integer> >();
 
    // Input Graph 1
    adj1.add(new ArrayList<Integer>());
    adj1.add(new ArrayList<Integer>());
    adj1.add(new ArrayList<Integer>());
 
    // Build the edges
    adj1.get(0).add(1);
    adj1.get(1).add(2);
    adj1.get(2).add(0);
    PrintCircuit(adj1);
    System.out.println();
 
    // Input Graph 2
    adj2.add(new ArrayList<Integer>());
    adj2.add(new ArrayList<Integer>());
    adj2.add(new ArrayList<Integer>());
    adj2.add(new ArrayList<Integer>());
    adj2.add(new ArrayList<Integer>());
    adj2.add(new ArrayList<Integer>());
    adj2.add(new ArrayList<Integer>());
    adj2.get(0).add(1);
    adj2.get(0).add(6);
    adj2.get(1).add(2);
    adj2.get(2).add(0);
    adj2.get(2).add(3);
    adj2.get(3).add(4);
    adj2.get(4).add(2);
    adj2.get(4).add(5);
    adj2.get(5).add(0);
    adj2.get(6).add(4);
    PrintCircuit(adj2);
  }
}
 
// This code is contributed by ishankhandelwals.


Python3




# Python3 program to print Eulerian circuit in given
# directed graph using Hierholzer algorithm
def printCircuit(adj):
  
    # adj represents the adjacency list of
    # the directed graph
      
    if len(adj) == 0:
        return # empty graph
  
    # Maintain a stack to keep vertices
    # We can start from any vertex, here we start with 0
    curr_path = [0]
  
    # list to store final circuit
    circuit = []
  
    while curr_path:
  
        curr_v = curr_path[-1]
          
        # If there's remaining edge in adjacency list 
        # of the current vertex
        if adj[curr_v]:
 
            # Find and remove the next vertex that is 
            # adjacent to the current vertex
            next_v = adj[curr_v].pop()
  
            # Push the new vertex to the stack
            curr_path.append(next_v)
  
        # back-track to find remaining circuit
        else:
            # Remove the current vertex and
            # put it in the circuit
            circuit.append(curr_path.pop())
  
    # we've got the circuit, now print it in reverse
    for i in range(len(circuit) - 1, -1, -1):
        print(circuit[i], end = "")
        if i:
            print(" -> ", end = "")
  
# Driver Code
if __name__ == "__main__":
  
    # Input Graph 1
    adj1 = [[] for _ in range(3)]
  
    # Build the edges
    adj1[0].append(1)
    adj1[1].append(2)
    adj1[2].append(0)
    printCircuit(adj1)
    print()
  
    # Input Graph 2
    adj2 = [[] for _ in range(7)]
  
    adj2[0].append(1)
    adj2[0].append(6)
    adj2[1].append(2)
    adj2[2].append(0)
    adj2[2].append(3)
    adj2[3].append(4)
    adj2[4].append(2)
    adj2[4].append(5)
    adj2[5].append(0)
    adj2[6].append(4)
    printCircuit(adj2)
    print()


C#




// C# code for above approach
using System;
using System.Collections.Generic;
public class Program {
  public static void PrintCircuit(List<List<int> > adj)
  {
 
    // adj represents the adjacency list of
    // the directed graph
    // edge_count represents the number of edges
    // emerging from a vertex
    Dictionary<int, int> edge_count
      = new Dictionary<int, int>();
    for (int i = 0; i < adj.Count; i++)
    {
 
      // find the count of edges to keep track
      // of unused edges
      edge_count[i] = adj[i].Count;
    }
    if (adj.Count == 0)
      return; // empty graph
    // Maintain a stack to keep vertices
    Stack<int> curr_path = new Stack<int>();
 
    // vector to store final circuit
    List<int> circuit = new List<int>();
 
    // start from any vertex
    curr_path.Push(0);
    int curr_v = 0; // Current vertex
    while (curr_path.Count != 0)
    {
 
      // If there's remaining edge
      if (edge_count[curr_v] != 0)
      {
 
        // Push the vertex
        curr_path.Push(curr_v);
 
        // Find the next vertex using an edge
        int next_v
          = adj[curr_v][adj[curr_v].Count - 1];
 
        // and remove that edge
        edge_count[curr_v]--;
        adj[curr_v].RemoveAt(adj[curr_v].Count - 1);
 
        // Move to next vertex
        curr_v = next_v;
      }
 
      // back-track to find remaining circuit
      else
      {
        circuit.Add(curr_v);
 
        // Back-tracking
        curr_v = curr_path.Pop();
      }
    }
 
    // we've got the circuit, now print it in reverse
    for (int i = circuit.Count - 1; i >= 0; i--) {
      Console.Write(circuit[i]);
      if (i != 0)
        Console.Write(" -> ");
    }
  }
 
  // Driver program to check the above function
  public static void Main()
  {
    List<List<int> > adj1 = new List<List<int> >();
    List<List<int> > adj2 = new List<List<int> >();
 
    // Input Graph 1
    adj1.Add(new List<int>());
    adj1.Add(new List<int>());
    adj1.Add(new List<int>());
 
    // Build the edges
    adj1[0].Add(1);
    adj1[1].Add(2);
    adj1[2].Add(0);
    PrintCircuit(adj1);
    Console.WriteLine();
 
    // Input Graph 2
    adj2.Add(new List<int>());
    adj2.Add(new List<int>());
    adj2.Add(new List<int>());
    adj2.Add(new List<int>());
    adj2.Add(new List<int>());
    adj2.Add(new List<int>());
    adj2.Add(new List<int>());
    adj2[0].Add(1);
    adj2[0].Add(6);
    adj2[1].Add(2);
    adj2[2].Add(0);
    adj2[2].Add(3);
    adj2[3].Add(4);
    adj2[4].Add(2);
    adj2[4].Add(5);
    adj2[5].Add(0);
    adj2[6].Add(4);
    PrintCircuit(adj2);
  }
}
 
// This code is contributed by ishankhandelwals.


Javascript




// Javascript program to print Eulerian circuit in given
// directed graph using Hierholzer algorithm
 
      // Function to print Eulerian circuit
      function printCircuit(adj, n)
      {
       
        // adj represents the adjacency list of
        // the directed graph
 
        if (n == 0) return; // empty graph
 
        // Maintain a stack to keep vertices
        // We can start from any vertex, here we start with 0
        let curr_path = new Array();
        curr_path.push(0);
 
        // list to store final circuit
 
        let circuit = new Array();
        while (curr_path.length > 0) {
          let curr_v = curr_path[curr_path.length - 1];
 
          // If there's remaining edge in adjacency list
          // of the current vertex
          if (adj[curr_v].length > 0) {
            // Find and remove the next vertex that is
            // adjacent to the current vertex
            let next_v = adj[curr_v][adj[curr_v].length - 1];
            adj[curr_v].pop();
 
            // Push the new vertex to the stack
            curr_path.push(next_v);
          }
 
          // back-track to find remaining circuit
          else {
            // Remove the current vertex and
            // put it in the circuit
            circuit.push(curr_path[curr_path.length - 1]);
            curr_path.pop();
          }
        }
 
        // we've got the circuit, now print it in reverse
        for (let i = circuit.length - 1; i >= 0; i--) {
          document.write(circuit[i]);
          if (i) document.write(" -> ");
        }
        document.write("<br>");
      }
 
      // Driver Code
 
      // Input Graph 1
      let n1 = 3;
      let adj1 = Array.from(Array(n1), () => new Array());
      // Build the edges
      adj1[0].push(1);
      adj1[1].push(2);
      adj1[2].push(0);
      printCircuit(adj1, n1);
 
      // Input Graph 2
      let n2 = 7;
      let adj2 = Array.from(Array(n2), () => new Array());
 
      adj2[0].push(1);
      adj2[0].push(6);
      adj2[1].push(2);
      adj2[2].push(0);
      adj2[2].push(3);
      adj2[3].push(4);
      adj2[4].push(2);
      adj2[4].push(5);
      adj2[5].push(0);
      adj2[6].push(4);
      printCircuit(adj2, n2);
       
      // This code is contributed by satwiksuman.


Output:

0 -> 1 -> 2 -> 0
0 -> 6 -> 4 -> 5 -> 0 -> 1 -> 2 -> 3 -> 4 -> 2 -> 0

Time Complexity :  O(V + E), where V is the number of vertices and E is the number of edges in the graph. The reason for this is because the algorithm performs a depth-first search (DFS) and visits each vertex and each edge exactly once. So, for each vertex, it takes O(1) time to visit it and for each edge, it takes O(1) time to traverse it.

Space complexity  : O(V + E), as the algorithm uses a stack to store the current path and a list to store the final circuit. The maximum size of the stack can be V + E at worst, so the space complexity is O(V + E).

The article contains also inputs from Nitish Kumar.



Previous Article
Next Article

Similar Reads

What is Directed Graph? | Directed Graph meaning
A directed graph is defined as a type of graph where the edges have a direction associated with them. Characteristics of Directed Graph Directed graphs have several characteristics that make them different from undirected graphs. Here are some key characteristics of directed graphs: Directed edges: In a directed graph, edges have a direction associ
3 min read
Convert the undirected graph into directed graph such that there is no path of length greater than 1
Given an undirected graph with N vertices and M edges and no self loops or multiple edges. The task is to convert the given undirected graph into a directed graph such that there is no path of length greater than 1. If it is possible to make such a graph then print two space-separated integers u and v in M lines where u, v denotes source and destin
10 min read
Convert undirected connected graph to strongly connected directed graph
Given an undirected graph of N vertices and M edges, the task is to assign directions to the given M Edges such that the graph becomes Strongly Connected Components. If a graph cannot be converted into Strongly Connected Components then print "-1". Examples: Input: N = 5, Edges[][] = { { 0, 1 }, { 0, 2 }, { 1, 2 }, { 1, 4 }, { 2, 3 }, { 3, 4 } } Ou
14 min read
Why Prim’s and Kruskal's MST algorithm fails for Directed Graph?
Pre-requisites: Graph and its representations Greedy Algorithms | Set 5 (Prim’s Minimum Spanning Tree (MST)) Kruskal’s Minimum Spanning Tree Algorithm | Greedy Algo-2 Given a directed graph D = &lt; V, E &gt;, the task is to find the minimum spanning tree for the given directed graph Example: But the Prim's Minimum Spanning Tree and Kruskal's algor
2 min read
Shortest path in a directed graph by Dijkstra’s algorithm
Given a directed graph and a source vertex in the graph, the task is to find the shortest distance and path from source to target vertex in the given graph where edges are weighted (non-negative) and directed from parent vertex to source vertices. Approach: Mark all vertices unvisited. Create a set of all unvisited vertices.Assign zero distance val
15 min read
Find if there is a path between two vertices in a directed graph
Given a Directed Graph and two vertices in it, check whether there is a path from the first given vertex to second. Example: Consider the following Graph: Input : (u, v) = (1, 3) Output: Yes Explanation: There is a path from 1 to 3, 1 -&gt; 2 -&gt; 3 Input : (u, v) = (3, 6) Output: No Explanation: There is no path from 3 to 6 Approach: Either Bread
15 min read
Shortest path with exactly k edges in a directed and weighted graph
Given a directed and two vertices ‘u’ and ‘v’ in it, find shortest path from ‘u’ to ‘v’ with exactly k edges on the path. The graph is given as adjacency matrix representation where value of graph[i][j] indicates the weight of an edge from vertex i to vertex j and a value INF(infinite) indicates no edge from i to j. For example, consider the follow
15+ min read
Assign directions to edges so that the directed graph remains acyclic
Given a graph with both directed and undirected edges. It is given that the directed edges don't form cycle. How to assign directions to undirected edges so that the graph (with all directed edges) remains acyclic even after the assignment? For example, in the below graph, blue edges don't have directions. We strongly recommend to minimize your bro
1 min read
Number of shortest paths in an unweighted and directed graph
Given an unweighted directed graph, can be cyclic or acyclic. Print the number of shortest paths from a given vertex to each of the vertices. For example consider the below graph. There is one shortest path vertex 0 to vertex 0 (from each vertex there is a single shortest path to itself), one shortest path between vertex 0 to vertex 2 (0-&gt;2), an
11 min read
Find if there is a path between two vertices in a directed graph | Set 2
Given a Directed Graph and two vertices in it, check whether there is a path from the first given vertex to second. Example: Consider the following Graph: Input : (u, v) = (1, 3) Output: Yes Explanation: There is a path from 1 to 3, 1 -&gt; 2 -&gt; 3 Input : (u, v) = (3, 6) Output: No Explanation: There is no path from 3 to 6 A BFS or DFS based sol
7 min read
Article Tags :
Practice Tags :