C++ Program to Check Whether an Undirected Graph Contains a Eulerian Cycle

C++ Program to Check Whether an Undirected Graph Contains a Eulerian Cycle The article is a lively article because it contains interesting information and your favorite.   

C++ Program to Check Whether an Undirected Graph Contains a Eulerian Cycle

C++ Program to Check Whether an Undirected Graph Contains a Eulerian Cycle

// 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 Euleriann";
    else if (res == 1)
        cout << "Graph has a Euler pathn";
    else
        cout << "Graph has a Euler cyclen";
}
 
// 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;
}

Read Also: C++ Program to Solve a Matching Problem for a Given Specific Case

Final Words

I hope you find the article C++ Program to Check Whether an Undirected Graph Contains a Eulerian Cycle uses. The reason is that we have told you all the information through this article in a way that you can understand. And if you have any doubts, you can express your doubts through the comment box. We also ask that you help share this article with your friends.

Hi, I'm Ranjith a full-time Blogger, YouTuber, Affiliate Marketer, & founder of Coding Deekshi. Here, I post about programming to help developers.

Share on:

Leave a Comment