More than 3 years have passed since last update.

Pythonでアルゴリズム（深さ優先探索、dfs）

Last updated at 2020-01-08Posted at 2020-01-07

#はじめに
　pythonで深さ優先探索をする場合、再帰ではパフォーマンスに不安があると聞いたので、stackで実装をしようと思いその備忘録として記事に残そうと思いました。
　学習の手助けになれば幸いですし、何かアドバイスなどありましたら是非コメントを頂きたいです!

#テーマ
　今回は、深さ優先探索の中でも代表的なテーマである、ある頂点をスタートして、各頂点まで到達するのにかかる時間について考えます。（時間というよりは順番？）その際、到達した時刻を調べる行きがけ順、最後に通過する時刻を調べる帰りがけ順、両方をタイムスタンプでまとめて記録するという3つの場合を扱います。最後に通過するというのは、その頂点より下の頂点すべての探索が終わった直後のことを指します。
　dfsの詳しい解説は省きますが、スタート地点から行けるところまで深く行き、それ以上進めなくなったら前の分岐点まで戻り同じことを繰り返していきます。ここで、頂点番号が若い方を優先的に探索するとします。

#入出力
###入力
　1行目に頂点の個数を整数で、その後N行に頂点番号、隣接する頂点の個数、隣接する頂点を空白区切りで入力します。

###出力
　N行に、頂点番号、到達時刻、探索終了時刻が空白区切りで出力されます。（行きがけ順では前者のみ、帰りがけ順では後者のみです。）

#実装
##行きがけ順

dfs_1.py

# 深さ優先探索（行きがけ）
import sys
input = sys.stdin.readline
from collections import deque

# グラフの作成(無向グラフでは#を消す)
N = int(input())
graph = [deque([]) for _ in range(N + 1)]
for _ in range(N):
    u, k, * v = [int(x) for x in input().split()] # uは頂点番号、kは隣接頂点の個数
    v.sort()
    for i in v:
        graph[u].append(i)
        # graph[i].append(u) # 無向グラフ

time = 0
arrive_time = [-1] * (N + 1) # 到着時刻

# 深さ優先探索
def dfs(v):
    global time
    time += 1
    stack = [v]
    arrive_time[v] = time
    while stack:
        v = stack[-1]
        if graph[v]:
            w = graph[v].popleft()
            if arrive_time[w] < 0:
                time += 1
                arrive_time[w] = time
                stack.append(w) 
        else:
            stack.pop()          
    return arrive_time

# 孤立している頂点対策
for i in range(N):
    if arrive_time[i + 1] < 0:
        ans = dfs(i + 1)

# 頂点番号、到着時刻
for j in range(N):
    temp = [j + 1, ans[j + 1]]
    print(* temp)

　まず、グラフは隣接リストで表現しています。ここでは、有向グラフとして考えていますが、コード中の#を一か所外せば無向グラフとしても扱えます。時刻はグローバル変数としてどの頂点から呼び出されても共通の時間軸で扱うことができ、新しい頂点に到達したときに+1され、到達時刻arrive_timeのリストに記録されます。
　有向グラフでは、スタートの頂点からたどり着けないものもあるので、しっかりすべての頂点に関して、未到達であれば深さ優先探索を実行していきます。
　stackでは後入れ先出しなので、後ろの要素を取り出し、隣接する頂点を調べます。それらの頂点は、調べたことが分かるように隣接リストから削除します。もしも中身が空ならその頂点の探索は終了したのでstackから削除します。

##帰りがけ順

dfs_2.py

# 深さ優先探索（帰りがけ）
import sys
input = sys.stdin.readline
from collections import deque

# グラフの作成(無向グラフでは#を消す)
N = int(input())
graph = [deque([]) for _ in range(N + 1)]
for _ in range(N):
    u, k, * v = [int(x) for x in input().split()] # uは頂点番号、kは隣接頂点の個数
    v.sort()
    for i in v:
        graph[u].append(i)
        # graph[i].append(u) # 無向グラフ

time = 0
arrive = [-1] * (N + 1) # 到着したか
finish_time = [-1] * (N + 1) # 探索終了時刻

# 深さ優先探索
def dfs(v):
    global time
    stack = [v]
    arrive[v] = 1
    while stack:
        v = stack[-1]
        if graph[v]:
            w = graph[v].popleft()
            if arrive[w] < 0:
                arrive[w] = 1
                stack.append(w) 
        else:
            time += 1
            finish_time[v] = time
            stack.pop()          
    return finish_time

# 孤立している頂点対策
for i in range(N):
    if arrive[i + 1] < 0:
        ans = dfs(i + 1)

# 頂点番号、終了時刻
for j in range(N):
    temp = [j + 1, ans[j + 1]]
    print(* temp)

　使っている変数や考え方はほぼ同じですが、今回は到達した時刻ではなく、探索が終了した時刻をfinish_timeに記録していきます。つまり、ある頂点の隣接する頂点を隣接リストから削除していく際、空になったら時間が進み、その時刻を記録します。

##行きがけ時間+帰りがけ時間

dfs_3.py

# 深さ優先探索（行きがけ、帰りがけ）
import sys
input = sys.stdin.readline
from collections import deque

# グラフの作成(無向グラフでは#を消す)
N = int(input())
graph = [deque([]) for _ in range(N + 1)]
for _ in range(N):
    u, k, * v = [int(x) for x in input().split()] # uは頂点番号、kは隣接頂点の個数
    v.sort()
    for i in v:
        graph[u].append(i)
        # graph[i].append(u) # 無向グラフ

time = 0
arrive_time = [-1] * (N + 1) # 到着時刻
finish_time = [-1] * (N + 1) # 探索終了時刻

# 深さ優先探索
def dfs(v):
    global time
    time += 1
    stack = [v]
    arrive_time[v] = time
    while stack:
        v = stack[-1]
        if graph[v]:
            w = graph[v].popleft()
            if arrive_time[w] < 0:
                time += 1
                arrive_time[w] = time
                stack.append(w) 
        else:
            time += 1
            finish_time[v] = time
            stack.pop()          
    return [arrive_time, finish_time]

# 孤立している頂点対策
for i in range(N):
    if arrive_time[i + 1] < 0:
        ans = dfs(i + 1)

# 頂点番号、到着時刻、終了時刻
for j in range(N):
    temp = [j + 1, ans[0][j + 1], ans[1][j + 1]]
    print(* temp)

　上の二つを組み合わせるだけです。つまり、ある頂点に到達、もしくはそれ以下の探索が終了すると時間が進み、それらをarrive_time、finish_timeに記録します。

#最後に
　自分は情報系の学科ではないので、ネットの記事や本を参考に勉強しています。特にこの深さ優先探索については考え方は簡単なのに初心者の自分には実装がとても難しかったです。（この記事のコードも誤りがあるかもしれません）なので、是非コメント欄やTwitterなどでアドバイスしてください!高速化などのアドバイスもあれば是非いただきたいです。

#参考文献
-DFS (深さ優先探索) 超入門！〜グラフ・アルゴリズムの世界への入口〜【前編】
　けんちょんさんの記事です。どれも分かりやすくていつもお世話になっています。
-[プログラミングコンテスト攻略のためのアルゴリズムとデータ構造]
(https://www.amazon.co.jp/%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0%E3%82%B3%E3%83%B3%E3%83%86%E3%82%B9%E3%83%88%E6%94%BB%E7%95%A5%E3%81%AE%E3%81%9F%E3%82%81%E3%81%AE%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%81%A8%E3%83%87%E3%83%BC%E3%82%BF%E6%A7%8B%E9%80%A0-%E6%B8%A1%E9%83%A8-%E6%9C%89%E9%9A%86/dp/4839952957)
　問題や考え方などを参考にさせていただきました。

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up