顶点着色的贪婪算法证明是存在的，即当前的算法得到只是给出最少颜色的一个上界。 算法描述：设G是一个图，它的顶点按某一顺序记为x1，x2,......xn. (1) 对顶点x1指定颜色1。 (2)对每个i=2，3，....n,令p是在顶点x1,x2,...xi-1与xi相邻接的顶点中没有任何一个顶点着色p的最小的颜色，并且xi指定颜色p。 数学书上的定理为：设G是一个图，对于该图顶点的最大度为△，那么贪婪算法X产生G的顶点的一个（△+1）着色，因此 X（G）<=△+1 #include <cstdio>#include <string> int a[26][26], n, m, ans, c[26], b[26];char s[26]; void greedy(){ int i, k; for(i = 0; i < n; i ++) {  memset(b, 0, sizeof(b));  for(k = 0; k < n; k ++)  {   if(a[i][k] && c[k] != -1)   {    b[c[k]] = 1;   }  }  for(k = 0; k <= i; k ++)  {   if(!b[k]) break;  }  c[i] = k; } for(i = 0; i < n; i ++) {  if(ans < c[i])   ans = c[i]; } ans ++;} void init(){ memset(a, 0, sizeof(a)); for(int i = 0; i < n; i ++) {  c[i] = -1; } ans = 0;} int main(){ //freopen("in.txt", "r", stdin); while(scanf("%d", &n) && n) {  int i, k;  init();  for(i = 0; i < n; i ++)  {   scanf("%s", &s);   m = strlen(s) - 2;   for(k = 0; k < m; k ++)   {    a[i][s[k + 2] - 'A'] = 1;    a[s[k + 2] - 'A'][i] = 1;   }  }  greedy();  if(ans != 1)   printf("%d channels needed.\n", ans);  else   printf("%d channel needed.\n", ans); } return 0;}   

评论