グラフ（辞書型編）

グラフ（辞書型編）

グラフ は、対象物の関係性 を表します。

グラフ を使うと、友人関係・鉄道路線・タスクの依存関係など、さまざまな関係性を表現できます。

関係性を グラフ で表すと、問題を抽象的に考えることができるというメリットがあります。

問題

次のような問題があります。

[問題]

頂点数がＮ個、辺数がＭ本であるような無向グラフ（辺の向きがないグラフ）があります。

頂点は隣接する頂点の情報（複数）を持っています。

それぞれの頂点は色の情報をもっており、色の情報は塗り替えることができます。

クエリ―は２種類あり下記のような操作を行います。

　クエリ―１：1 aという形式で情報が与えられ、頂点aに隣接する頂点 の色が 頂点aの色 に塗り変えられます。
　
　クエリ―２：2 a bという形式で情報が与えられ、頂点a の色が 色b に塗り替えられます。

[条件]

・頂点数Ｎは1以上200以下の整数

・変数ＭはＮ（Ｎ－１）／２以下の整数

・クエリ―数Ｑは1以上200以下の整数

解法・ソースコード

頂点と辺、色の情報を辞書型の変数で管理します。

辞書型のキーには 頂点のID を設定し、辞書型の値として 色情報と隣接する頂点 の情報を辞書型データとして設定します。

クエリ―ごとに各頂点の色情報を更新し、最後に各頂点の色情報を表示しています。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#---------- 入力例 ----------
# ノード情報
nodes = {
    1:{'color':5,       # 色情報（初期）
       'edge':[2]},     # 隣接ノード（１→２）
    2:{'color':10,      # 色情報（初期）
       'edge':[1,3]},   # 隣接ノード（２→１、２→３）
    3:{'color':15,      # 色情報（初期）
       'edge':[2]},     # 隣接ノード（３→２）
}
# クエリ―情報
querys = [(1, 2),
          (2, 1, 20),
          (1, 1)]
#----------------------------
# 各ノードの色情報を表示する
def show_color():
    for k,v in nodes.items():
        print('  node[{}]: color[{}]'.format(k, v['color']))

print('【初期のカラー情報】')
show_color()
print(' -------')

for query in querys:
    print('クエリ―', query)
    node = nodes[query[1]]          # ノードを選択
    if query[0] == 1:               # クエリ―がタイプ１の場合
        for e in node['edge']:      # 選択ノードに隣接する各ノードの色を更新
            nodes[e]['color'] = node['color']
    else:                           # クエリ―がタイプ２の場合
        node['color'] = query[2]    # 選択ノードの色を更新
    print(' (カラー情報)')
    show_color()
    print(' -------')

print('【解：カラー情報】')
show_color()

[実行結果]

【初期のカラー情報】
  node[1]: color[5]
  node[2]: color[10]
  node[3]: color[15]
 -------
クエリ― (1, 2)
 (カラー情報)
  node[1]: color[10]
  node[2]: color[10]
  node[3]: color[10]
 -------
クエリ― (2, 1, 20)
 (カラー情報)
  node[1]: color[20]
  node[2]: color[10]
  node[3]: color[10]
 -------
クエリ― (1, 1)
 (カラー情報)
  node[1]: color[20]
  node[2]: color[20]
  node[3]: color[10]
 -------
【解：カラー情報】
  node[1]: color[20]
  node[2]: color[20]
  node[3]: color[10]

１番目のクエリ―により、頂点２に隣接する全ての頂点の色が10に塗り替えられます。

２番目のクエリ―により、頂点１の色が色20に塗り替えられます。

３番目のクエリ―により、頂点１に隣接する全ての色が20に塗り替えられます。

最終的には、頂点１の色が20、頂点２の色が20、頂点３の色が10になっていることが確認できます。