/*求一个图的所有m-着色方案*/ #define N_VER 5 /*定义图的顶点个数*/ #include <stdio.h> #include <malloc.h> #define LEN1 sizeof(struct BRANCH) #define LEN2 sizeof(struct H)

typedef struct /*顶点数据*/ { char color; /*顶点着的颜色*/ struct VER *con[N_VER]; /*邻接指针*/ int visited; int id; /*身份标志*/ }VER;

typedef struct /*树枝数据*/ { struct BRANCH *par; /*父结点*/ char color; /*颜色*/ struct BRANCH *son[4]; /*子结点*/

}BRANCH;

typedef struct { struct BRANCH *par; /*父结点*/ struct H *next; /*水平线上下一个(右边的)结点*/ }H;

void draw(VER *p); void mark(int id); void visit(VER *p); void set_root(); void getcon(VER *p,int con_col[]); void buildit(BRANCH *p,int vn); char getcolor(int i);

int trace[N_VER]; /*用来记录访问顶点的顺序*/ char colors[4]={'A','B','C','D'}; /*4种颜色*/ int use_col[4]={0}; /*用过了的颜色*/ BRANCH root; H *p_h,*p_go; p_go=p_h=(struct H *)malloc(LEN2); BRANCH *p_par;

void main() {

VER v[N_VER]; /*生成每个顶点*/

int i,m,i_v,i_con,i_col,rl[N_VER],n_color;

for(i=0;i<N_VER;i++) { trace[i]=-1; }

/*首先，通过输入邻接矩阵，构造图。并确定顶点之间的联系*/ printf("Now,enter the relation of the Graph by 0,1:\n\n"); printf(" "); for(i=0;i<N_VER;i++){printf(" %d",i+1);} printf("\n-------------\n"); for(i_v=0;i_v<N_VER;i_v++) {

printf("%d| ",i_v+1); for(i=0;i<N_VER;i++) /*输入关系*/ { scanf("%d",&rl[i]); }

for(i_con=0;i_con<N_VER;i_con++) /*构造当前顶点的邻顶点指针*/ { if (rl[i_con]==0) v[i_v].con[i_con]=NULL; /*0代表跟对应顶点没联系*/ else v[i_v].con[i_con]=&v[i_con]; /*1代表跟对应顶点有联系*/ } v[i_v].visited=0; /*设置为0，因为还没有访问*/ v[i_v].id=i_v; /*顶点0,1,2,3,4.....*/ v[i_v].color='0'; /*颜色为空,说明还没有着色*/ }

/*广度优先(怎么有点像深度优先)遍历图，并且算出图的色数， 同时还要记下访问顶点的顺序*/ /*当然从v[0]顶点开始访问*/ visit(&v[0]); /*看看还有没有未访问的*/ for(i_v=0;i_v<N_VER;i_v++) { if(v[i_v].visited==0) visit(&v[i_v]); } /**************************************************************/ /*到此,一定所有顶点都被访问了*/ /* 1.各顶点着了什么色? 2.总共用了几种颜色? 3.访问的顺序是什么? 4.是否所有顶点都被访问?*/ printf("\nEach color of the ver is: "); for(i_v=0;i_v<N_VER;i_v++) { printf("color_%c ",v[i_v].color); }

printf("\nThe list of color used is: "); for(i_col=0;i_col<4;i_col++) { printf("%d ",use_col[i_col]); } printf("\nThe order of visiting is: "); for(i_v=0;i_v<N_VER;i_v++) { printf("v%d ",trace[i_v]); } printf("\nIs all the ver be visited? "); for(i_v=0;i_v<N_VER;i_v++) { printf("%d ",v[i_v].visited); }

n_color=0; for(i=0;i<4;i++){n_color+=use_col[i];} printf("\nThe num of color used is: %d\n",n_color); /*色数*/

/**************************************************************/ /*现在已经知道了需要用几种颜色了,我们就创建所有m-方案*/ set_root(); for(i=0;i<n_color;i++) { buildit(root.son[i],0); /*注意:0是记录顶点访问次序的数组的下标*/

}

/**************************************************************/ /*倒序输出所有方案*/ p_go=p_h->next; p_par=p_go->par; m=1; while(p_go!=NULL) { printf("\n%d. ",m) while(p_par!=&root) { printf("%c ",p_par->color); p_par=p_par->par; } p_go=p_go->next; m++; }

/**************************************************************/ getch(); }

void visit(VER *p) /*访问该顶点，并准备访问它的所有邻接点*/ { /*

给该顶点着色 准备访问邻接点 访问过的就做标记1 到访问顺序数组中报道

着色思想： 因为前辈已经证明了任何图的色数<=4；所以我们先准备4种颜色A,B,C,D 我们还要知道已经用了哪几种颜色了 我们还要知道该顶点所有已经着色的邻接点的颜色 对该顶点着色的时候，从已经用的颜色中选择一种颜色， 但是这种颜色不能和邻接顶点的颜色相同 如果没颜色了，那么就再从准备好的颜色中选一种新颜色 如果还有，那就选择剩下的颜色中的一种 */ int i_con;

draw(p); /*着色*/ p->visited=1; /*访问标记*/ mark(p->id); /*顺序标记*/ /*访问邻接点*/ /*访问过了就不要再访问了*/

for(i_con=0;i_con<N_VER;i_con++) { if(p->con[i_con]!=NULL && p->con[i_con]->visited==0) { visit(p->con[i_con]); } } }

void draw(VER *p) { int con_col[4]={0}; /*所有邻接点的颜色*/ /*1.取得邻接点的颜色,2.着色后需要把本颜色添加在已经用的颜色中*/ int i_col; getcon(p,con_col); /*取得邻接点颜色*/

/*决定用哪种颜色*/ for(i_col=0;i_col<4;i_col++) { if(con_col[i_col]==0) /*就是这种颜色了*/ { p->color=colors[i_col]; /*着色*/ use_col[i_col]=1; /*已经用的颜色做标记*/ break; } }

}

void getcon(VER *p,int con_col[]) { int i_con,n_position; for(i_con=0;i_con<N_VER;i_con++) { if(p->con[i_con]!=NULL && p->con[i_con]->color!='0') /*如果有这个邻接点, 并且已经着了色*/ { switch(p->con[i_con]->color) { case 'A':n_position=0;break; case 'B':n_position=1;break; case 'C':n_position=2;break; case 'D':n_position=3;break; } con_col[n_position]=1; /*如果邻接点的颜色为B, 那么是第2种颜色被使用 所以,在邻接数组中的第 2个位置做上标记*/ }

}

}

void mark(int id) { int i; for(i=0;i<N_VER;i++) { if(trace[i]==-1){ trace[i]=id;break;} } }

void set_root() { int i; root.par=NULL; root.color='0'; for(i=0;i<n_color;i++) { root.son[i]=(struct BRANCH *)malloc(LEN1); root.son[i]->par=*root; root.son[i]->color=getcolor(i); }

}

void buildit(BRANCH *p,int vn) { int con_col[4]=0; int i; getcon(&v[trace[vn]],con_col); /*取得邻接点的颜色组*/ for(i=0;i<n_color;i++) { if(con_col[i]==0) /*邻接点没用到,但是use_col[]中有的 就给它发展下线*/ { p->son[i]=(struct BRANCH *)malloc(LEN1); p->son[i]->par=p; p->son[i]->color=getcolor(i); /*取得当前结点应该着的色*/ if(vn==N_VER-2) /*下一个(p->son[i])就是最后一个结点了*/ /*为了等下倒序输出,让它在铁路上注册登记*/ { p_go->next=(struct H *)malloc(LEN2); p_go->next->par=p->son[i]; p->go=p_go->next; } else /*如果不是的话,就继续回溯*/ buildit(p->son[i],nv+1); } else p->son[i]=NULL; } }

char getcolor(int i) { char mycolor; switch(i) { case 0:mycolor='A';break; case 1:mycolor='B';break; case 2:mycolor='C';break; case 3:mycolor='D';break; } return mycolor; }