# How can i implement a program which checks if a graph is bipartite using BFS and adjacency lists?

I've been trying to solve a problem however i realized too late that it was more convenient to solve it using adjacency matrix.So how can i do it by using BFS and adjencey lists instead?

Here is what I managed to do until now:

main function and main source code

#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
#include "graph.h"
#include "queue.h"
#include "isbipartite.h"
#include<assert.h>
main()
{
bool has_path = false;
bool is_not_in_graph = true;
graph g;
int start_Vertex;
int i;
print_graph(&g);
printf("\n Which vertex do you want to start from?(P.S:Make sure it is in the graph!)");
scanf("%d", &start_Vertex);
for (i = 1; i <= g.no_vertices; i++)
if (start_Vertex == i)
is_not_in_graph = false;
assert(is_not_in_graph==false);
if (!is_not_in_graph) {
printf("\n===Doing a BFS traversal===:\n");
bfs(&g, start_Vertex);
}
system("pause");
}

graph.c

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include "graph.h"
#include<assert.h>
void init_graph(graph *g) {
g->no_tunnels = 0;
g->no_vertices = 0;
for (int i = 1; i <= MAXV; i++) {
g->tunnels[i] = NULL;
g->visited[i] = false;
}

}
int i;
int initial_node;
int final_node;
init_graph(g);
scanf("%d %d", &g->no_vertices, &g->no_tunnels);
for (i = 1; i <= g->no_tunnels; i++) {
scanf("%d %d", &initial_node, &final_node);
assert(initial_node != final_node);  //avoiding self-loop
create_edge(g,initial_node,final_node,has_path);
}
}
void create_edge(graph *g,int initial_node,int final_node,bool has_path) {
edgenode* p;
p = malloc(sizeof(edgenode));
p->no_tower = final_node;
p->next_tower = g->tunnels[initial_node];
g->tunnels[initial_node] = p;
if(!has_path)
create_edge(g, final_node, initial_node,true);
}
void print_graph(graph *g) {
int i;
edgenode *p;
for (i = 1; i <= g->no_vertices; i++) {
printf("%d ", i);
p = g->tunnels[i];
while (p != NULL) {
printf(" %d", p->no_tower);
p = p->next_tower;
}
printf("\n");
}
}

queue.c

#include "queue.h"
#include "graph.h"
bool isEmpty(Queue *q) {
if (q->rear ==0)
return true;
else
return false;
}
int dequeue(Queue *q) {
int item;
if (isEmpty(q)) {
printf("Queue is empty");
item = 0;
}
else {
item = q->items[q->front];
q->front++;
if (q->front > q->rear) {
printf("Reseting queue...");
q->front = q->rear = 0;
}
}
return item;
}
void enqueue(Queue *q, int value) {
if (q->rear == MAXV)
printf("Queue is full");
else
{
if (q->front == 0)
q->front = 1;
q->rear++;
q->items[q->rear] = value;
}
}
void print_Queue(Queue *q) {
int i = q->front;
if (isEmpty(q)) {
printf("Queue is empty");
}
else {
printf("Queue contains \n");
for (i = q->front; i < q->rear + 1; i++)
printf("%d ", q->items[i]);
}
}

isbipartite.c

#include "isbipartite.h"
#include"graph.h"
#include"queue.h"
void bfs(graph *g, int startVertex) {
Queue* q;
edgenode* temp;
q = (Queue*)malloc(sizeof(Queue));//allocating memory for queue
q->front = 0;    //initiates queue
q->rear = 0;
g->visited[startVertex] = true;
enqueue(q, startVertex);
while (!isEmpty(q)) {
print_Queue(q);
int current_vertex = dequeue(q);
printf("Visited %d\n", current_vertex);
temp = g->tunnels[current_vertex];

while (temp) {

}
temp = temp->next_tower;

}
}
}

graph.h

#ifndef GRAPH_H
#define GRAPH_H
#define MAXV 1000
#include<stdlib.h>
#include<stdio.h>
#include<stdbool.h>
typedef struct edgenode {
int no_tower;
char type_of_tower;
struct edgenode *next_tower;
}edgenode;
typedef struct graph {
int no_vertices;
int no_tunnels;  // number of edges
edgenode *tunnels[MAXV+1]; // edeges themselves(connections between vertices)
bool visited[MAXV + 1];
//int haspath[MAXV + 1][MAXV + 1];
}graph ;
void init_graph(graph *g);
void create_edge(graph *g,int initial_node,int final_node,bool has_path);
void print_graph(graph *g);
#endif // !GRAPH_H

queue.h

#ifndef QUEUE_H
#define QUEUE_H
#include "graph.h"
#include<stdbool.h>
typedef struct queue {
int items[MAXV + 1];
int front;
int rear;

}Queue;
void enqueue(Queue *q, int value);
int dequeue(Queue *q);
bool isEmpty(Queue* q);
void print_Queue(Queue* q);
#endif // !1

isbipartite.h

#include"graph.h"
#include"queue.h"
void bfs(graph * g, int startVertex);