2

BFS を使用してグラフの色分けを実装できないかと考えた結果、以下の疑似コードのアプローチを思いつきました。

貪欲なアルゴリズムのように見えますが、正確かどうかはわかりません。専門家のコメントはありますか？

colors[MAX_COLORS];
colorsUsedSoFar[] = NIL;
like BFS, color first node u with colors[0] i.e color[u] = colors[0];
colorsUsedSoFar[] += colors[0];

for each node v adjacent to u{
  (if v not already colored){
     color[v] = color from the colorsUsedSoFar[] but NotUsedByItsAdjacents
     If all the colors in colorsUsedSoFar[] are used by adjacents, assign a new color to v)
  }
}

「BFS のように」とは、Queue を使用し、Queue が使い果たされるまで処理することを意味しました。

4

2 に答える 2

1

アルゴリズムでグラフを BFS の順序で色付けしたい場合は、 for ループ内で色付けした後にノードをキューに追加しなかったことを除いて、アルゴリズムが正しければ完全に問題ないと思います。そして、それは一種の貪欲なアプローチでもあります。レベルに応じて最初に色付けするノードを貪欲に選択しています。単純な貪欲ではありませんが、ちょっと私は言います。

于 2013-05-25T12:01:00.220 に答える
1

これは貪欲なカラーリング アルゴリズムの例です。

幅優先探索 (BFS) は暗黙的に順序付けを選択します。

したがって、アルゴリズムは正しいですが、常に最適な色 (つまり、使用される色の最小数) が得られるとは限りません。

より一般的な順序付けは、ウェルシュ・パウエル アルゴリズムとして知られる次数で頂点を順序付けることです。

于 2013-05-24T17:10:46.217 に答える