Check whether a directed graph is Eulerian
Given a directed graph, check whether it has an Eulerian path or not. An Eulerian path (or Eulerian trail) is a path in a graph that visits every edge exactly once.
The following graph has an Eulerian path since it is possible to construct a path that visits each edge exactly once. The Eulerian path is 0 —> 1 —> 2 —> 3 —> 0 —> 5 —> 4 —> 3 —> 1 —> 4.
Related Post:
A directed graph has an Eulerian path if and only if the following conditions are satisfied:
- At most one vertex in the graph has
out-degree = 1 + in-degree, and at most one vertex in the graph hasin-degree = 1 + out-degree. All the remaining vertices havein-degree == out-degree. - All vertices with a non-zero degree belong to a single connected component of the underlying undirected graph. In other words, if one removes the “directness” of edges, then the graph without isolated vertices should be connected.
For example, in the above graph, the only vertex 0 has out-degree one more than the in-degree, and vertex 4 has in-degree one more than the out-degree. Every other vertex has equal in-degree and out-degree, and the non-isolated vertices are weakly connected. The algorithm can be implemented as follows in C++, Java, and Python:
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 164 165 |
#include <iostream> #include <vector> 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: // vector of vectors to represent an adjacency list vector<vector<int>> adjList; // vector to store in-degree of each vertex in the graph vector<int> in; // Constructor Graph(int n) { // resize both vectors to hold `n` elements each adjList.resize(n); in.resize(n); } // Utility function to add an edge (u, v) to the graph // and update in-degree for each edge 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 replace all the directed edges of the graph with undirected edges // and produce an undirected graph Graph getUndirectedGraph(Graph const &graph, int n) { Graph g(n); // do for every edge (u, v) for (int u = 0; u < n; u++) { for (int v: graph.adjList[u]) { g.addEdge(v, u); g.addEdge(u, v); } } return g; } // Function to check if all vertices with a non-zero degree in a graph // belong to a single connected component bool isConnected(Graph const &graph, int n) { // keep track of all previously visited vertices in DFS vector<bool> visited(n); // start DFS from the first vertex with a non-zero degree for (int i = 0; i < n; i++) { if (graph.adjList[i].size()) { DFS(graph, i, visited); break; } } // if a single DFS call couldn't visit all vertices with a non-zero degree, // the graph contains more than one connected component for (int i = 0; i < n; i++) { if (!visited[i] && graph.adjList[i].size() > 0) { return false; } } return true; } // Function to check if a directed graph has an Eulerian path bool hasEulerPath(Graph const &graph, int n) { /* The following loop checks the following conditions to determine if an Eulerian path can exist or not: a. At most one vertex in the graph has `out-degree = 1 + in-degree`. b. At most one vertex in the graph has `in-degree = 1 + out-degree`. c. Rest all vertices have `in-degree == out-degree`. If either of the above condition fails, the Euler path can't exist. */ bool x = false, y = false; for (int i = 0; i < n; i++) { int out_degree = graph.adjList[i].size(); int in_degree = graph.in[i]; if (out_degree != in_degree) { if (!x && out_degree - in_degree == 1) { x = true; } else if (!y && in_degree - out_degree == 1) { y = true; } else { return false; } } } // consider given edges as undirected and check if all non-isolated vertices // belong to a single connected component return isConnected(getUndirectedGraph(graph, n), 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}, {0, 5}, {5, 4} }; // total number of nodes in the graph (labelled from 0 to 5) int n = 6; // build a directed graph from the above edges Graph graph(n); // add edges to the directed graph for (auto &edge: edges) { graph.addEdge(edge.src, edge.dest); } if (hasEulerPath(graph, n)) { cout << "The graph has an Eulerian path" << endl; } else { cout << "The Graph doesn't have an Eulerian path" << endl; } return 0; } |
Output:
The graph has an Eulerian path
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 |
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)); } // 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 replace all the directed edges of the graph with undirected edges // and produce an undirected graph public static Graph getUndirectedGraph(Graph graph, int n) { Graph g = new Graph(n); for (int u = 0; u < n; u++) { for (int v: graph.adjList.get(u)) { // for every edge (u, v) g.addEdge(v, u); g.addEdge(u, v); } } return g; } // Function to check if all vertices with a non-zero degree in a graph // belong to a single connected component public static boolean isConnected(Graph graph, int n) { // keep track of all previously visited vertices in DFS boolean[] visited = new boolean[n]; // start DFS from the first vertex with a non-zero degree for (int i = 0; i < n; i++) { if (graph.adjList.get(i).size() > 0) { DFS(graph, i, visited); break; } } // if a single DFS call couldn't visit all vertices with a non-zero degree, // the graph contains more than one connected component for (int i = 0; i < n; i++) { if (!visited[i] && graph.adjList.get(i).size() > 0) { return false; } } return true; } // Function to check if a directed graph has an Eulerian path public static boolean hasEulerPath(Graph graph, int n) { /* The following loop checks the following conditions to determine if an Eulerian path can exist or not: a. At most one vertex in the graph has `out-degree = 1 + in-degree`. b. At most one vertex in the graph has `in-degree = 1 + out-degree`. c. Rest all vertices have `in-degree == out-degree`. If either of the above condition fails, the Euler path can't exist. */ boolean x = false, y = false; for (int i = 0; i < n; i++) { int out_degree = graph.adjList.get(i).size(); int in_degree = graph.in.get(i); if (out_degree != in_degree) { if (!x && out_degree - in_degree == 1) { x = true; } else if (!y && in_degree - out_degree == 1) { y = true; } else { return false; } } } // consider given edges as undirected and check if all non-isolated vertices // belong to a single connected component return isConnected(getUndirectedGraph(graph, n), 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), new Edge(0, 5), new Edge(5, 4) ); // total number of nodes in the graph (labelled from 0 to 5) int n = 6; // build a directed graph from the above edges Graph graph = new Graph(n); // add edges to the directed graph for (Edge edge: edges) { graph.addEdge(edge.source, edge.dest); } if (hasEulerPath(graph, n)) { System.out.println("The graph has an Eulerian path"); } else { System.out.println("The Graph doesn't have an Eulerian path"); } } } |
Output:
The graph has an Eulerian path
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 |
# A class to represent a graph object class Graph: def __init__(self, n): # resize both lists to hold `n` elements each self.adjList = [[] for _ in range(n)] self.indegree = [0] * n # 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 replace all the directed edges of the graph with undirected edges # and produce an undirected graph def getUndirectedGraph(graph, n): g = Graph(n) # do for every edge (u, v) for u in range(n): for v in graph.adjList[u]: g.addEdge(v, u) g.addEdge(u, v) return g # Function to check if all vertices with a non-zero degree in a graph # belong to a single connected component def isConnected(graph, n): # keep track of all previously discovered vertices in DFS discovered = [False] * n # start DFS from the first vertex with a non-zero degree for i in range(n): if len(graph.adjList[i]): DFS(graph, i, discovered) break # if a single DFS call couldn't visit all vertices with a non-zero degree, # the graph contains more than one connected component for i in range(n): if not discovered[i] and len(graph.adjList[i]): return False return True # Function to check if a directed graph has an Eulerian path def hasEulerPath(graph, n): ''' The following loop checks the following conditions to determine if an Eulerian path can exist or not: a. At most one vertex in the graph has `out-degree = 1 + in-degree`. b. At most one vertex in the graph has `in-degree = 1 + out-degree`. c. Rest all vertices have `in-degree == out-degree`. If either of the above condition fails, the Euler path can't exist. ''' x = y = False for i in range(n): out_degree = len(graph.adjList[i]) in_degree = graph.indegree[i] if out_degree != in_degree: if not x and out_degree - in_degree == 1: x = True elif not y and in_degree - out_degree == 1: y = True else: return False # consider given edges as undirected and check if all non-isolated vertices # belong to a single connected component return isConnected(getUndirectedGraph(graph, n), 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), (0, 5), (5, 4)] # total number of nodes in the graph (labelled from 0 to 5) n = 6 # build a directed graph from the above edges graph = Graph(n) # add edges to the directed graph for edge in edges: graph.addEdge(edge[0], edge[1]) if hasEulerPath(graph, n): print('The graph has an Eulerian path') else: print('The Graph doesn\'t have an Eulerian path') |
Output:
The graph has an Eulerian path
The time complexity of the above solution is 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 :)