Eulerian cycle in directed graphs
Given a directed graph, check if it is possible to construct a cycle that visits each edge exactly once, i.e., check whether the graph has an Eulerian cycle or not.
Related Post:
An Eulerian trail (or Eulerian path) is a path that visits every edge in a graph exactly once. An Eulerian circuit (or Eulerian cycle) is an Eulerian trail that starts and ends on the same vertex. A directed graph has an Eulerian cycle if and only if
- Every vertex has equal in-degree and out-degree, and
- All of its vertices with a non-zero degree belong to a single strongly connected component.
The graph is strongly connected if it contains a directed path from u to v and a directed path from v to u for every pair of vertices (u, v). For example, the following graph has an Eulerian cycle [0 -> 1 -> 2 -> 3 -> 1 -> 4 -> 3 -> 0] since it is strongly connected, and each vertex has an equal in-degree and out-degree:
Following is the implementation in C++, Java, and Python to check whether a given directed graph has an Eulerian cycle using Kosaraju’s algorithm to find the strongly connected component in the graph.
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 |
#include <iostream> #include <vector> #include <algorithm> using namespace std; // Data structure to store a graph edge struct Edge { int src, dest; }; // A class to represent a graph object class Graph { public: // A vector of vectors to represent an adjacency list vector<vector<int>> adjList; // A vector to store in-degree of each vertex in the graph vector<int> in; // Graph Constructor Graph(int n, vector<Edge> const &edges = {}) { // resize both vectors to hold `n` elements each adjList.resize(n); in.resize(n); // add edges to the directed graph, and update in-degree for each edge for (auto &edge: edges) { addEdge(edge.src, edge.dest); } } // Utility function to add an edge (u, v) to the graph void addEdge(int u, int v) { adjList[u].push_back(v); in[v]++; } }; // Utility function to perform DFS traversal on the graph void DFS(Graph const &graph, int u, vector<bool> &visited) { // mark the current node as visited visited[u] = true; // do for every edge (u, v) for (int v: graph.adjList[u]) { // recur if `v` is not visited if (!visited[v]) { DFS(graph, v, visited); } } } // Function to create transpose of a graph, i.e., the same graph // with the direction of every edge reversed Graph buildTranspose(Graph const &graph, int n) { Graph g(n); for (int u = 0; u < n; u++) { // for every edge (u, v), create a reverse edge (v, u) // in the transpose graph for (int v: graph.adjList[u]) { g.addEdge(v, u); } } return g; } // Function to check if all vertices of a graph with a non-zero degree are visited bool isVisited(Graph const &graph, const vector<bool> &visited) { for (int i = 0; i < visited.size(); i++) { if (graph.adjList[i].size() && !visited[i]) { return false; } } return true; } // Function to check if all vertices with a non-zero degree in a graph belong to a // single strongly connected component using Kosaraju’s algorithm bool isSC(Graph const &graph, int n) { // keep track of all previously visited vertices vector<bool> visited(n); // find the first vertex `i` with a non-zero degree, and start DFS from it int i; for (i = 0; i < n; i++) { if (graph.adjList[i].size()) { DFS(graph, i, visited); break; } } // return false if DFS couldn't visit all vertices with a non-zero degree if (!isVisited(graph, visited)) { return false; } // reset the visited array fill(visited.begin(), visited.end(), false); // create a transpose of the graph Graph g = buildTranspose(graph, n); // perform DFS on the transpose graph using the same starting vertex as // used in the previous DFS call DFS(g, i, visited); // return true if second DFS also explored all vertices with a non-zero degree; // false otherwise return isVisited(g, visited); } // Function to check if a directed graph has an Eulerian cycle bool hasEulerianCycle(Graph const &graph, int n) { // check if every vertex has the same in-degree and out-degree for (int i = 0; i < n; i++) { if (graph.adjList[i].size() != graph.in[i]) { return false; } } // check if all vertices with a non-zero degree belong to a single // strongly connected component return isSC(graph, n); } int main() { // vector of graph edges as per the above diagram vector<Edge> edges = { {0, 1}, {1, 2}, {2, 3}, {3, 1}, {1, 4}, {4, 3}, {3, 0} }; // total number of nodes in the graph (labelled from 0 to 4) int n = 5; // build a directed graph from the above edges Graph graph(n, edges); if (hasEulerianCycle(graph, n)) { cout << "The graph has an Eulerian cycle" << endl; } else { cout << "The Graph does not contain Eulerian cycle" << endl; } return 0; } |
Output:
The graph has an Eulerian cycle
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 |
import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.List; // A class to store a graph edge class Edge { int source, dest; public Edge(int source, int dest) { this.source = source; this.dest = dest; } } // A class to represent a graph object class Graph { // A list of lists to represent an adjacency list List<List<Integer>> adjList; // stores indegree of a vertex List<Integer> in; // Constructor Graph(int n) { adjList = new ArrayList<>(); for (int i = 0; i < n; i++) { adjList.add(new ArrayList<>()); } // initialize indegree of each vertex by 0 in = new ArrayList<>(Collections.nCopies(n, 0)); } // Constructor Graph(List<Edge> edges, int n) { this(n); // add edges to the directed graph for (Edge edge: edges) { addEdge(edge.source, edge.dest); } } // Utility function to add an edge (u, v) to the graph void addEdge(int u, int v) { // add an edge from source to destination adjList.get(u).add(v); // increment in-degree of destination vertex by 1 in.set(v, in.get(v) + 1); } } class Main { // Function to perform DFS traversal on the graph public static void DFS(Graph graph, int v, boolean[] discovered) { // mark the current node as discovered discovered[v] = true; // do for every edge (v, u) for (int u: graph.adjList.get(v)) { // `u` is not discovered if (!discovered[u]) { DFS(graph, u, discovered); } } } // Function to create transpose of a graph, i.e., the same graph // with the direction of every edge reversed public static Graph buildTranspose(Graph graph, int n) { Graph g = new Graph(n); for (int u = 0; u < n; u++) { // for every edge (u, v), create a reverse edge (v, u) // in the transpose graph for (int v: graph.adjList.get(u)) { g.addEdge(v, u); } } return g; } // Function to check if all vertices of a graph with a non-zero degree are visited public static boolean isVisited(Graph graph, boolean[] visited) { for (int i = 0; i < visited.length; i++) { if (graph.adjList.get(i).size() > 0 && !visited[i]) { return false; } } return true; } // Function to check if all vertices with a non-zero degree in a graph belong to a // single strongly connected component using Kosaraju’s algorithm public static boolean isSC(Graph graph, int n) { // keep track of all previously visited vertices boolean[] visited = new boolean[n]; // find the first vertex `i` with a non-zero degree, and start DFS from it int i; for (i = 0; i < n; i++) { if (graph.adjList.get(i).size() > 0) { DFS(graph, i, visited); break; } } // return false if DFS couldn't visit all vertices with a non-zero degree if (!isVisited(graph, visited)) { return false; } // reset the visited array Arrays.fill(visited, false); // create a transpose of the graph Graph g = buildTranspose(graph, n); // perform DFS on the transpose graph using the same starting vertex as // used in the previous DFS call DFS(g, i, visited); // return true if second DFS also explored all vertices with a non-zero degree; // false otherwise return isVisited(g, visited); } // Function to check if a directed graph has an Eulerian cycle public static boolean hasEulerianCycle(Graph graph, int n) { // check if every vertex has the same in-degree and out-degree for (int i = 0; i < n; i++) { if (graph.adjList.get(i).size() != graph.in.get(i)) { return false; } } // check if all vertices with a non-zero degree belong to a single // strongly connected component return isSC(graph, n); } public static void main(String[] args) { // List of graph edges as per the above diagram List<Edge> edges = Arrays.asList(new Edge(0, 1), new Edge(1, 2), new Edge(2, 3), new Edge(3, 1), new Edge(1, 4), new Edge(4, 3), new Edge(3, 0)); // total number of nodes in the graph (labelled from 0 to 4) int n = 5; // build a directed graph from the above edges Graph graph = new Graph(edges, n); if (hasEulerianCycle(graph, n)) { System.out.println("The graph has an Eulerian cycle"); } else { System.out.println("The Graph does not contain Eulerian cycle"); } } } |
Output:
The graph has an Eulerian cycle
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 |
# A class to represent a graph object class Graph: def __init__(self, n, edges=[]): # resize both lists to hold `n` elements each self.adjList = [[] for _ in range(n)] self.indegree = [0] * n for edge in edges: self.addEdge(edge[0], edge[1]) # Function to add an edge (u, v) to the graph # and update in-degree for each edge def addEdge(self, u, v): # add an edge from source to destination self.adjList[u].append(v) # increment in-degree of destination vertex by 1 self.indegree[v] = self.indegree[v] + 1 # Function to perform DFS traversal on the graph def DFS(graph, v, discovered): discovered[v] = True # mark the current node as discovered # do for every edge (v, u) for u in graph.adjList[v]: if not discovered[u]: # `u` is not discovered DFS(graph, u, discovered) # Function to create transpose of a graph, i.e., the same graph # with the direction of every edge reversed def buildTranspose(graph, n): g = Graph(n) for u in range(n): # for every edge (u, v), create a reverse edge (v, u) # in the transpose graph for v in graph.adjList[u]: g.addEdge(v, u) return g # Function to check if all vertices of a graph with a non-zero degree are discovered def isdiscovered(graph, discovered): for i in range(len(discovered)): if len(graph.adjList[i]) and not discovered[i]: return False return True # Function to check if all vertices with a non-zero degree in a graph belong to a # single strongly connected component using Kosaraju’s algorithm def isSC(graph, n): # keep track of all previously discovered vertices discovered = [False] * n # find the first vertex `i` with a non-zero degree, and start DFS from it for i in range(n): if len(graph.adjList[i]): DFS(graph, i, discovered) break # return false if DFS couldn't visit all vertices with a non-zero degree if not isdiscovered(graph, discovered): return False # reset the discovered array discovered[:] = [False] * n # create a transpose of the graph g = buildTranspose(graph, n) # perform DFS on the transpose graph using the same starting vertex as # used in the previous DFS call DFS(g, i, discovered) # return true if second DFS also explored all vertices with a non-zero degree; # false otherwise return isdiscovered(g, discovered) # Function to check if a directed graph has an Eulerian cycle def hasEulerianCycle(graph, n): # check if every vertex has the same in-degree and out-degree for i in range(n): if len(graph.adjList[i]) != graph.indegree[i]: return False # check if all vertices with a non-zero degree belong to a single # strongly connected component return isSC(graph, n) if __name__ == '__main__': # List of graph edges as per the above diagram edges = [(0, 1), (1, 2), (2, 3), (3, 1), (1, 4), (4, 3), (3, 0)] # total number of nodes in the graph (labelled from 0 to 4) n = 5 # build a directed graph from the above edges graph = Graph(n, edges) if hasEulerianCycle(graph, n): print('The graph has an Eulerian cycle') else: print('The Graph does not contain Eulerian cycle') |
Output:
The graph has an Eulerian cycle
The time complexity of the above solution is the same as that of Kosaraju’s algorithm, i.e., O(V + E), where V and E are the total number of vertices and edges in the graph, respectively.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)