[原创]图4色问题

#include <stdio.h>
#include <string.h>
#define NG 5
typedef int Tgraph[NG][NG]; /*定义二维数组类型Tgraph*/

void fourcolord(Tgraph g,int n,int m,int* sel,int t) {/*递归输出所有结果*/
int i,f;
if(t==n) {
printf("\n->");
for(i=0;i<n;i++) printf("%d ",sel[i]);
}
else {
for(i=1;i<=m;i++) {
*(sel+t)=i;
for(f=0;f<n&&!(g[t][f]&&sel[t]==sel[f]);f++);
if(f==n) fourcolord(g,n,m,sel,t+1);
}
}
}

void fourcolor(Tgraph g,int n,int m) { /*只输出一个结果*/
int i,t=0;
int sel[NG]={0};
while(t>=0) {
if(sel[t]<m) { /*检查赋值越界*/
sel[t++]=++sel[t];
for(i=0;i<n&&!(g[t-1][i]&&sel[t-1]==sel[i]);i++); /*检查邻结点冲突*/
if(i<n) --t; /*冲突退栈*/
else if(t==n) { /*一个可行方案*/
for(i=0;i<n;i++) printf("%d ",sel[i]);
t=-1; /*t=-1退出循环*/
}
}
else --t; /*越界退栈*/
}
}

main() {
Tgraph g={0};
int sel[NG]={0};
g[0][1]=g[1][0]=g[0][2]=g[2][0]=1;
g[0][3]=g[3][0]=g[1][2]=g[2][1]=1;
g[1][3]=g[3][1]=g[1][4]=g[4][1]=1;
g[2][3]=g[3][2]=g[3][4]=g[4][3]=1;
fourcolor(g,NG,4); /*NG为图结点个数,4为可用颜色的数目*/
fourcolord(g,NG,4,sel,0);
}