C 中的图形着色：无法识别逻辑错误

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");
}

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

预期输出：

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³) 算法，所以我认为这样做不会有什么坏处.

以下是您的代码，已更新以反映我提到的更改。

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");
}

Answer 2

为顶点着色的简单算法是什么样的？

考虑循环中的所有顶点并分配颜色。访问过的顶点已经有颜色；仍将被访问的顶点仍未着色。
确定已着色的相邻顶点使用哪些颜色。
根据这些信息，选择尽可能低的颜色。

你的算法是什么样的：

将颜色 1 分配给顶点 1，将颜色 2 分配给顶点 2。（请注意，如果顶点 2 未连接，则可以使用与顶点 1 相同的颜色。）
遍历所有剩余的顶点；然后遍历连接到它的所有顶点。
计算另一个循环中到第二个顶点的传入和传出链接的数量。（请注意，仅计算链接数并不能为您提供有关哪些颜色仍然可用的信息。例如，您可以使用颜色 3 和 4 着色许多顶点，但是您可以根据链接数来设置新颜色。在这个例子中, 颜色 1 会是一个不错的选择。)
您选择新颜色的标准是链接数是否大于或等于 2。然后您分配 count，但在增加它之前。这为您提供了示例中的第二个 3，其中应该有一个 4.

所以你循环次数太多，选色标准差。不要计算 lonks，您应该在相邻节点中保留一个已用颜色的列表，并将您的新颜色基于该列表。

您的代码的其他风格问题：

你所有的变量都应该是 main 的本地变量；没有理由将它们设为全局，尤其是因为您不使用函数。
请更加系统地声明您的变量。将它们全部放在一个大定义中，甚至将数组和标量混为一谈，使它们难以理解。
请在所有代码块周围使用大括号，即使它们不是绝对必要的。它使阅读代码更容易。内部块中没有 else 的小 if s，例如 if (ct > rt) m = ct; 不需要大括号，但请考虑在其他地方使用它们。

C 中的图形着色：无法识别逻辑错误

Graph Coloring in C: Unable to identify the logical error

c

graph

vertex