Как я могу реализовать программу, которая проверяет, является ли граф двудольным, используя BFS и списки смежности?

Question

Я пытался решить проблему, однако слишком поздно осознал, что ее удобнее решать с помощью матрицы смежности. Так как я могу это сделать, используя вместо этого BFS и списки смежности?

Вот что мне удалось сделать до сих пор:

основная функция и основной исходный код

#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;
    read_graph(&g,has_path);
    print_graph(&g);
    //print_adj_matrix(&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;
    }

}
void read_graph(graph *g,bool has_path) {
    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) {
            int adjVertex = temp->no_tower;
            if (!g->visited[adjVertex]) {
                g->visited[adjVertex] = true;

                enqueue(q, adjVertex);
            }
            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 read_graph(graph *g,bool has_path);
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);