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

Code:

#include    iostream
#include    list
using namespace std;

// A class that represents an undirected graph
class Graph
{
        int V; // No. of vertices
        list *adj; // A dynamic array of adjacency lists
    public:
        // Constructor and destructor
        Graph(int V)
        {
            this->V = V;
            adj = new list [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);
}

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::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:

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


More C++ Programs: