一般图的着色

原本这是离散数学的期末作业，因为对图论比较熟悉，就先看了一下图论题；

引用《离散数学（左孝凌版）》（其实就是我们的离散数学课本……）：

用韦尔奇·鲍威尔法对图G进行着色，其方法是：
　　a）将图G中的节点按照度数的递减次序进行排列。（这种排列可能并不是唯一的，因为有些点有相同度数。）
　　b）用第一种颜色对第一点着色，并且按排列次序，对与前面着色点不邻接的每一点着上同样的颜色。
　　c）用第二种颜色对尚未着色的点重复b），用第三种颜色继续这种做法，直到所有的点全部着上色为止。

然后直接照着码成代码即可：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #define MAX 25
 5 using namespace std;
 6 bool edge[MAX][MAX];
 7 struct Vertex{
 8     int color,degree;
 9 }vertex[MAX];
10 int n,m;//n个点，m条边
11 void calc_degree()//计算每个点的度数
12 {
13     for(int i=1;i<=n;i++)
14     {
15         vertex[i].color=vertex[i].degree=0;
16         for(int j=1;j<=n;j++) vertex[i].degree+=edge[i][j];
17     }
18 }
19 bool cmp(Vertex a,Vertex b){return a.degree>b.degree;}
20 int main()
21 {
22     while(scanf("%d%d",&n,&m)!=EOF)//输入图的点数和边数
23     {
24         memset(edge,0,sizeof(edge));//初始化邻接矩阵
25         for(int i=1,u,v;i<=m;i++)
26         {
27             scanf("%d%d",&u,&v);
28             edge[u][v]=edge[v][u]=1;
29         }
30         calc_degree();
31         sort(vertex+1,vertex+n+1,cmp);
32         int colored_vertices_cnt=0;
33         int ncolor=0;
34         while(colored_vertices_cnt<n)
35         {
36             ncolor++;
37             for(int i=1;i<=n;i++)
38             {
39                 if(vertex[i].color) continue;
40                     //如果已经着色就跳过
41 
42                 bool ok=1;
43                 for(int j=1;j<=n;j++)
44                 {
45                     if(!edge[i][j]) continue;
46                     if(vertex[j].color==ncolor)
47                     {
48                         ok=0;
49                         break;
50                     }
51                 }
52                 if(!ok) continue;
53                     //如果邻接的点有相同颜色就跳过
54                 
55                 vertex[i].color=ncolor;
56                 colored_vertices_cnt++;
57                 printf("vertex[%d]=%d
",i,vertex[i].color);
58             }
59         }
60         printf("%d
",ncolor);
61     }
62 }