C Program to Check Whether a Given Graph is Bipartite or not

This is a C Program to check if a graph is Bipartite. A bipartite graph or bigraph is a graph whose vertices can be divided into two disjoint sets P and Q (that is, P and Q are each completely independent sets) such that every edge connects a vertex in P to one in Q. Vertex set P and Q are often denoted as partite sets. Also it does not contain any odd-length cycles.

Here is source code of the C Program to Check if a Given Graph is Bipartite. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

```
#include <stdio.h>
```
```
#define V 4
```
```
/*
```

 * A utility function to check if the current color assignment

```
 * is safe for vertex v
```
```
 */
```

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

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

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

```
            return 0;
```
```
    return 1;
```
```
}
```
```
/*
```

 * A recursive utility function to solve m coloring problem

```
 */
```

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

```
    int c;
```
```
    if (v == V)
```
```
        return 1;
```
```
    for (c = 1; c <= m; c++) {
```

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

```
            color[v] = c;
```

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

```
                return 1;
```
```
            color[v] = 0;
```
```
        }
```
```
    }
```
```
    return 0;
```
```
}
```
```
/*
```

 * This function solves the m Coloring problem using Backtracking.

```
 */
```

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

    int *color = malloc(V * sizeof(int[V]));

```
    int i;
```
```
    for (i = 0; i < V; i++)
```
```
        color[i] = 0;
```

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

```
        return 0;
```
```
    return 1;
```
```
}
```
```
/*
```
```
 * Main Contains Menu
```
```
 */
```
```
int main() {
```
```
    int graph[V][V] = { { 0, 1, 1, 1 },
```
```
                        { 1, 0, 1, 0 },
```
```
                        { 1, 1, 0, 1 },
```
```
                        { 1, 0, 1, 0 },
```
```
                      };
```
```
    int 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))
```

        printf("The graph 1 is Bipartite\n");

```
    else
```

        printf("The graph 1 is not Bipartite\n");

```
    if (graphColoring(gr, m))
```

        printf("The graph 2 is Bipartite\n");

```
    else
```

        printf("The graph 2 is not Bipartite\n");

```
    return 0;
```
```
}
```

Output:

$ gcc CheckBipartite.c
$ ./a.out
 
The graph 1 is not Bipartite
The graph 2 is Bipartite

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 if Graph is DAG

» Next - C Program to Implement Branch and Bound Method

Related Posts:

Recommended Articles: