深さ優先探索（Depth First Search）

問題

頂点数 $N$、辺数 $M$ のグラフが与えられます。

頂点には $1$ から $N$ までの番号が付けられており、$i$ 番目の辺は頂点 $A_i$ と $B_i$ を双方向につないでいます。

グラフ全体が連結であるかどうかを判定して下さい。

連結とは、グラフがどの頂点間も行き来可能であることを意味します。

[制約]
🔹$ 1 \leqq N \leqq 100000 $
🔹$ 0 \leqq M \leqq min(100000, N(N-1)/2 $
🔹$ 1 \leqq A_i < B_i \leqq N $

解き方・ソースコード

深さ優先探索とは、『進めるだけ進み、行き詰ったら一歩戻る』という考えに基づいてグラフを探索していくアルゴリズムです。

深さ優先探索を使うと、次のようにしてグラフの連結判定を行うことができます。

訪問した頂点には青色の印をつけていくことにします。

🔹【手順１】最初に、全ての頂点の色を白色に塗っておく。
🔹【手順２】頂点１を訪問して青色で塗る。その後、以下の行動を繰り返す。
　・隣接する白色頂点がある場合⇒現在位置に隣接する白色の頂点を１つ選び、その頂点に移動し青色で塗る。
　・隣接する白色頂点がない場合⇒一歩戻る。ただし頂点１にいる場合は戻れないので行動終了。
🔹【手順３】行動が終わった時点で全頂点が青色で塗られていたら、グラフは連結となる。

深さ優先探索は、再帰関数を使って次のように実装します。

🔹ある頂点に移動するときはdfs関数を再帰呼び出しする。
🔹一歩戻るときはreturnする。

プロブラムの計算量は $ O(N+M) $ となります。

[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
39
40
41
42
43
44
#-------- 入力例１ ---------
N = 6       # 頂点の数
M = 6       # 辺の数
# 各辺が結ぶ頂点の情報
edges = [
    (1, 2),
    (1, 3),
    (2, 4),
    (3, 4),
    (4, 5),
    (4, 6)
]
#-------- 入力例２ ---------
# N = 6       # 頂点の数
# M = 6       # 辺の数
# # 各辺が結ぶ頂点の情報
# edges = [
#     (1, 2),
#     (1, 3),
#     (2, 4),
#     (3, 4),
#     (4, 5)
# ]
#---------------------------
# 深さ優先探索を行う関数（pos は現在位置、visited[x] は頂点 x が青色かどうかを表す真偽値）
def dfs(pos, G, visited):
    visited[pos] = True
    for i in G[pos]:
        if visited[i] == False:
            dfs(i, G, visited)

# 隣接リストの作成
G = [list() for i in range(N + 1)] # G[i] は頂点 i に隣接する頂点のリスト
for a, b in edges:
    G[a].append(b) # 頂点 a に隣接する頂点として b を追加
    G[b].append(a) # 頂点 b に隣接する頂点として a を追加

# 深さ優先探索
visited = [ False ] * (N + 1)
dfs(1, G, visited)
print('各頂点の判定結果', visited[1:], '=> 全ての結果をまとめた判定', all(visited[1:]))

# 答えの出力
print("このグラフは連結です。" if all(visited[1:]) else "このグラフは連結ではありません。")

[実行結果（入力例１）]

各頂点の判定結果 [True, True, True, True, True, True] => 全ての結果をまとめた判定 True

このグラフは連結です。

[実行結果（入力例２）]

各頂点の判定結果 [True, True, True, True, True, False] => 全ての結果をまとめた判定 False

このグラフは連結ではありません。

グラフが連結となっているかどうかを判定することができました。