The Algorithm Design Manualでは、著者はグラフを 2 色で着色するためのアルゴリズムを提供しています。これは、コンポーネントの数をカウントするアルゴリズムに似ています。使用可能なすべての頂点を反復処理し、検出されない場合にのみ、その頂点に色を付けて 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]);
}
ここで、次のようなグラフがあるとします。
次のように 2 色にできます。
ただし、頂点の順序でトラバースする場合は、最初に node から開始し、それを に1色付けしWHITEます。次に、ノードを見つけ13て に色付けしBLACKます。ループの次の反復では、ノードが検出されてい5ないため、色をWHITE付けて BFS を開始します。これを行っている間に、ノード5との間の競合が検出されます。次に、 と の間に別の矛盾があることを発見します。11BLACKWHITE11313WHITEBLACK
すべてのコンポーネント (接続されているかどうかに関係なく) を介してグラフの通常のトラバーサルを実行する場合、いずれにせよすべてのノードにアクセスすることになるため、順序は問題になりませんが、グラフに色を付ける場合は順序が問題になるようです。私は本でこれについての言及を見たことがなく、上記のようなランダムに生成されたグラフを 2 色にしようとしたときにのみ、この問題に出くわしました。既存のアルゴリズムに小さな変更を加えることができたので、この問題は解消されました。
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.バッハの回答に基づいて、次のグラフがあると仮定します。
どうすればこれが適切に 2 色になるのか、私はまだ混乱しています。元のアルゴリズムでは、最初の反復でノードを使用して BFS が開始され、次1のような色のグラフが得られます。
次の反復では、ノード5を使用して BFS を開始し、次のような色のグラフを表示します。
次の反復では、ノードを使用して BFS を開始し、次6のような色のグラフを表示します。
しかし、ここで5は既にアクセス済みであるため、色を変更しません。これにより、適切に色付けされていないグラフが残ります。