在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
重新着色,因为我们已经访问过它,所以这给我们留下了一个没有正确着色的图表。
最佳答案
图形的定向性质与您提出的二分着色问题无关,除非您定义方向确实开始重要的不同问题。因此,您可以将示例中使用的图转换为无向图,然后按照教科书中给出的方式运行算法。
虽然课本上没有明确提到图应该是无向的,但边的方向与我们研究的常见着色问题无关。但是,您可以定义考虑边缘方向的问题 ( http://www.labri.fr/perso/sopena/pmwiki/index.php?n=TheOrientedColoringPage.TheOrientedColoringPage )。
注意:我本来打算把这个写成评论的,但是作为一个新手,我不能这样做,直到我积累了一些声望点。
关于algorithm - 尝试对有向图进行双色处理时,顶点顺序是否重要?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15870093/