グラフ彩色

グラフ彩色の問題は、グラフラベリングの特殊なケースです。この問題では、各ノードがいくつかの色に色分けされています。しかし、着色にはいくつかの制約があります。隣接する頂点に同じ色を使用することはできません。

この問題を解決するには、欲張りアルゴリズムを使用する必要がありますが、最小色を使用することを保証するものではありません。

入力と出力

入力：グラフの隣接行列0 0 1 0 10 0 1 1 11 1 0 1 00 1 1 0 11 1 0 1 0出力：ノード：0、色で割り当て：0ノード：1、色で割り当て：0ノード：2、色で割り当て：1ノード：3、色で割り当て：2ノード：4、色で割り当て：1 

アルゴリズム

グラフ彩色（グラフ）

入力- 与えられたグラフ。

出力- いくつかの色が割り当てられた各ノード。

色のリストの宣言を開始します。最初のノードの色を0に設定し、配列colorUsedを定義して、使用された色と使用されたことのない色を追跡します。最初の1つを除くすべての頂点iについて、iを任意の色に割り当てられていないものとしてマークします。が割り当てられていない場合は、colorUsed [color [v]]：=trueをマークし、カラーリスト内のすべての色の列に対して実行します。色が使用されていない場合は実行し、ループを停止します。 uに隣接して、color [v]が割り当てられていない場合は、colorUsed [color [v]]：=falseを実行し、グラフ内のすべての頂点uに対して実行し、ノードとその色を表示します。 
例
 
 #include  #define NODE 6using namespace std; intgraph [NODE] [NODE] ={{0、1、1、1、0、0}、{1、0、0、1、1、 0}、{1、0、0、1、0、1}、{1、1、1、0、1、1}、{0、1、0、1、0、1}、{0、0、 1、1、1、0}}; voidgraphColoring（）{int color [NODE]; color [0] =0; //最初のノードに最初の色を割り当てますboolcolorUsed[NODE]; //色が使用されているかどうかを確認するために使用されますfor（int i =1; i  
出力
 
ノード：0、色で割り当て：0ノード：1、色で割り当て：0ノード：2、色で割り当て：1ノード：3、色で割り当て：2ノード：4、色で割り当て：1