Euler Circuit in a Directed Graph

Last Updated : 31 Jan, 2023

Eulerian Path is a path in graph that visits every edge exactly once. Eulerian Circuit is an Eulerian Path which starts and ends on the same vertex.

A graph is said to be eulerian if it has a eulerian cycle. We have discussed eulerian circuit for an undirected graph. In this post, the same is discussed for a directed graph.

For example, the following graph has eulerian cycle as {1, 0, 3, 4, 0, 2, 1}

SCC

How to check if a directed graph is eulerian?

A directed graph has an eulerian cycle if following conditions are true

All vertices with nonzero degree belong to a single strongly connected component.
In degree is equal to the out degree for every vertex.

We can detect singly connected component using Kosaraju’s DFS based simple algorithm.

To compare in degree and out-degree, we need to store in degree and out-degree of every vertex. Out degree can be obtained by the size of an adjacency list. In degree can be stored by creating an array of size equal to the number of vertices.

Following implementations of above approach.

C++

// A C++ program to check if a given directed graph is Eulerian or not
#include<iostream>
#include <list>
#define CHARS 26
using namespace std;
 
// A class that represents an undirected graph
class Graph
{
    int V;    // No. of vertices
    list<int> *adj;    // A dynamic array of adjacency lists
    int *in;
public:
    // Constructor and destructor
    Graph(int V);
    ~Graph()   { delete [] adj; delete [] in; }
 
    // function to add an edge to graph
    void addEdge(int v, int w) { adj[v].push_back(w);  (in[w])++; }
 
    // Method to check if this graph is Eulerian or not
    bool isEulerianCycle();
 
    // Method to check if all non-zero degree vertices are connected
    bool isSC();
 
    // Function to do DFS starting from v. Used in isConnected();
    void DFSUtil(int v, bool visited[]);
 
    Graph getTranspose();
};
 
Graph::Graph(int V)
{
    this->V = V;
    adj = new list<int>[V];
    in = new int[V];
    for (int i = 0; i < V; i++)
       in[i] = 0;
}
 
/* This function returns true if the directed graph has a eulerian
   cycle, otherwise returns false  */
bool Graph::isEulerianCycle()
{
    // Check if all non-zero degree vertices are connected
    if (isSC() == false)
        return false;
 
    // Check if in degree and out degree of every vertex is same
    for (int i = 0; i < V; i++)
        if (adj[i].size() != in[i])
            return false;
 
    return true;
}
 
// A recursive function to do DFS starting from v
void Graph::DFSUtil(int v, bool visited[])
{
    // Mark the current node as visited and print it
    visited[v] = true;
 
    // Recur for all the vertices adjacent to this vertex
    list<int>::iterator i;
    for (i = adj[v].begin(); i != adj[v].end(); ++i)
        if (!visited[*i])
            DFSUtil(*i, visited);
}
 
// Function that returns reverse (or transpose) of this graph
// This function is needed in isSC()
Graph Graph::getTranspose()
{
    Graph g(V);
    for (int v = 0; v < V; v++)
    {
        // Recur for all the vertices adjacent to this vertex
        list<int>::iterator i;
        for(i = adj[v].begin(); i != adj[v].end(); ++i)
        {
            g.adj[*i].push_back(v);
            (g.in[v])++;
        }
    }
    return g;
}
 
// This function returns true if all non-zero degree vertices of 
// graph are strongly connected (Please refer 
// https://www.geeksforgeeks.org/connectivity-in-a-directed-graph/ )
bool Graph::isSC()
{
    // Mark all the vertices as not visited (For first DFS)
    bool visited[V];
    for (int i = 0; i < V; i++)
        visited[i] = false;
 
    // Find the first vertex with non-zero degree
    int n;
    for (n = 0; n < V; n++)
        if (adj[n].size() > 0)
          break;
 
    // Do DFS traversal starting from first non zero degrees vertex.
    DFSUtil(n, visited);
 
     // If DFS traversal doesn't visit all vertices, then return false.
    for (int i = 0; i < V; i++)
        if (adj[i].size() > 0 && visited[i] == false)
              return false;
 
    // Create a reversed graph
    Graph gr = getTranspose();
 
    // Mark all the vertices as not visited (For second DFS)
    for (int i = 0; i < V; i++)
        visited[i] = false;
 
    // Do DFS for reversed graph starting from first vertex.
    // Starting Vertex must be same starting point of first DFS
    gr.DFSUtil(n, visited);
 
    // If all vertices are not visited in second DFS, then
    // return false
    for (int i = 0; i < V; i++)
        if (adj[i].size() > 0 && visited[i] == false)
             return false;
 
    return true;
}
 
// Driver program to test above functions
int main()
{
    // Create a graph given in the above diagram
    Graph g(5);
    g.addEdge(1, 0);
    g.addEdge(0, 2);
    g.addEdge(2, 1);
    g.addEdge(0, 3);
    g.addEdge(3, 4);
    g.addEdge(4, 0);
 
    if (g.isEulerianCycle())
       cout << "Given directed graph is eulerian n";
    else
       cout << "Given directed graph is NOT eulerian n";
    return 0;
}

Java

// A Java program to check if a given directed graph is Eulerian or not
 
// A class that represents an undirected graph
import java.io.*;
import java.util.*;
import java.util.LinkedList;
 
// This class represents a directed graph using adjacency list
class Graph
{
    private int V;   // No. of vertices
    private LinkedList<Integer> adj[];//Adjacency List
    private int in[];            //maintaining in degree
 
    //Constructor
    Graph(int v)
    {
        V = v;
        adj = new LinkedList[v];
        in = new int[V];
        for (int i=0; i<v; ++i)
        {
            adj[i] = new LinkedList();
            in[i]  = 0;
        }
    }
 
    //Function to add an edge into the graph
    void addEdge(int v,int w)
    {
        adj[v].add(w);
        in[w]++;
    }
 
    // A recursive function to print DFS starting from v
    void DFSUtil(int v,Boolean visited[])
    {
        // Mark the current node as visited
        visited[v] = true;
 
        int n;
 
        // Recur for all the vertices adjacent to this vertex
        Iterator<Integer> i =adj[v].iterator();
        while (i.hasNext())
        {
            n = i.next();
            if (!visited[n])
                DFSUtil(n,visited);
        }
    }
 
    // Function that returns reverse (or transpose) of this graph
    Graph getTranspose()
    {
        Graph g = new Graph(V);
        for (int v = 0; v < V; v++)
        {
            // Recur for all the vertices adjacent to this vertex
            Iterator<Integer> i = adj[v].listIterator();
            while (i.hasNext())
            {
                g.adj[i.next()].add(v);
                (g.in[v])++;
            }
        }
        return g;
    }
 
    // The main function that returns true if graph is strongly
    // connected
    Boolean isSC()
    {
        // Step 1: Mark all the vertices as not visited (For
        // first DFS)
        Boolean visited[] = new Boolean[V];
        for (int i = 0; i < V; i++)
            visited[i] = false;
 
        // Step 2: Do DFS traversal starting from the first vertex.
        DFSUtil(0, visited);
 
        // If DFS traversal doesn't visit all vertices, then return false.
        for (int i = 0; i < V; i++)
            if (visited[i] == false)
                return false;
 
        // Step 3: Create a reversed graph
        Graph gr = getTranspose();
 
        // Step 4: Mark all the vertices as not visited (For second DFS)
        for (int i = 0; i < V; i++)
            visited[i] = false;
 
        // Step 5: Do DFS for reversed graph starting from first vertex.
        // Starting Vertex must be same starting point of first DFS
        gr.DFSUtil(0, visited);
 
        // If all vertices are not visited in second DFS, then
        // return false
        for (int i = 0; i < V; i++)
            if (visited[i] == false)
                return false;
 
        return true;
    }
 
    /* This function returns true if the directed graph has a eulerian
       cycle, otherwise returns false  */
    Boolean isEulerianCycle()
    {
        // Check if all non-zero degree vertices are connected
        if (isSC() == false)
            return false;
 
        // Check if in degree and out degree of every vertex is same
        for (int i = 0; i < V; i++)
            if (adj[i].size() != in[i])
                return false;
 
        return true;
    }
 
    public static void main (String[] args) throws java.lang.Exception
    {
        Graph g = new Graph(5);
        g.addEdge(1, 0);
        g.addEdge(0, 2);
        g.addEdge(2, 1);
        g.addEdge(0, 3);
        g.addEdge(3, 4);
        g.addEdge(4, 0);
 
        if (g.isEulerianCycle())
            System.out.println("Given directed graph is eulerian ");
        else
            System.out.println("Given directed graph is NOT eulerian ");
    }
}
//This code is contributed by Aakash Hasija

Python3

# A Python3 program to check if a given 
# directed graph is Eulerian or not
 
from collections import defaultdict
 
class Graph():
 
    def __init__(self, vertices):
        self.V = vertices
        self.graph = defaultdict(list)
        self.IN = [0] * vertices
 
    def addEdge(self, v, u):
 
        self.graph[v].append(u)
        self.IN[u] += 1
 
    def DFSUtil(self, v, visited):
        visited[v] = True
        for node in self.graph[v]:
            if visited[node] == False:
                self.DFSUtil(node, visited)
 
    def getTranspose(self):
        gr = Graph(self.V)
 
        for node in range(self.V):
            for child in self.graph[node]:
                gr.addEdge(child, node)
 
        return gr
 
    def isSC(self):
        visited = [False] * self.V
 
        v = 0
        for v in range(self.V):
            if len(self.graph[v]) > 0:
                break
 
        self.DFSUtil(v, visited)
 
        # If DFS traversal doesn't visit all 
        # vertices, then return false.
        for i in range(self.V):
            if visited[i] == False:
                return False
 
        gr = self.getTranspose()
 
        visited = [False] * self.V
        gr.DFSUtil(v, visited)
 
        for i in range(self.V):
            if visited[i] == False:
                return False
 
        return True
 
    def isEulerianCycle(self):
 
        # Check if all non-zero degree vertices 
        # are connected
        if self.isSC() == False:
            return False
 
        # Check if in degree and out degree of 
        # every vertex is same
        for v in range(self.V):
            if len(self.graph[v]) != self.IN[v]:
                return False
 
        return True
 
 
g = Graph(5);
g.addEdge(1, 0);
g.addEdge(0, 2);
g.addEdge(2, 1);
g.addEdge(0, 3);
g.addEdge(3, 4);
g.addEdge(4, 0);
if g.isEulerianCycle():
   print( "Given directed graph is eulerian");
else:
   print( "Given directed graph is NOT eulerian");
 
# This code is contributed by Divyanshu Mehta

C#

// A C# program to check if a given 
// directed graph is Eulerian or not
 
// A class that represents an
// undirected graph
using System;
using System.Collections.Generic;
 
// This class represents a directed
// graph using adjacency list
class Graph{
     
// No. of vertices
public int V;   
 
// Adjacency List
public List<int> []adj;
 
// Maintaining in degree
public int []init;           
 
// Constructor
Graph(int v)
{
    V = v;
    adj = new List<int>[v];
    init = new int[V];
     
    for(int i = 0; i < v; ++i)
    {
        adj[i] = new List<int>();
        init[i]  = 0;
    }
}
 
// Function to add an edge into the graph
void addEdge(int v, int w)
{
    adj[v].Add(w);
    init[w]++;
}
 
// A recursive function to print DFS 
// starting from v
void DFSUtil(int v, Boolean []visited)
{
     
    // Mark the current node as visited
    visited[v] = true;
 
    // Recur for all the vertices 
    // adjacent to this vertex
    foreach(int i in adj[v])
    {
         
        if (!visited[i])
            DFSUtil(i, visited);
    }
}
 
// Function that returns reverse
// (or transpose) of this graph
Graph getTranspose()
{
    Graph g = new Graph(V);
    for(int v = 0; v < V; v++)
    {
         
        // Recur for all the vertices 
        // adjacent to this vertex
        foreach(int i in adj[v])
        {
            g.adj[i].Add(v);
            (g.init[v])++;
        }
    }
    return g;
}
 
// The main function that returns 
// true if graph is strongly connected
Boolean isSC()
{
     
    // Step 1: Mark all the vertices 
    // as not visited (For first DFS)
    Boolean []visited = new Boolean[V];
    for(int i = 0; i < V; i++)
        visited[i] = false;
 
    // Step 2: Do DFS traversal starting
    // from the first vertex.
    DFSUtil(0, visited);
 
    // If DFS traversal doesn't visit 
    // all vertices, then return false.
    for(int i = 0; i < V; i++)
        if (visited[i] == false)
            return false;
 
    // Step 3: Create a reversed graph
    Graph gr = getTranspose();
 
    // Step 4: Mark all the vertices as
    // not visited (For second DFS)
    for(int i = 0; i < V; i++)
        visited[i] = false;
 
    // Step 5: Do DFS for reversed graph 
    // starting from first vertex.
    // Starting Vertex must be same 
    // starting point of first DFS
    gr.DFSUtil(0, visited);
 
    // If all vertices are not visited 
    // in second DFS, then return false
    for(int i = 0; i < V; i++)
        if (visited[i] == false)
            return false;
 
    return true;
}
 
// This function returns true if the 
// directed graph has a eulerian 
// cycle, otherwise returns false  
Boolean isEulerianCycle()
{
     
    // Check if all non-zero degree 
    // vertices are connected
    if (isSC() == false)
        return false;
 
    // Check if in degree and out 
    // degree of every vertex is same
    for(int i = 0; i < V; i++)
        if (adj[i].Count != init[i])
            return false;
 
    return true;
}
 
// Driver code
public static void Main(String[] args)
{
    Graph g = new Graph(5);
    g.addEdge(1, 0);
    g.addEdge(0, 2);
    g.addEdge(2, 1);
    g.addEdge(0, 3);
    g.addEdge(3, 4);
    g.addEdge(4, 0);
     
    if (g.isEulerianCycle())
        Console.WriteLine("Given directed " + 
                          "graph is eulerian ");
    else
        Console.WriteLine("Given directed " + 
                          "graph is NOT eulerian ");
}
}
 
// This code is contributed by Princi Singh

Javascript

<script>
// A Javascript program to check if a given directed graph is Eulerian or not
 
// This class represents a directed graph using adjacency
// list representation
class Graph
{
    // Constructor
    constructor(v)
    {
        this.V = v;
        this.adj = new Array(v);
         
        this.in=new Array(v);
        for (let i=0; i<v; ++i)
        {    
            this.adj[i] = [];
            this.in[i]=0;
        }
    }
     
    //Function to add an edge into the graph
    addEdge(v,w)
    {
        this.adj[v].push(w);  
        this.in[w]++;
         
    }
     
    // A recursive function to print DFS starting from v
    DFSUtil(v,visited)
    {
        // Mark the current node as visited
        visited[v] = true;
  
        let n;
  
        // Recur for all the vertices adjacent to this vertex
         
        for(let i of this.adj[v])
        {
            n = i;
            if (!visited[n])
                this.DFSUtil(n,visited);
        }
    }
     
    // Function that returns reverse (or transpose) of this graph
    getTranspose()
    {
        let g = new Graph(this.V);
        for (let v = 0; v < this.V; v++)
        {
            // Recur for all the vertices adjacent to this vertex
             
            for(let i of this.adj[v])
            {
                g.adj[i].push(v);
                (g.in[v])++;
            }
        }
        return g;
    }
     
    // The main function that returns true if graph is strongly
    // connected
    isSC()
    {
        // Step 1: Mark all the vertices as not visited (For
        // first DFS)
        let visited = new Array(this.V);
        for (let i = 0; i < this.V; i++)
            visited[i] = false;
  
        // Step 2: Do DFS traversal starting from the first vertex.
        this.DFSUtil(0, visited);
  
        // If DFS traversal doesn't visit all vertices, then return false.
        for (let i = 0; i < this.V; i++)
            if (visited[i] == false)
                return false;
  
        // Step 3: Create a reversed graph
        let gr = this.getTranspose();
  
        // Step 4: Mark all the vertices as not visited (For second DFS)
        for (let i = 0; i < this.V; i++)
            visited[i] = false;
  
        // Step 5: Do DFS for reversed graph starting from first vertex.
        // Starting Vertex must be same starting point of first DFS
        gr.DFSUtil(0, visited);
  
        // If all vertices are not visited in second DFS, then
        // return false
        for (let i = 0; i < this.V; i++)
            if (visited[i] == false)
                return false;
  
        return true;
    }
     
    /* This function returns true if the directed graph has a eulerian
       cycle, otherwise returns false  */
    isEulerianCycle()
    {
        // Check if all non-zero degree vertices are connected
        if (this.isSC() == false)
            return false;
  
        // Check if in degree and out degree of every vertex is same
        for (let i = 0; i < this.V; i++)
            if (this.adj[i].length != this.in[i])
                return false;
  
        return true;
    }
}
 
let g = new Graph(5);
g.addEdge(1, 0);
g.addEdge(0, 2);
g.addEdge(2, 1);
g.addEdge(0, 3);
g.addEdge(3, 4);
g.addEdge(4, 0);
 
if (g.isEulerianCycle())
    document.write("Given directed graph is eulerian ");
else
    document.write("Given directed graph is NOT eulerian ");
 
 
// This code is contributed by avanitrachhadiya2155
</script>

Output

Given directed graph is eulerian n

Time complexity of the above implementation is O(V + E) as Kosaraju’s algorithm takes O(V + E) time. After running Kosaraju’s algorithm we traverse all vertices and compare in degree with out degree which takes O(V) time.

Auxiliary Space : O(V), since an extra visited array of size V is required.

See following as an application of this.
Find if the given array of strings can be chained to form a circle.

GeeksforGeeks

Improve

Previous Article

Count all possible walks from a source to a destination with exactly k edges

Word Ladder (Length of shortest chain to reach a target word)

Similar Reads

Conversion of an Undirected Graph to a Directed Euler Circuit

Given an undirected graph with V nodes (say numbered from 1 to V) and E edges, the task is to check whether the graph is an Euler Graph or not and if so then convert it into a Directed Euler Circuit. A Directed Euler Circuit is a directed graph such that if you start traversing the graph from any node and travel through each edge exactly once you w

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

Minimum edges required to add to make Euler Circuit

Given a undirected graph of n nodes and m edges. The task is to find minimum edges required to make Euler Circuit in the given graph. Examples: Input : n = 3, m = 2 Edges[] = {{1, 2}, {2, 3}} Output : 1By connecting 1 to 3, we can create a Euler Circuit. For a Euler Circuit to exist in the graph we require that every node should have even degree be

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

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

Program to find Circuit Rank of an Undirected Graph

Given the number of Vertices and the number of Edges of an Undirected Graph. The task is to determine the Circuit rank. Circuit Rank: The Circuit rank of an undirected graph is defined as the minimum number of edges that must be removed from the graph to break all of its cycles, converting it into a tree or forest. Examples: Input :Edges = 7 , Vert

Eulerian path and circuit for undirected graph

Eulerian Path is a path in a graph that visits every edge exactly once. Eulerian Circuit is an Eulerian Path that starts and ends on the same vertex. How to find whether a given graph is Eulerian or not? The problem is same as following question. "Is it possible to draw a given graph without lifting pencil from the paper and without tracing any of

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 -> 2 -> 3 Input : (u, v) = (3, 6) Output: No Explanation: There is no path from 3 to 6 Approach: Either Bread

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

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

Article Tags :

Practice Tags :