Euler Circuit in a Directed Graph - GeeksforGeeks
We have discussed eulerian circuit for an undirected graph. In this post, same is discussed for a directed graph.
How to check if a directed graph is eulerian?
A directed graph has an eulerian cycle if following conditions are true (Source: Wiki)
1) All vertices with nonzero degree belong to a single strongly connected component.
2) In degree and out degree of every vertex is same.
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 an out degree of every vertex. Out degree can be obtained by size of adjacency list. In degree can be stored by creating an array of size equal to number of vertices.
Read full article from Euler Circuit in a Directed Graph - GeeksforGeeks
We have discussed eulerian circuit for an undirected graph. In this post, same is discussed for a directed graph.
How to check if a directed graph is eulerian?
A directed graph has an eulerian cycle if following conditions are true (Source: Wiki)
1) All vertices with nonzero degree belong to a single strongly connected component.
2) In degree and out degree of every vertex is same.
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 an out degree of every vertex. Out degree can be obtained by size of adjacency list. In degree can be stored by creating an array of size equal to number of vertices.
/* This function returns true if the directed graph has an 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;}void addEdge(int v, int w) { adj[v].push_back(w); (in[w])++; }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 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 degree 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. // Staring 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;}