In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets $U$ and $V$ such that every edge connects a vertex in $U$ to one in $V$. Vertex sets $U$ and $V$ are usually called the parts of the graph.

The two sets $U$ and $V$ may be thought of as a coloring of the graph with two colors: if one colors all nodes in $U$ blue, and all nodes in $V$ green, each edge has endpoints of differing colors, as is required in the graph coloring problem. In contrast, such a coloring is impossible in the case of a non-bipartite graph, such as a triangle: after one node is colored blue and another green, the third vertex of the triangle is connected to vertices of both colors, preventing it from being assigned either color.

Write a program that checks if a graph is Bipartite.

Difficulty level
This exercise is mostly suitable for students 
#include<stdio.h>
#include<stdlib.h>
#define N 100

typedef int element;

typedef struct 
{
	element data[N]; /* queue content */
	int front, length;
} queue;


typedef struct node {
	int vertexNumber;
	struct node * next;
} node;
typedef struct {
	int V;
	int E;
	node** Adj;  //array of linked list
} Graph;




queue CreateQueue()
{
	queue q;
	q.front = 0; q.length=0;
	return q;
}
int isEmptyQueue(queue q)
{
	return q.length == 0;
}

int isFullQueue(queue q)
{
	return q.length ==N;
}

int EnQueue(queue *q, element e)
{
	if (isFullQueue(*q)) return 0;
	q->data[(q->front + q->length)%N] = e;
	q->length = q->length + 1;
	return 1;
}

int DeQueue(queue *q)
{
	if (isEmptyQueue(*q)) return 0;
	q->front=(q->front + 1) % N;
	q->length--;
	return 1;
}

int Front(queue q, element *e)
{
	if (isEmptyQueue(q)) return 0;
	*e = q.data[q.front];
	return 1;
}

 




Graph* adjacencyList() {
	int i, x, y;
	node * temp, *temp2;
	Graph* G=(Graph*) malloc(sizeof(Graph));

//	printf("Enter the number of Vertices: ");
	scanf("%d", &G->V);
//	printf("Enter the number of Edges: ");
	scanf("%d", &G->E);
	G->Adj = (node **)malloc(G->V * sizeof(node));
	for (i = 0; i < G->V; i++) {
		G->Adj[i] = (node *)malloc(G->V * sizeof(node));
		G->Adj[i]->vertexNumber = i;
		G->Adj[i]->next = NULL;
	}
 
	for (i = 0; i < G->E; i++) {
	//	printf("Enter the edge: ");
		scanf("%d %d", &x,&y);
		temp = (node*)malloc(sizeof(node));
		temp->vertexNumber = y;
        temp->next = NULL;
        
		temp2 = G->Adj[x];
		while (temp2->next != NULL)
			temp2 = temp2->next;
		temp2->next = temp;
		
	}
	return G;
}

int BFSTraversal(Graph *G, int index, int Visited[], int Color[]) {
	queue q;
	element e;
    	node * head;
   	int isBipartite;

	isBipartite=1;
	q=CreateQueue();
 
	EnQueue(&q,index);
	Visited[index] = 1;
	Color[index]=0;

	while(Front(q,&e) && isBipartite)
	{
	    DeQueue(&q);
	     
	    head=G->Adj[e]->next;
	    while(head)
	    {
	        if(Color[head->vertexNumber]==-1)
	        {
			Color[head->vertexNumber] = 1-Color[e];
	            	EnQueue(&q,head->vertexNumber);
	        }
		else
			if(Color[head->vertexNumber]==Color[e])
			{
				isBipartite=0;
				break;
			}
	        head = head->next;
	    }
	}
	if(isBipartite==0)
		return 0;
	return 1;
}

int BFS(Graph *G) {
	int i;
	int *Visited;
	int *Color;

 	Visited = (int *)malloc(G->V * sizeof(int));
	Color = (int *)malloc(G->V * sizeof(int));
	for (i = 0; i < G->V; i++)
	{
		Visited[i] = 0;
		Color[i]=-1;
	}

	// this loop is required if the graph has more than one component
	for (i = 0; i < G->V; i++)
		if (!Visited[i])
			if(!BFSTraversal(G, i, Visited,Color))
				return 0;
	return 1;
}



void test() {
	Graph *G = adjacencyList();
	if(BFS(G))
		printf("YES\n");
	else
		printf("NO\n");
}

int main()
{
    int tests;
    scanf("%d",&tests);
    while(tests--)
    {
	    test();
    }
	return 0;
}
Back to the list of exercises
Looking for a more challenging exercise, try this one !!
Graph Edge Property