c - C : Unable to identify the logical error 中的图形着色

Question

我正在尝试用 C 实现图形着色算法，该实现基于我们如何通过遍历邻接矩阵来分配颜色。在为第二个顶点分配颜色后，我无法得到它。

这是我的程序代码:

int n, a[10][10], i, j, k, c[10], max = 0, col, ct = 0, rt = 0, m, count = 2;
void main() {
    printf("enter n\n");
    scanf("%d", &n);
    printf("enter the Adjacency Matrix for %d rows and %d columns\n", n, n);
    for (i = 0; i < n; i++) {
       c[i] = 0;
       for (j = 0; j < n; j++)
           scanf("%d", &a[i][j]);
    }
    c[0] = 1;
    c[1] = 2;
    for (i = 1; i < n; i++) {  
        for (j = 0; j < n; j++)
            if (a[i][j] > 0) {  
                m = 0;
                for (col = 0; col < n; col++) {
                    if (a[i][col] > 0)
                        rt++;
                    if (a[col][i] > 0)
                        ct++;
                }
                m = rt;
                if (ct > rt)
                    m = ct;
                if (m < 2) {
                    if (a[0][i] > 0)
                        c[i] = 2;
                    else
                        c[i] = 1;
                } else {
                    c[i] = count;
                    if (m > max) {
                        max = m;
                        count++;
                    }
                }    
                rt = 0;
                ct = 0;
            }
        if (c[i] < 1)
            if (c[i - 1] > 1)
                c[i] = 1;
            else
                c[i] = 2;
    }
    printf("The proper coloring is\n");
    for (i = 0; i < n; i++)
        printf("c%d=%d ", i + 1, c[i]);
    printf("\n");
}

示例输入:考虑一个完整的图:

0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0

预期输出:

c1=1 c2=2 c3=3 c4=4

观察到的输出:

c1=1 c2=2 c3=3 c4=3

Answer 1

错误似乎在逻辑上，正如您可能已经从问题标题的外观中推断出的那样。您检查 m 是否大于 max 然后相应地更新 max 和 count 的条件语句似乎不正确。

我无法确切地弄清楚预期的逻辑是什么，但我可以说出它为什么不正确。

在您的用法中，您将遇到的最大邻居数保留在 max 中，并在找到具有更多邻居的顶点时更新它。有了它，您还可以更新计数，我认为它具有当前最高值的颜色。现在，除非你在每一步(遍历每一行)遇到一个有更多邻居的顶点，否则你不会更新最大值，因此你不会更新计数。因此，除非您遇到这样的顶点，否则您会一直为遇到的所有顶点分配相同的当前最高计数。

你应该更多地解释一下你实现的算法。但是，仅通过查看您的代码，我认为您至少应该在不同的地方增加计数。

一个好主意可能是让一个数组等于顶点的数量。然后对于每个顶点(在最外层循环内)，您可以重置数组并通过遍历第 i 个^th 顶点的所有邻居，您可以设置它们中使用的颜色，并选择最小的未使用颜色。

这可能不是最有效的方法，但您已经有了 O(n³) 算法，所以我认为采用这种方法不会有什么坏处。

下面是您的代码，已更新以反射(reflect)我提到的更改。

int n,a[10][10],i,j,k,c[10],max=0,col,ct=0,rt=0,m,count=2;
int used[11]; /* indices used are from 1 to n, inclusive */
void main()
{
    printf("enter n\n");
    scanf("%d",&n);
    printf("enter the Adjacency Matrix for %d rows and %d columns\n",n,n);   
    for(i=0; i < n ; i++)
    {
        c[i]=0;
        for(j=0;j<n;j++)
            scanf("%d",&a[i][j]);
    }
    c[0]=1;
    c[1]=2;
    for(i = 1 ;i < n;i++)
    {
        for(j = 1 ;j <= n ;j++)
            used[j] = 0;
        for(j = 0 ;j < i ;j++)
        {
            if(a[i][j] > 0)
                used[c[j]] = 1;
        }
        for(j = 1 ;j <= n ;j++)
            if(!used[j])
            {
                c[i] = j;
                break;
            }
    }
    printf("The proper coloring is\n");
    for(i = 0;i < n ;i++)
            printf("c%d=%d ",i+1,c[i]);
        printf("\n");
}