python3系でグラフ理論のWelsh・. Powellアルゴリズムを用いてそのグラフを彩色する際に何色必要か求めたいのですが、問題となるグラフのソートまでできたのですが
次数の高い順に色を塗っていくところがうまくできません
python3
1#エッジがある場合はそのノードを記述(例AとBはつながっている,BはA,C,D,E,Gとつながってる) 2A = [0, 'B', 0, 0, 0, 0, 0, 0] 3B = ['A', 0, 'C', 'D', 'E', 0, 'G', 0] 4C = [0, 'B', 0, 'D', 0, 0, 0, 0] 5D = [0, 'B', 'C', 0, 'E', 'F', 0, 'H'] 6E = [0, 'B', 0, 'D', 0, 'F', 'G', 0] 7F = [0, 0, 0, 'D', 'E', 0, 'G', 'H'] 8G = [0, 'B', 0, 0, 'E', 'F', 0, 'H'] 9H = [0, 0, 0, 'D', 0, 'F', 'G', 0] 10 11graph = [A, B, C, D, E, F, G, H] 12graph_str = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'] 13copy_graph = copy.copy(graph_str) 14d_graph = list() 15 16print(graph_str) 17 18#次数を求める 19for node in graph: 20 #dgraphに接点数を格納 21 tmp = node.count(0) 22 tmp = len(graph)-tmp 23 d_graph.append(tmp) 24 25 26 27print('接点数',d_graph) 28 29#次数でバブルソート 30for i in range(len(d_graph)): 31 for j in range(len(d_graph)-1, i, -1): 32 if d_graph[j] > d_graph[j-1]: 33 d_graph[j], d_graph[j-1] = d_graph[j-1], d_graph[j] 34 tmp = str(graph_str[j]) 35 graph_str[j] = str(graph_str[j-1]) 36 graph_str[j-1] = str(tmp) 37 38print('接点数順でソート大→小') 39print(graph_str)
とりあえず上記でソートまでです
これ以降をお願い致します。
グラフは上記で、隣り合ったノードは同じ色で塗らないといったものです
何にどんな風に色を塗ればよいか分からないので、イメージ画像またはできているまでのソースコードを提示すると回答得られるかもしれません。
Welsh_Powellのアルゴリズムなんですが隣り合ったノードは違う色で塗ったら合計で何色必要かというものです
1,ノードの次数を求める
2,次数順にソートする
3,まだ塗ってない中で次数が一番高いものに色を塗る
4,次数が一番高いものとつながりがなくまだ色を割り振っていないものを同じ色で塗る
3と4を繰り返す
です
実際に動かしてみたところFとHが隣り合っているのに同じグループになってしまい、
4,次数が一番高いものとつながりがなくまだ色を割り振っていないものを同じ色で塗る
の際にすでに割り振られているノードから再度つながりがあるか確認する必要がありました(Hを割り振る際にHのつながりからFはスルーしたい)
if n in graph_str:
の後に
for subnode_2 in (graph_map[n]):
if subnode_ 2 in graph_map:
スルーする
みたく書けばいいと思うのですがうまくいかなくて詰まっています
何かいい方法がありますか?
回答1件
あなたの回答
tips
プレビュー