algorithm - 尝试对有向图进行双色处理时，顶点顺序是否重要？

Question

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

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

当边缘 x -> y 中的 y 未被处理时，或者如果图形是有向的，BFS 将调用 process_edge 函数。 BFS 看起来像这样:

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

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

我们可以像这样对它进行双色处理:

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

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

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 的 answer ，假设我们有以下图表:

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

在下一次迭代中，我们将启动一个具有节点 5 的 BFS 来为我们提供一个颜色如下所示的图:

下一次迭代将启动一个具有节点 6 的 BFS，为我们提供一个颜色如下所示的图:

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

Answer 1

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

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

注意:我本来打算把这个写成评论的，但是作为一个新手，我不能这样做，直到我积累了一些声望点。