Find if Path Exists in Graph
無向グラフには n 個のノードがあり、番号は 0 から n-1 までです。edges の各要素 [u, v] はノード u と v をつなぎ、辺はどちらの方向にもたどることができます。辺に沿って source から destination まで移動できる場合は true を、そうでない場合は false を返してください。ノードは常に自分自身に到達できます。
関数
- ninteger
- ノードの数
- edgesinteger-2d-array
- 各辺は、接続されたノードのペア [u, v] です
- sourceinteger
- 開始地点となるノード
- destinationinteger
- 到達したいノード
- 戻り値boolean
- あるパスがソースと宛先を結合するかどうか
制約
2 ≤ n ≤ 1041 ≤ edges.length ≤ 5000edges[i] = [u, v]（0 ≤ u, v ≤ n-1かつu ≠ v）- どの辺も、どちらの向きでも2回現れることはありません。
0 ≤ source, destination ≤ n-1
例
- 入力
- n = 6edges = [[0, 1], [1, 2], [2, 3], [4, 5]]source = 0destination = 3
- 出力
- true
- 説明
- 経路
0 → 1 → 2 → 3は3本の辺を使うため、ノード3に到達できます。ノード4と5は独立した部分を形成しており、この経路で通る必要はありません。
- 入力
- n = 5edges = [[0, 1], [0, 2], [3, 4]]source = 2destination = 4
- 出力
- false
- 説明
- ノード 2 からは 0、そして 1 に到達でき、それ以外には到達できません。ノード 4 はノード 3 にしか接続しておらず、
{0, 1, 2}と{3, 4}を結ぶ辺はないため、答えはfalseです。
提出時に隠しテスト+16件
発展問題
辺が一方向だとします。[u, v]では、uからvへの移動のみが可能です。3つのアプローチのうち、引き続き使えるのはどれですか。また、それぞれどのように変更しますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
ひとまず目的地のことは忘れましょう。
sourceから到達できるノードはどれですか？sourceから到達済みノードの集合を、1つずつ辺をたどって広げ、拡大しなくなったら停止します。隣接ノードのリストを調べれば、ノードを二度訪問しない限り、1回の走査でこれを行えます。seen配列を使ってsourceから BFS を実行するか、union-find を使って各辺の両端を 1 つのグループに統合し、sourceとdestinationが最終的に同じ根になるかを確認します。
解説
問題は、source と destination がグラフの同じ連結成分に属しているかどうかです。遅い方法では、新たに到達できる頂点がなくなるまで辺のリストを再走査します。隣接リストを使った幅優先探索では、各頂点と各辺を一度ずつ調べます。また、Union-Find では、辺を読み込みながらグループを統合することで同じ答えを得られ、隣接リストは必要ありません。
何も変化しなくなるまで、端をスイープします
正しいが、最大のテストでは終わらない
考え方
sourceから始めて、到達できると分かっているすべてのノードに印を付けます。次に、辺のリストを読みます。印の付いた端点と印の付いていない端点を1つずつ持つ辺があれば、印の付いていない端点にも到達できるので、そこに印を付けます。新たに印が付くノードがなくなるか、destinationに印が付くまで、この一巡を繰り返します。
これは正しい方法です。sourceから長さkの経路上にあるノードは、遅くともk回目の一巡までに印が付きます。また、ノードに印が付くのは、印の付いたノードからそのノードへ辺がつながっている場合に限られます。最初の例では、リストの順に1回一巡すると、1、2、3に順番に印が付き、完了です。
計算量は辺の順序によって変わります。経路が遠い端から逆向きに並んでいる場合、一巡ごとに新たに印が付くノードは1つだけです。その場合、5001個のノードを通る経路では、5000本の辺に対して5000回の一巡が必要になり、辺の確認回数は2.5 × 10^7回になります。隣接リストを使えば一巡で済むところです。
アルゴリズム
sourceだけに印を付けて、reachedを作成します。- すべての辺
[u, v]を調べます。端点のちょうど一方に印が付いている場合は、もう一方にも印を付け、何か変化があったことを記録します。 - 何か変化があり、かつ
destinationにまだ印が付いていない間、この処理を繰り返します。 destinationに印が付いているかどうかを返します。
def validPath(n, edges, source, destination):
reached = [False] * n
reached[source] = True
changed = True
while changed and not reached[destination]:
changed = False
for u, v in edges:
# An edge with exactly one reached end pulls the other end in.
if reached[u] != reached[v]:
reached[u] = reached[v] = True
changed = True
return reached[destination]幅優先探索
考え方
この走査では、両端がずっと前に確定した辺を何度も読み直すため、時間を無駄にしています。代わりに、各ノードについて、隣接するノードをすべてリストにします。各辺 [u, v] は両方のリストに追加します。どちらの方向にもたどれるからです。次に、source から外側へ探索します。キューからノードを取り出し、まだ訪れていない隣接ノードをそれぞれキューに追加します。
ノードは、キューから取り出すときではなく、キューに追加するときに訪問済みとして印を付けます。そうすれば、どのノードもキューに二度入ることはなく、0 → 1 → 2 → 0 のようなサイクルがグラフにあっても探索は終了します。destination がキューから取り出されたら、経路が存在します。先にキューが空になった場合は、source から到達できるすべてのノードを訪問済みであり、その中に destination はありません。
各ノードは最大1回キューに追加され、各辺は両端から1回ずつ、合計2回調べられるため、辺の数を m とすると、時間計算量は O(n + m) です。隣接リストに必要な空間は O(n + m) です。再帰の代わりにキューを使えば、5000個のノードからなる経路でもコールスタックがあふれません。
アルゴリズム
- 隣接リストを作成します。各辺
[u, v]について、vをuのリストに追加し、uをvのリストに追加します。 sourceを訪問済みとしてマークし、キューに入れます。- 先頭からノードを取り出します。それが
destinationなら、trueを返します。 - まだ訪問していない各隣接ノードを訪問済みとしてマークし、キューに入れます。
- キューが空になったら、
falseを返します。
from collections import deque
def validPath(n, edges, source, destination):
# Each edge goes both ways, so list it under both of its ends.
graph = [[] for _ in range(n)]
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
seen = [False] * n
seen[source] = True
queue = deque([source])
while queue:
node = queue.popleft()
if node == destination:
return True
for nxt in graph[node]:
if not seen[nxt]:
# Mark on push, so no node enters the queue twice.
seen[nxt] = True
queue.append(nxt)
return FalseUnion-find
考え方
経路そのものは必要なく、経路が存在するかどうかだけが必要です。そこで、グラフを連結したノードのグループとして扱います。最初は、すべてのノードがそれぞれ独立したグループです。辺 [u, v] は、u と v が同じグループに属することを示すので、それらのグループを統合します。すべての辺を処理した後、source と destination が連結しているのは、同じグループに属している場合に限ります。
各グループを parent リンクを持つ木として保存し、根がグループを表します。find(x) は根までたどります。統合するには、一方の根をもう一方の根の下につなげます。2つ目の例では、[0, 1] と [0, 2] によってグループ {0, 1, 2} ができ、[3, 4] によって {3, 4} ができます。find(2) と find(4) は異なる根を返すため、答えは false です。
2つの工夫で木を平坦に保てます。小さいグループを大きいグループの下につなげ、find の途中で各ノードを祖父母に向けて、経路の長さを半分にします。これらを組み合わせると、各操作の計算量は α(n)（逆アッカーマン関数）となり、どのような入力でも 5 未満にとどまります。辺は一度だけ読み込み、保存するのは parent と size だけです。空間計算量は O(n) で、隣接リストを作る必要もありません。
アルゴリズム
- すべてのノードについて、
parent[x] = xとsize[x] = 1を設定します。 - 各辺
[u, v]について、両端のルートaとbを見つけます。 - それらが異なる場合、小さいグループのルートをもう一方の下に置き、サイズを加算します。
find(source)がfind(destination)と等しいかどうかを返します。
def validPath(n, edges, source, destination):
parent = list(range(n)) # every node starts as its own group
size = [1] * n
def find(x):
# Walk up to the group's root, halving the path on the way.
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
for u, v in edges:
a, b = find(u), find(v)
if a != b:
# Hang the smaller group under the larger one.
if size[a] < size[b]:
a, b = b, a
parent[b] = a
size[a] += size[b]
return find(source) == find(destination)
落とし穴と境界ケース
グラフは小さいですが、探索が完了し、正しい答えが返るかどうかを左右する細かな点がいくつかあります。
- 各辺を一方向にだけ追加する。グラフは無向なので、
[1, 0]があれば、0から1へも移動できなければなりません。一方向のみの隣接リストでは、辺を逆向きに使う経路を見落とします。 - ノードをキューに入れるときではなく、キューから取り出すときに訪問済みとして記録する。すると、そのノードより前に処理された隣接ノードごとにキューへ追加されるため、キューには最大で
n件ではなく、最大2m件の要素が入ることがあります。 sourceとdestinationが同じ場合があることを忘れる。そのノードに辺がまったくなくても、答えはtrueです。- 長い経路で再帰的なDFSを使う。5000個のノードを通る経路では、呼び出しが5000段ネストし、Pythonのデフォルト上限である1000を超えます。キューまたは明示的なスタックを使いましょう。
- union-findで
parent[source]とparent[destination]を比較する。グループを表すのはルートだけです。必ずfind(source)とfind(destination)を比較しましょう。 - 配列のインデックスが1から始まるLuaとRで、ずれを考慮し忘れる。ノード
xはインデックスx+1にあります。
よくある質問4
パスが存在するかどうかを確認するには、BFS、DFS、union-find のどれを使えばよいですか？
3つとも線形、またはそれに近い計算量です。BFSとDFSは目的地に到達した時点ですぐに停止でき、経路そのものを返すこともできます。Union-findは隣接リストを必要とせず、各辺を1回ずつ読み取ります。また、同じグラフについて連結性に関する質問が多数ある場合に力を発揮します。併合後は、各質問に必要なのが2回のfind呼び出しだけだからです。
グラフ内に経路が存在するかどうかを調べる時間計算量は何ですか？
BFS または DFS では、ノード数が n、辺数が m の場合、時間計算量と空間計算量は O(n + m) です。各ノードは 1 回訪問され、各辺は両端から確認されます。サイズによる併合と経路の短縮を用いる union-find の場合、時間計算量は O(n + m·α(n))、空間計算量は O(n) です。ここで α の増加は非常に遅いため、実際には小さな定数として扱えます。
BFS に visited 配列が必要なのはなぜですか？
これがないと、0 → 1 → 2 → 0のような循環によって探索がいつまでも続き、循環がなくても、複数の隣接ノードを持つノードは隣接ノードごとに一度ずつキューに追加されます。各ノードをキューに追加した時点でマークすれば、そのノードは一度だけ処理されることが保証され、処理量をO(n + m)に抑えられます。
union-findにおける経路圧縮とサイズによる併合は、何をするものですか？
findが高速なままでいられるよう、木の深さを浅く保ちます。サイズによる併合では、小さい木を大きい木の下につなぐため、ノードの深さが増えるのは、そのノードが属するグループのサイズが少なくとも2倍になったときだけです。これにより、深さはlog n以下に抑えられます。経路圧縮、またはここで使われている経路半分化は、根までたどるたびに経路を短くします。この2つを組み合わせることで、各操作の計算量はα(n)になります。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def validPath(n, edges, source, destination):
# ここにコードを書いてくださいケース1
ケース2
入力
n = 6 edges = [[0, 1], [1, 2], [2, 3], [4, 5]] source = 0 destination = 3
期待値
true