C++ Program to Check Whether a Directed Graph Contains a Eulerian Path

«
»
This is a C++ Program to check whether 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.

Here is source code of the C++ Program to Check Whether a Directed Graph Contains a Eulerian Path. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. // A C++ program to check if a given graph is Eulerian or not
  2. #include<iostream>
  3. #include <list>
  4. using namespace std;
  5.  
  6. // A class that represents an undirected graph
  7. class Graph
  8. {
  9.         int V; // No. of vertices
  10.         list<int> *adj; // A dynamic array of adjacency lists
  11.     public:
  12.         // Constructor and destructor
  13.         Graph(int V)
  14.         {
  15.             this->V = V;
  16.             adj = new list<int> [V];
  17.         }
  18.         ~Graph()
  19.         {
  20.             delete[] adj;
  21.         } // To avoid memory leak
  22.  
  23.         // function to add an edge to graph
  24.         void addEdge(int v, int w);
  25.  
  26.         // Method to check if this graph is Eulerian or not
  27.         int isEulerian();
  28.  
  29.         // Method to check if all non-zero degree vertices are connected
  30.         bool isConnected();
  31.  
  32.         // Function to do DFS starting from v. Used in isConnected();
  33.         void DFSUtil(int v, bool visited[]);
  34. };
  35.  
  36. void Graph::addEdge(int v, int w)
  37. {
  38.     adj[v].push_back(w);
  39. }
  40.  
  41. void Graph::DFSUtil(int v, bool visited[])
  42. {
  43.     // Mark the current node as visited and print it
  44.     visited[v] = true;
  45.  
  46.     // Recur for all the vertices adjacent to this vertex
  47.     list<int>::iterator i;
  48.     for (i = adj[v].begin(); i != adj[v].end(); ++i)
  49.         if (!visited[*i])
  50.             DFSUtil(*i, visited);
  51. }
  52.  
  53. // Method to check if all non-zero degree vertices are connected.
  54. // It mainly does DFS traversal starting from
  55. bool Graph::isConnected()
  56. {
  57.     // Mark all the vertices as not visited
  58.     bool visited[V];
  59.     int i;
  60.     for (i = 0; i < V; i++)
  61.         visited[i] = false;
  62.  
  63.     // Find a vertex with non-zero degree
  64.     for (i = 0; i < V; i++)
  65.         if (adj[i].size() != 0)
  66.             break;
  67.  
  68.     // If there are no edges in the graph, return true
  69.     if (i == V)
  70.         return true;
  71.  
  72.     // Start DFS traversal from a vertex with non-zero degree
  73.     DFSUtil(i, visited);
  74.  
  75.     // Check if all non-zero degree vertices are visited
  76.     for (i = 0; i < V; i++)
  77.         if (visited[i] == false && adj[i].size() > 0)
  78.             return false;
  79.  
  80.     return true;
  81. }
  82.  
  83. /* The function returns one of the following values
  84.  0 --> If grpah is not Eulerian
  85.  1 --> If graph has an Euler path (Semi-Eulerian)
  86.  2 --> If graph has an Euler Circuit (Eulerian)  */
  87. int Graph::isEulerian()
  88. {
  89.     // Check if all non-zero degree vertices are connected
  90.     if (isConnected() == false)
  91.         return 0;
  92.  
  93.     // Count vertices with odd degree
  94.     int odd = 0;
  95.     for (int i = 0; i < V; i++)
  96.         if (adj[i].size() & 1)
  97.             odd++;
  98.  
  99.     // If count is more than 2, then graph is not Eulerian
  100.     if (odd > 2)
  101.         return 0;
  102.  
  103.     // If odd count is 2, then semi-eulerian.
  104.     // If odd count is 0, then eulerian
  105.     // Note that odd count can never be 1 for undirected graph
  106.     return (odd) ? 1 : 2;
  107. }
  108.  
  109. // Function to run test cases
  110. void test(Graph &g)
  111. {
  112.     int res = g.isEulerian();
  113.     if (res == 0)
  114.         cout << "Graph is not Eulerian\n";
  115.     else if (res == 1)
  116.         cout << "Graph has a Euler path\n";
  117.     else
  118.         cout << "Graph has a Euler cycle\n";
  119. }
  120.  
  121. // Driver program to test above function
  122. int main()
  123. {
  124.     // Let us create and test graphs shown in above figures
  125.     Graph g1(5);
  126.     g1.addEdge(1, 0);
  127.     g1.addEdge(0, 2);
  128.     g1.addEdge(2, 1);
  129.     g1.addEdge(0, 3);
  130.     g1.addEdge(3, 4);
  131.     cout<<"Result for Graph 1: ";
  132.     test(g1);
  133.  
  134.     Graph g2(5);
  135.     g2.addEdge(1, 0);
  136.     g2.addEdge(0, 2);
  137.     g2.addEdge(2, 1);
  138.     g2.addEdge(0, 3);
  139.     g2.addEdge(3, 4);
  140.     g2.addEdge(4, 0);
  141.     cout<<"Result for Graph 2: ";
  142.     test(g2);
  143.  
  144.     Graph g3(5);
  145.     g3.addEdge(1, 0);
  146.     g3.addEdge(0, 2);
  147.     g3.addEdge(2, 1);
  148.     g3.addEdge(0, 3);
  149.     g3.addEdge(3, 4);
  150.     g3.addEdge(1, 3);
  151.     cout<<"Result for Graph 3: ";
  152.     test(g3);
  153.  
  154.     // Let us create a graph with 3 vertices
  155.     // connected in the form of cycle
  156.     Graph g4(3);
  157.     g4.addEdge(0, 1);
  158.     g4.addEdge(1, 2);
  159.     g4.addEdge(2, 0);
  160.     cout<<"Result for Graph 4: ";
  161.     test(g4);
  162.  
  163.     // Let us create a graph with all veritces
  164.     // with zero degree
  165.     Graph g5(3);
  166.     cout<<"Result for Graph 5: ";
  167.     test(g5);
  168.  
  169.     return 0;
  170. }

Output:

advertisement
$ g++ EulerianPathDirected.cpp
$ a.out
 
Result for Graph 1: Graph is not Eulerian
Result for Graph 2: Graph is not Eulerian
Result for Graph 3: Graph has a Euler path
Result for Graph 4: Graph is not Eulerian
Result for Graph 5: Graph has a Euler cycle
 
------------------
(program exited with code: 0)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

advertisement
advertisement

Here’s the list of Best Books in C++ Programming, Data Structures and Algorithms.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.