设计并实现了一种改进的宽度优先搜索算法，以检测图是否为二部图。如果一个无向图的节点可以被染成红色和蓝色，即每条边的一端的节点是红色的，另一端是蓝色的，则称为二部图。如果可能的话，该算法也应该进行着色。原始代码在下。请注意，您可能必须使用多个连接的组件为图形着色，因此，您应该确保处理了所有的顶点。将您的程序应用到下面的图表中（每个只有一个连接组件）（在第一个，着色色应该是可能的，在第二个不是）
bfsgraph.h,不能修改
#ifndef BFSGRAPH_H_INCLUDED
#define BFSGRAPH_H_INCLUDED
// Header file for breadth-first search
#include <limits.h>
// Maximum number of vertices
// define according to your needs
#define MAXVERTS 1000
// Nodes are numbered as integers from 1
// Colors for color table
#define WHITE 0
#define GREY 1
#define BLACK 2
// Maximum value in the distance table
#define INF INT_MAX
// Defines edge in the adjacency list
typedef struct bfsedgnd {
int nodenum;
struct bfsedgnd* next;
} bfsedgenode, *pbfsedgenode;
// Defines the graph
typedef struct bfsg {
pbfsedgenode adj_list[MAXVERTS+1];
int pred[MAXVERTS+1];
int dist[MAXVERTS+1];
int color[MAXVERTS+1];
int nVertices;
} bfsgraph;
// Initializes graph for breadth-first search
void init_graph(bfsgraph* g, int vertices);
// Adds new edge (x,y)
void add_edge(bfsgraph* g, int x, int y);
// Actual breadth-first search from node s
void bfsearch(bfsgraph* g, int s);
// Frees allocated memory
void delete_graph(bfsgraph* g, int vertices);
#endif
bfsmain.c,想要着色时可以修改
// DSA Programming task 4.3 - Bicoloring
// Do changes here once you want to try your bi coloring.
// Base file using breadth-first search
#include <stdio.h>
#include "bfsgraph.h"
int main(){
// Define and initialize graph with 8 nodes
// Nodes are assumed to be integers 1..8
bfsgraph g;
init_graph(&g,8);
// Add some edges:
add_edge(&g,1,2);
add_edge(&g,1,4);
add_edge(&g,1,5);
add_edge(&g,2,3);
add_edge(&g,3,4);
add_edge(&g,5,6);
add_edge(&g,6,7);
add_edge(&g,6,8);
// Do breadth-first search
bfsearch(&g,1);
//Uncomment when ready
/* // The other graph - add this one to see that coloring is not possible
// add_edge(&g,2,4);
if (bicolor(&g,colors) == 0) {
printf("Coloring is not possible!\n");
}
else {
int i;
printf("Coloring is possible:\n");
for (i=1; i <= 8; i++) {
printf("Node[%d] = ",i);
colors[i]==RED?printf("RED\n"):printf("BLUE\n");
}
}
*/
// Delete graph
delete_graph(&g,8);
return 0;
}
bfsgraph.c，对TODO所在区域(bfsearch函数)的算法修改，具体方式详情见原始代码部分的注释，按照TODO注释部分进行修改
// DSA Programming task 4.3 - Bicoloring
// You work on this files where the TODO is
#include <stdio.h>
#include <stdlib.h>
#include "bfsgraph.h"
// Code file for breadth-first search
// Initializes graph for breadth-first search
void init_graph(bfsgraph* g, int vertices){
g->nVertices = vertices;
int i;
for(i=1; i <= vertices; i++) {
g->adj_list[i] = 0;
g->pred[i] = 0;
g->dist[i] = INF;
g->color[i] = WHITE;
}
}
// Adds new edge (x,y)
void add_edge(bfsgraph* g, int x, int y){
if( x <= g->nVertices && y <= g->nVertices){
pbfsedgenode pxy = malloc(sizeof(bfsedgenode));
pbfsedgenode pyx = malloc(sizeof(bfsedgenode));
pxy->nodenum = y;
pxy->next = g->adj_list[x];
g->adj_list[x] = pxy;
// Remove this if the graph is directed:
pyx->nodenum = x;
pyx->next = g->adj_list[y];
g->adj_list[y] = pyx;
}
}
/*
Algorithm for breadth first search
BFS(G,s)
1. for each u in V
2. color[u] = WHITE
3. d[u] = INF
4. p[u] = NIL
5. d[s] = 0
6. color[s] = GRAY
7. Q = EMPTY
8. ENQUEUE(Q,s)
9. while Q != EMPTY
10. u = DEQUEUE(Q)
11. for each v in Adj[u]
12. if color[v] == WHITE
13. color[v] = GRAY
14. d[v] = d[u]+1
15. p[v] = u
16. ENQUEUE(Q,v)
17. color[u] = BLACK
18. return
*/
// Actual breadth-first search from node s
// TODO
// You can modify this algorithm or copy it and modify the copy.
// Change the funciton to be int instead of void and return 1 if
// bicoloring is possible, and 0 if it is not possible.
// In addition to predecessor table, distance table, and color table, you need an additional color tabel
void bfsearch(bfsgraph* g, int s){
int queue[MAXVERTS];
int head = 0;
int tail = 0;
int i=0;
for(i=1; i <= g->nVertices; i++) {
g->pred[i] = 0;
g->dist[i] = INF;
g->color[i] = WHITE;
}
g->dist[s] = 0;
g->color[s] = GREY;
queue[tail] = s;
tail++;
while( head != tail) {
int u = queue[head];
head++;
pbfsedgenode pedge = g->adj_list[u];
while(pedge != 0){
int v = pedge->nodenum;
if(g->color[v] == WHITE) {
g->color[v] = GREY;
g->dist[v] = g->dist[u] +1;
g->pred[v] = u;
queue[tail] = v;
tail++;
}
pedge = pedge->next;
}
// DEBUG INFO:
printf("%d processed: d[%d] = %d\n",u,u,g->dist[u]);
g->color[u] = BLACK;
}
}
// Free allocated memory
void delete_graph(bfsgraph* g, int vertices){
int i;
for(i=1; i <= vertices; i++) {
pbfsedgenode pedge = g->adj_list[i];
pbfsedgenode pnext = 0;
while(pedge != 0) {
pnext = pedge->next;
free(pedge);
pedge = pnext;
}
}
}
