🦔

【Python3】1次元深さ優先探索(DFS)

2022/11/14に公開約900字

以下の内容はアルゴ式(https://algo-method.com/)を参考にしています。
DFS問題集(https://zenn.dev/pienthon/articles/1452aaefe02390)を解くと実践に繋げられます。

DFSの手順

  1. 木を作成する
  2. 関数dfsを作成する

木の作成手順

G = [[頂点0から向かっている頂点], [頂点1から向かっている頂点], ...]
というリストを作成します。
これが木です。

単純有向グラフの場合、以下のように作成します。

from collections import defaultdict
N, M = map(int, input().split())
G = defaultdict(lambda: [])
for i in range(M):
    A, B = map(int, input().split())
    G[A].append(B)
for v in range(N):
   G[v].sort()


関数dfsの作成手順

以下のように、頂点を辿りながら、すでに到達した頂点を黒く塗っていきます。
また、到達順に頂点を表示していきます。

dfs(頂点 v):
    頂点 v を黒く塗る
    頂点 v の頂点番号を出力する
    for v2 in G[v]:
        if 頂点 v2 がすでに黒く塗られている:
            continue
        rec(頂点 v2)



これをPythonで表現したものは以下のようになります。

def dfs(v, G, seen):
    seen[v] = True
    print(v, end = " ")
    for v2 in G[v]:
        if seen[v2]: continue
        dfs(v2, G, seen)
    return
seen = [False for _ in range(N)]

Discussion

ログインするとコメントできます