DFS（深さ優先探索）

DFSについて学びました。
参考にしたのはこの記事です。

基本編

以下が、DFSを実現する基本的なソースコードです。

#頂点数
#競プロでは入力を受け付けるが、ここでは気にしない
v = 5
#グラフは2次元配列であらわす（無向グラフ）
graph = [[] for i in range(v)]
#頂点0は頂点1,2と辺で連結している
#頂点1は頂点0,2,3と辺で連結している
#・・・以下同様
graph[0] = [1, 2]
graph[1] = [0, 2, 3]
graph[2] = [0, 1, 3]
graph[3] = [1, 2, 4]
graph[4] = [3]

#訪問済みかを表す配列（各頂点に対して訪問したかを表すため、サイズは頂点数v）
seen = [False] * v

#深さ優先探索（探索対象のグラフと、探索開始頂点vを引数とする）
def dfs(graph, v):
  #vを訪問済みとする
  seen[v] = True
  print(str(v) + 'に訪問しました！') #優先順がわかりやすくするため出力
  #頂点vから行ける（連結している）各頂点に対して
  for next_v in graph[v]:
    if seen[next_v]:
      #すでに訪問済みであれば処理しない
      continue
    #再帰的に探索
    dfs(graph, next_v)

#0から順に深さ優先探索を実行
dfs(graph, 0)

ここからは深さ優先探索を用いた実際の例題をやってみます。 参考はこの記事です。

sからtへたどり着けるか

上記の基本コードから少し変更して、頂点sから頂点vへたどり着けるかを判定するプログラムです。
やっていることは基本編とほぼ変わりません。
最終的に、seen[v]がtrueとなっているか（訪問済になっているか）を確かめます。

#sからtへたどり着けるか
#頂点数vと辺の数e
v, e = map(int, input().split())
s, t = map(int, input().split())
graph = [[] for i in range(v)]
#辺の数だけ入力があり、e1とe2は連結していることを表す
for i in range(e):
  e1, e2 = map(int, input().split())
  #無向グラフのため、両方から行けること
  graph[e1].append(e2)
  graph[e2].append(e1)

print(graph)

seen = [False] * v

def dfs(g, v):
  seen[v] = True
  for next_v in g[v]:
    if seen[next_v]:
      continue
    dfs(g, next_v)
  
dfs(graph, s)

if seen[t]:
  print('Yes')
else:
  print('No')