# C++ Program to Check whether a Graph is Bipartite using 2 Color Algorithm

This C++ Program checks whether Graph is a Bipartite using 2 Color Algorithm

Here is source code of the C++ Program to check whether Graph is a Bipartite using 2 Color Algorithm. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

1. `/*`
2. ` * C++ Program to Check whether Graph is a Bipartite using 2 Color Algorithm`
3. ` */`
4. `#include <iostream>`
5. `#include <cstdio>`
6. `#define V 4`
7. `using namespace std;`
8. `/* `
9. ` * A utility function to check if the current color assignment`
10. ` * is safe for vertex v  `
11. ` */`
12. `bool isSafe (int v, bool graph[V][V], int color[], int c)`
13. `{`
14. `    for (int i = 0; i < V; i++)`
15. `        if (graph[v][i] && c == color[i])`
16. `            return false;`
17. `    return true;`
18. `}`
19. ` `
20. `/* `
21. ` * A recursive utility function to solve m coloring problem `
22. ` */`
23. `bool graphColoringUtil(bool graph[V][V], int m, int color[], int v)`
24. `{`
25. `    if (v == V)`
26. `        return true;`
27. `    for (int c = 1; c <= m; c++)`
28. `    {`
29. `        if (isSafe(v, graph, color, c))`
30. `        {`
31. `            color[v] = c;`
32. `            if (graphColoringUtil (graph, m, color, v+1) == true)`
33. `                return true;`
34. `           color[v] = 0;`
35. `        }`
36. `    }`
37. `    return false;`
38. `}`
39. ` `
40. `/* `
41. ` * This function solves the m Coloring problem using Backtracking.`
42. ` */`
43. `bool graphColoring(bool graph[V][V], int m)`
44. `{`
45. `    int *color = new int[V];`
46. `    for (int i = 0; i < V; i++)`
47. `       color[i] = 0;`
48. `    if (graphColoringUtil(graph, m, color, 0) == false)`
49. `        return false;`
50. `    return true;`
51. `}`
52. ` `
53. `/* `
54. ` * Main Contains Menu `
55. `*/`
56. `int main()`
57. `{`
58. `    bool graph[V][V] = {{0, 1, 1, 1},`
59. `        {1, 0, 1, 0},`
60. `        {1, 1, 0, 1},`
61. `        {1, 0, 1, 0},`
62. `    };`
63. `    bool gr[V][V] = {{0, 1, 0, 1},`
64. `        {1, 0, 1, 0},`
65. `        {0, 1, 0, 1},`
66. `        {1, 0, 1, 0}`
67. `    };`
68. `    int m = 2;`
69. `    if (graphColoring (graph, m))`
70. `        cout<<"The graph 1 is Bipartite"<<endl;`
71. `    else`
72. `        cout<<"The graph 1 is not Bipartite"<<endl;`
73. `    if (graphColoring (gr, m))`
74. `        cout<<"The graph 2 is Bipartite"<<endl;`
75. `    else`
76. `        cout<<"The graph 2 is not Bipartite"<<endl;`
77. `    return 0;`
78. `}`

```\$ g++ bipartite_2color.cpp
\$ a.out
The graph 1 is not Bipartite
The graph 2 is Bipartite

------------------
(program exited with code: 1)

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