C++ Program to Implement Euler Circuit Problem

This C++ program displays the Euler Circuit Problem in which a particular circuit starts and ends on the same vertex by visiting each edge exactly once.

Here is the source code of the C++ program to display whether the particular undirected graphs given as input are Eulerian or not. This C++ program is successfully compiled and run on DevCpp, a C++ compiler. The program output is given below.

```
/*
```

 * C++ Program to Implement Euler Circuit Problem

```
 */
```
```
#include<iostream>
```
```
#include<conio.h>
```
```
#include<list>
```
```
using namespace std;
```
```
 
```
```
class Graph
```
```
{
```
```
    int V;   
```
```
    list<int> *adj;
```
```
public:
```
```
    Graph(int V)
```
```
    {
```
```
        this->V = V;
```
```
        adj = new list<int>[V];
```
```
    }
```
```
    void addEdge(int v, int w);
```
```
 
```
```
    int isEulerian();
```
```
 
```
```
    bool isConnected();
```
```
 
```

    void DFSUtil(int v, bool visited[]);

```
};
```
```
 
```
```
void Graph::addEdge(int v, int w)
```
```
{
```
```
    adj[v].push_back(w);
```
```
    adj[w].push_back(v); 
```
```
}
```
```
 
```

void Graph::DFSUtil(int v, bool visited[])

```
{
```
```
    visited[v] = true;
```
```
 
```
```
    list<int>::iterator i;
```

    for (i = adj[v].begin(); i != adj[v].end(); ++i)

```
    {
```
```
        if (!visited[*i])
```
```
        {
```
```
            DFSUtil(*i, visited);
```
```
        }
```
```
    }
```
```
}
```
```
bool Graph::isConnected()
```
```
{
```
```
    bool visited[V];
```
```
    int i;
```
```
    for (i = 0; i < V; i++)
```
```
    {
```
```
        visited[i] = false;
```
```
    }
```
```
    for (i = 0; i < V; i++)
```
```
    {
```
```
        if (adj[i].size() != 0)
```
```
        {
```
```
            break;
```
```
        }
```
```
    }
```
```
    if (i == V)
```
```
    {
```
```
        return true;
```
```
    }
```
```
    DFSUtil(i, visited);
```
```
    for (i = 0; i < V; i++)
```
```
    {
```

        if (visited[i] == false && adj[i].size() > 0)

```
        {
```
```
            return false;
```
```
        }
```
```
    }
```
```
    return true;
```
```
}
```
```
int Graph::isEulerian()
```
```
{
```
```
    if (isConnected() == false)
```
```
    {
```
```
        return 0;
```
```
    }
```
```
    int odd = 0;
```
```
    for (int i = 0; i < V; i++)
```
```
    {
```
```
        if (adj[i].size() & 1)
```
```
        {
```
```
            odd++;
```
```
        }
```
```
    }
```
```
    if (odd > 2)
```
```
    {
```
```
        return 0;
```
```
    }
```
```
    return (odd)? 1 : 2;
```
```
}
```
```
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";

```
    }
```
```
}
```
```
int main()
```
```
{
```
```
    Graph g1(5);
```
```
    g1.addEdge(1, 0);
```
```
    g1.addEdge(0, 2);
```
```
    g1.addEdge(2, 1);
```
```
    g1.addEdge(0, 3);
```
```
    g1.addEdge(3, 4);
```
```
    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);
```
```
    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);
```
```
    test(g3);
```
```
 
```
```
    Graph g4(3);
```
```
    g4.addEdge(0, 1);
```
```
    g4.addEdge(1, 2);
```
```
    g4.addEdge(2, 0);
```
```
    test(g4);
```
```
 
```
```
    Graph g5(3);
```
```
    test(g5);
```
```
 
```
```
    getch();
```
```
}
```

Output
Graph has a Euler path
Graph has a Euler cycle
Graph is not Eulerian
Graph has a Euler cycle
Graph has a Euler cycle

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

If you wish to look at all C++ Programming examples, go to C++ Programs.

« Prev - C++ Program to Implement Ford Fulkerson Algorithm

» Next - C++ Program to Find Maximum Number of Edge Disjoint Paths

Related Posts:

Recommended Articles: