C++ Program to 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.

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

// 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;
```
```
}
```

Output:

$ g++ EulerianPathUndirected.cpp
$ a.out
 
Result for Graph 1: Graph has a Euler path
Result for Graph 2: Graph has a Euler cycle
Result for Graph 3: Graph is not Eulerian
Result for Graph 4: Graph has a Euler cycle
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.

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

If you find any mistake above, kindly email to [email protected]

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

» Next - C++ Program to Remove the Edges in a Cyclic Graph such that its Linear Extension can be Found

Related Posts:

Recommended Articles: