## 2019年1月16日水曜日

### Algorithm - Python - 忘れられない週末(グラフ彩色(2彩色)、2部グラフ、非連結、辞書を使ったグラフの表現、例外、深さ優先のグラフの再帰横断)

コード

Python 3

```#!/usr/bin/env python3

def bipartite_graph_color(
graph: dict, start: str, coloring: dict, color: str) -> (bool, dict):
if not start in graph:
return False, {}
if not start in coloring:
coloring[start] = color
elif coloring[start] != color:
return False, {}
else:
return True, coloring
if color == '赤':
color = '青'
else:
color = '赤'
for vertex in graph[start]:
bln, coloring = bipartite_graph_color(graph, vertex, coloring, color)
if not bln:
return False, {}
return True, coloring

def bipartite_graph_color_not_connected(
graph: dict, start: str, coloring: dict, color: str) -> (bool, dict):
bln, coloring = bipartite_graph_color(graph, start, coloring, color)
graph_keys = set(graph)
coloring_keys = set(coloring)
if bln and graph_keys == coloring_keys:
return True, coloring
return bipartite_graph_color(
graph, (graph_keys - coloring_keys).pop(), coloring, color)

if __name__ == '__main__':
graph1 = {'a': ['b'],
'b': ['a'],
'c': ['d'],
'd': ['c', 'e', 'f'],
'e': ['d'],
'f': ['d', 'g', 'h', 'i'],
'g': ['f'],
'h': ['f'],
'i': ['f']}
graph2 = {k: list(reversed(v)) for k, v in graph1.items()}
for graph in [graph1, graph2]:
print(graph)
print(bipartite_graph_color_not_connected(graph, 'a', {}, '赤'))
```

```\$ python3 sample1.py
{'a': ['b'], 'b': ['a'], 'c': ['d'], 'd': ['c', 'e', 'f'], 'e': ['d'], 'f': ['d', 'g', 'h', 'i'], 'g': ['f'], 'h': ['f'], 'i': ['f']}
(True, {'a': '赤', 'b': '青', 'c': '赤', 'd': '青', 'e': '赤', 'f': '赤', 'g': '青', 'h': '青', 'i': '青'})
{'a': ['b'], 'b': ['a'], 'c': ['d'], 'd': ['f', 'e', 'c'], 'e': ['d'], 'f': ['i', 'h', 'g', 'd'], 'g': ['f'], 'h': ['f'], 'i': ['f']}
(True, {'a': '赤', 'b': '青', 'c': '赤', 'd': '青', 'f': '赤', 'i': '青', 'h': '青', 'g': '青', 'e': '赤'})
\$
```