C++ Programming Code Examples C++ > Computer Graphics Code Examples Check Whether an Undirected Graph Contains a Eulerian Path Check Whether an Undirected Graph Contains a Eulerian Path This is a C++ Program to check whether an undirected graph contains Eulerian Path. The criteran Euler suggested, 1. If graph has no odd degree vertex, there is at least one Eulerian Circuit. 2. If graph as two vertices with odd degree, there is no Eulerian Circuit but at least one Eulerian Path. 3. If graph has more than two vertices with odd degree, there is no Eulerian Circuit or Eulerian Path. // A C++ program to check if a given graph is Eulerian or not #include<iostream> #include <list> 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 public: // Constructor and destructor Graph(int V) { this->V = V; adj = new list<int> [V]; } ~Graph() { delete[] adj; } // To avoid memory leak // function to add an edge to graph void addEdge(int v, int w); // Method to check if this graph is Eulerian or not int isEulerian(); // Method to check if all non-zero degree vertices are connected bool isConnected(); // Function to do DFS starting from v. Used in isConnected(); void DFSUtil(int v, bool visited[]); }; void Graph::addEdge(int v, int w) { adj[v].push_back(w); adj[w].push_back(v); // Note: the graph is undirected } 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); } // Method to check if all non-zero degree vertices are connected. // It mainly does DFS traversal starting from bool Graph::isConnected() { // Mark all the vertices as not visited bool visited[V]; int i; for (i = 0; i < V; i++) visited[i] = false; // Find a vertex with non-zero degree for (i = 0; i < V; i++) if (adj[i].size() != 0) break; // If there are no edges in the graph, return true if (i == V) return true; // Start DFS traversal from a vertex with non-zero degree DFSUtil(i, visited); // Check if all non-zero degree vertices are visited for (i = 0; i < V; i++) if (visited[i] == false && adj[i].size() > 0) return false; return true; } /* The function returns one of the following values 0 --> If grpah is not Eulerian 1 --> If graph has an Euler path (Semi-Eulerian) 2 --> If graph has an Euler Circuit (Eulerian) */ int Graph::isEulerian() { // Check if all non-zero degree vertices are connected if (isConnected() == false) return 0; // Count vertices with odd degree int odd = 0; for (int i = 0; i < V; i++) if (adj[i].size() & 1) odd++; // If count is more than 2, then graph is not Eulerian if (odd > 2) return 0; // If odd count is 2, then semi-eulerian. // If odd count is 0, then eulerian // Note that odd count can never be 1 for undirected graph return (odd) ? 1 : 2; } // Function to run test cases void test(Graph &g) { int res = g.isEulerian(); if (res == 0) cout << "Graph is not Eulerian\n"; else if (res == 1) cout << "Graph has a Euler path\n"; else cout << "Graph has a Euler cycle\n"; } // Driver program to test above function int main() { // Let us create and test graphs shown in above figures Graph g1(5); g1.addEdge(1, 0); g1.addEdge(0, 2); g1.addEdge(2, 1); g1.addEdge(0, 3); g1.addEdge(3, 4); cout<<"Result for Graph 1: "; test(g1); Graph g2(5); g2.addEdge(1, 0); g2.addEdge(0, 2); g2.addEdge(2, 1); g2.addEdge(0, 3); g2.addEdge(3, 4); g2.addEdge(4, 0); cout<<"Result for Graph 2: "; test(g2); Graph g3(5); g3.addEdge(1, 0); g3.addEdge(0, 2); g3.addEdge(2, 1); g3.addEdge(0, 3); g3.addEdge(3, 4); g3.addEdge(1, 3); cout<<"Result for Graph 3: "; test(g3); // Let us create a graph with 3 vertices // connected in the form of cycle Graph g4(3); g4.addEdge(0, 1); g4.addEdge(1, 2); g4.addEdge(2, 0); cout<<"Result for Graph 4: "; test(g4); // Let us create a graph with all veritces // with zero degree Graph g5(3); cout<<"Result for Graph 5: "; test(g5); return 0; }