0

在The Algorithm Design Manual中，作者提供了一种对图进行两种着色的算法。它类似于计算组件数量的算法，因为它迭代所有可用顶点，然后仅在未发现该顶点时对该顶点着色并执行 BFS：

for(i = 1; i <= (g->nvertices); i++) {
    if(discovered[i] == FALSE) {
        color[i] = WHITE;
        bfs(g, i);
    }
}

BFS在边缘没有被处理或者图是有向的process_edge时候调用一个函数。BFS 看起来像这样：yx -> y

bfs(graph *g, int start) {

    queue q; //queue of vertices to visit
    int v; //current vertex
    int y; //successor vertex
    edgenode* p; //temporary pointer used to traverse adjacency list

    init_queue(&q);
    enqueue(&q, start);
    discovered[start] = TRUE;

    while(empty_queue(&q) == FALSE) {
        v = dequeue(&q);

        process_vertex_early(v); //function that handles early processing
        processed[v] = TRUE;
        p = g->edges[v];

        while(p != NULL) {
            y = p->y;

            //If the node hasn't already been processed, or if the graph is directed
            //process the edge. This part bothers me with undirected graphs
            //because how would you process an edge that was wrongly colored
            //in an earlier iteration when it will have processed[v] set to TRUE?
            if((processed[y] == FALSE) || g->directed) {
                process_edge(v, y); //coloring happens here
            }

            if(discovered[y] == FALSE) {
                enqueue(&q, y);
                discovered[y] = TRUE;
                parent[y] = v;
            }

            p = p->next;
        }

        process_vertex_late(v); //function that handles late processing
    }
}

该process_edge函数如下所示：

process_edge(int x, int y) {
    if(color[x] == color[y]) {
        bipartite = FALSE;
        printf("Warning: not bipartite due to (%d, %d)\n", x, y);
    }

    color[y] = complement(color[x]);
}

现在假设我们有一个这样的图表：

在此处输入图像描述

我们可以像这样对它进行两种着色：

在此处输入图像描述

但是，如果我们按顶点顺序遍历它，那么我们最初将从 node 开始1，并将其着色为WHITE。然后我们将找到节点13并将其着色为BLACK. 在循环的下一次迭代中，我们正在查看5未发现的节点，因此我们将对其着色WHITE并在其上启动 BFS。在执行此操作时，我们会发现节点之间存在冲突5，1因为1应该是BLACK，但之前设置为WHITE。1然后我们会发现and之间的另一个冲突13，因为13应该是WHITE，但它被设置为BLACK。

当通过所有组件（连接或未连接）执行图的正常遍历时，顺序无关紧要，因为无论如何我们最终都会访问所有节点，但是在为图着色的情况下顺序似乎很重要。我没有在书中看到提到这一点，只是在我尝试对上面的随机生成的图形进行双色着色时才遇到这个问题。我能够对现有算法进行一些小改动，从而消除了这个问题：

for(i = 1; i <= (g->nvertices); i++) {
    //Only initiate a BFS on undiscovered vertices and vertices that don't
    //have parents.
    if(discovered[i] == FALSE && parent[i] == NULL) {
        color[i] = WHITE;
        bfs(g, i);
    }
}

这种变化是否有意义，还是因为我不理解一些基本概念而造成的？

更新

根据 G. Bach 的回答，假设我们有以下图表：

在此处输入图像描述

我仍然对这将如何正确地变成双色感到困惑。使用原始算法，第一次迭代将启动一个带节点的 BFS，1为我们提供一个颜色如下的图：

在此处输入图像描述

在下一次迭代中，我们将启动一个带节点的 BFS，5为我们提供一个颜色如下的图：

在此处输入图像描述

下一次迭代将启动一个带节点的 BFS，6为我们提供一个像这样着色的图：

在此处输入图像描述

但是现在我们不会重新着色5，因为我们已经访问过它，所以这给我们留下了一个没有正确着色的图表。

4

2 回答 2

1

图形的有向性质与您提出的二分着色问题无关，除非您定义了一个不同的问题，其中方向确实开始很重要。因此，您可以将示例中使用的图转换为无向图并运行教科书中给出的算法。

虽然教科书没有明确提到图应该是无向的，但边缘方向与我们研究的常见着色问题无关。但是，您可以定义考虑边缘方向的问题（http://www.labri.fr/perso/sopena/pmwiki/index.php?n=TheOrientedColoringPage.TheOrientedColoringPage）。

注意：我打算写这个作为评论，但是作为一个新手，我不允许这样做，直到我积累一些声望点。

于 2013-12-01T02:07:14.390 回答
0

使用 BFS 着色二分图不依赖于顶点顺序。调用构成二部图 A 和 B 的分区的两个顶点集；WLOG 从aA 的顶点开始，将其着色为白色；第一个 BFS 将找到邻居N(a)，它们都将被着色为黑色。对于每个v in N(a)with all v in B，这将启动一个 BFS（如果我没看错的话），找到N(v)它的子集A，将它们全部着色为白色等等。

如果您尝试使用它为非二分图着色，您将遇到一个奇数长度的循环（因为有这样一个循环作为子图相当于不是二分的）并且 BFS 将在某个时候遇到再次那个奇怪的循环，发现它已经有一种颜色，但不是它想要分配给它的颜色。

我假设您的图表会发生什么（因为您从 1 开始在 BFS 中不包括 5）是它是有向的；我假设您阅读的算法是为无向图编写的，否则您确实会遇到您描述的问题。此外，着色图通常在无向图上定义（当然可以转移到有向图）。

您的修复一般不会解决问题；添加一个新的顶点6和边6->24，你会遇到同样的问题。开始的 BFS5将要涂成1黑色，从 开始的 BFS6将要涂成白色。但是，该图仍然是 2-colorable。

于 2013-04-08T02:05:29.160 回答