C++ Programming Code Examples

C++ > Computer Graphics Code Examples

Check whether Graph is a Bipartite using 2 Color Algorithm



Check whether Graph is a Bipartite using 2 Color Algorithm

    #include <iostream>

    #include <cstdio>

    #define V 4

    using namespace std;

    /* A utility function to check if the current color assignment is safe for vertex v       */

    bool isSafe (int v, bool graph[V][V], int color[], int c)

    {

        for (int i = 0; i < V; i++)

            if (graph[v][i] && c == color[i])

                return false;

        return true;

    }

    /* A recursive utility function to solve m coloring problem      */

    bool graphColoringUtil(bool graph[V][V], int m, int color[], int v)

    {

        if (v == V)

            return true;

        for (int c = 1; c <= m; c++)

        {

            if (isSafe(v, graph, color, c))

            {

                color[v] = c;

                if (graphColoringUtil (graph, m, color, v+1) == true)

                    return true;

               color[v] = 0;

            }

        }

        return false;

    }

    /* This function solves the m Coloring problem using Backtracking.     */

    bool graphColoring(bool graph[V][V], int m)

    {

        int *color = new int[V];

        for (int i = 0; i < V; i++)

           color[i] = 0;

        if (graphColoringUtil(graph, m, color, 0) == false)

            return false;

        return true;

    }

    /* Main Contains Menu     */

    int main()

    {

        bool graph[V][V] = {{0, 1, 1, 1},

            {1, 0, 1, 0},

            {1, 1, 0, 1},

            {1, 0, 1, 0},

        };

        bool gr[V][V] = {{0, 1, 0, 1},

            {1, 0, 1, 0},

            {0, 1, 0, 1},

            {1, 0, 1, 0}

        };

        int m = 2;

        if (graphColoring (graph, m))

            cout<<"The graph 1 is Bipartite"<<endl;

        else

            cout<<"The graph 1 is not Bipartite"<<endl;

        if (graphColoring (gr, m))

            cout<<"The graph 2 is Bipartite"<<endl;

        else

            cout<<"The graph 2 is not Bipartite"<<endl;

        return 0;

    }