无向图的3-着色(C语言）代码

#include<stdio.h>
#define INITIAL -1
int graph[100][100];		//图的邻接矩阵
int N,M;			//顶点数&边数
int colour[100];
int sum=0;
int initial(){			//对整个图形初始化
    for(int i=0;i<100;i++){
	colour[i]=0;			//0代表每个顶点没涂颜色
	for(int j=0;j<100;j++)
   	    graph[i][j]=INITIAL;		//无边连接
    }  
}
int CreateGraph(){		//邻接矩阵的方式创建图形
    int start,end;
    printf("请输入顶点数,边数:");	
    scanf("%d,%d",&N,&M);
    printf("请输入图的邻接矩阵");
    for(int i=0;i<M;i++){
       scanf("%d,%d",&start,&end);
       graph[start][end] = graph[end][start] = 1;
    }
    return 1;
} 
int isok(int point){		//这一步是判断某个顶点上这个颜色是否合法
    for(int i=0;i<N;i++){		//只需要看和他相邻的顶点颜色是否相同，相同则不合法返回0
    if(graph[point][i] == 1 && (colour[point] == colour[i]))
                  return 0;
    }
    return 1;
}
int Colour(int start){		//下面开始上色
    int i,j;
    if(start == N){		//只要最开始的顶点经过不断的递归后达到顶点数说明已完成一种涂色,可以看成是递归出口
    for(j=0;j<N;j++)		//打印
       printf("point:%d colour:%dn",j,colour[j]);
    sum++;			//数量++
 }
 else{
     for(i=1;i<=3;i++){		//每个顶点依次试这三种颜色
        colour[start]=i;		
        if(isok(start)){		//如果涂的颜色合法则进行下一个顶点着色
           Colour(start+1);
      }
      colour[start]=0;  		//这步回溯可以回到上一个顶点进行下一个颜色的试色
    }
  } 
}
int main(){
    initial();
    CreateGraph();
    Colour(0); 
    printf("着色方案:%d",sum);
}

各位博友们你们好！这是本人第一篇文章，如有内容不当之处欢迎指正，谢谢大家。

最后

以上就是欣慰小笼包为你收集整理的无向图的3着色问题(C语言)无向图的3-着色(C语言）代码的全部内容，希望文章能够帮你解决无向图的3着色问题(C语言)无向图的3-着色(C语言）代码所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。