回答編集履歴
1
修正
answer
CHANGED
|
@@ -63,4 +63,66 @@
|
|
|
63
63
|
color_idx += 1
|
|
64
64
|
|
|
65
65
|
print(graph_color) # {'A': 1, 'B': 0, 'E': 2, 'D': 1, 'C': 2, 'F': 0, 'H': 0, 'G': 1}
|
|
66
|
+
```
|
|
67
|
+
|
|
68
|
+
#### コメントを受けて修正
|
|
69
|
+
`B`の着色時、`F`と`H`は`B`に接続していないので同色で着色していましたが、`F`と`H`がつながっていることが考慮されていませんでした。
|
|
70
|
+
これを考慮し、なおかつコードを全面的に修正しました。
|
|
71
|
+
```Python
|
|
72
|
+
#
|
|
73
|
+
# 隣接ノード'edge'が指定した色'clr'を持っているか
|
|
74
|
+
#
|
|
75
|
+
def has_color(edge,clr,graph_clr):
|
|
76
|
+
for e in edge:
|
|
77
|
+
if e in graph_clr:
|
|
78
|
+
if graph_clr[e] == clr:
|
|
79
|
+
return True
|
|
80
|
+
return False
|
|
81
|
+
|
|
82
|
+
#エッジがある場合はそのノードを記述(例AとBはつながっている,BはA,C,D,E,Gとつながってる)
|
|
83
|
+
A = ['B']
|
|
84
|
+
B = ['A','C','D','E','G']
|
|
85
|
+
C = ['B','D']
|
|
86
|
+
D = ['B','C','E','F','H']
|
|
87
|
+
E = ['B','D','F','G']
|
|
88
|
+
F = ['D','E','G','H']
|
|
89
|
+
G = ['B','E','F','H']
|
|
90
|
+
H = ['D','F','G']
|
|
91
|
+
|
|
92
|
+
# ノード→エッジマップを作成
|
|
93
|
+
edges = [A, B, C, D, E, F, G, H]
|
|
94
|
+
nodes = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']
|
|
95
|
+
graph_map = {k:v for k,v in zip(nodes,edges)}
|
|
96
|
+
#print(graph_map)
|
|
97
|
+
|
|
98
|
+
#次数を求め、降順でソート
|
|
99
|
+
graph_dim = {k:len(v) for k,v in graph_map.items()}
|
|
100
|
+
graph_dim = sorted( graph_dim.items(), key=lambda x: x[1], reverse=True)
|
|
101
|
+
#print(graph_dim)
|
|
102
|
+
|
|
103
|
+
# 3,まだ塗ってない中で次数が一番高いものに色を塗る
|
|
104
|
+
clr = 0 # あらたに塗る色番号
|
|
105
|
+
graph_clr = {}# ノード→色番号マップ
|
|
106
|
+
for i, node_dim in enumerate(graph_dim):
|
|
107
|
+
node = node_dim[0]
|
|
108
|
+
if node in graph_clr: # すでに着色済み
|
|
109
|
+
continue
|
|
110
|
+
graph_clr[node] = clr
|
|
111
|
+
|
|
112
|
+
# 4,次数が一番高いものとつながりがなくまだ色を割り振っていないものを同じ色で塗る
|
|
113
|
+
# ※この条件だけだとFとHが同じ色になる
|
|
114
|
+
for j in range(i+1,len(graph_dim)): # 次の次数の大きいものから順に走査
|
|
115
|
+
sub_node = graph_dim[j][0]
|
|
116
|
+
if sub_node in graph_clr: # すでに着色済み
|
|
117
|
+
continue
|
|
118
|
+
if sub_node in graph_map[node]: # 現在のノードとつながっている
|
|
119
|
+
continue
|
|
120
|
+
# 隣接ノードがすでに同色で着色済み ※この条件が必要
|
|
121
|
+
if has_color(graph_map[sub_node],clr,graph_clr):
|
|
122
|
+
continue
|
|
123
|
+
graph_clr[sub_node] = clr
|
|
124
|
+
|
|
125
|
+
clr += 1
|
|
126
|
+
|
|
127
|
+
print(graph_clr) # {'C': 2, 'D': 0, 'E': 2, 'A': 0, 'G': 0, 'F': 1, 'B': 1, 'H': 2}
|
|
66
128
|
```
|