深さ優先探索で実装するアルゴリズムまとめ by Python

深さ優先探索は、幅優先探索と並べて紹介されることが多いですが、実際の使用場面でいうと深さ優先探索が圧倒的に多い印象です。

そんな深さ優先探索についてアルゴリズムをまとめます。
①組合せアルゴリズムへの適用
・ナップサック問題への適用
・編集距離への適用
②グラフアルゴリズムへの適用
・グラフ探索
・s-tパス探索
・トポロジカルソート
・ベルマンフォード法
・ワーシャルフロイド法
・フォードファルカーソン法

①組合せアルゴリズムへの適用

ナップサック問題への適用

N個の品物の重さと価値をweight[i], value[i]とし、ナップサックに入れられる重さの総和をWとするときに、ナップサックに入れられる価値の総和の最大値を求める。

Knapsack.py

# ナップサック問題を解く動的計画法
# 計算量　：O(NW)

# アルゴリズム定義
def knapsack():
    dp = [[0 for number in range(0, W+1)] for i in range(0, N+1)]

    for i in range(0, N):
        for w in range(0, W+1):
            if w - weight[i] >= 0:
                dp[i+1][w] = max(dp[i][w], dp[i][w-weight[i]] + value[i])

    print(dp[N][W])

# 入力受取
N, W = map(int, (input().split()))
weight = list(map(int, input().split()))
value = list(map(int, input().split()))

# アルゴリズム実行
knapsack()

# 入力
# 6 10
# 2 1 3 2 1 5
# 3 2 6 1 3 85

# 出力
# 96

編集距離への適用

2つの文字列S, Tがあり、「1文字変更」「1文字削除」「1文字追加」の処理をSがTになるまで繰り返し施すとし、必要な処理回数の最小値を求める。

EditDistance.py

# 編集距離を求める動的計画法
# 計算量　：O(|S||T|)

# アルゴリズム定義
def editDistance(S, T):
    dp = [[10000 for number in range(0, len(T)+1)] for i in range(0, len(S)+1)]
    dp[0][0] = 0

    for i in range(len(S)+1):
        for j in range(len(T)+1):
            if i > 0 and  j > 0:
                if S[i-1] == T[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    dp[i][j] = dp[i-1][j-1]+1

            if i > 0:
                dp[i][j] = min(dp[i][j], dp[i-1][j]+1)

            if j > 0:
                dp[i][j] = min(dp[i][j], dp[i][j-1]+1)

    print(dp[len(S)][len(T)])

# 入力受取
S = input()
T = input()

# アルゴリズム実行
editDistance(S, T)

# 入力
# kintoun
# nyoibou

# 出力
# 6

②グラフアルゴリズムへの適用

グラフ探索

N個の頂点とM個の辺からなる有向グラフGにおいて、始点sから各頂点に接続可能かを判定する。

GraphSearch.py

# グラフ探索：深さ優先探索

# アルゴリズム定義
def DFS(G, v):
    seen[v] = True

    for next_v in range(len(G[v])):
        if seen[G[v][next_v]]:
            continue
        DFS(G, G[v][next_v])

# 入力受取
N, M = map(int, input().split())

# グラフ生成
G = [[] for i in range(N)]
for j in range(M):
    a, b = map(int, input().split())
    G[a].append(b)

# メモ準備    
seen = [False for i in range(N)]

# アルゴリズム実行
s = 0
DFS(G, s)

# 結果出力
print(seen)

# 入力
# 6 8
# 0 1
# 0 4
# 0 5
# 1 2
# 2 4
# 2 5
# 3 4
# 3 5

# 出力
# [True, True, True, False, True, True]

s-tパス探索

N個の頂点とM個の辺からなる有向グラフGにおいて、s-tとなるパスが存在するかを判定する。

stPathSearch.py

# グラフ探索：s-tパスを求める
# 計算量：O(|V|+|E|)

# アルゴリズム定義
def dfs(G, v):
    seen[v] = True

    for next_v in range(len(G[v])):
        if seen[G[v][next_v]]:
            continue
        dfs(G, G[v][next_v])

# 入力受取        
N, M, s, t = map(int, input().split())

# グラフ生成
G = [[] for i in range(N)]
for j in range(M):
    a, b = map(int, input().split())
    G[a].append(b)

# メモ準備
seen = [False for k in range(N)]

# アルゴリズム実行
dfs(G, s)

# 結果出力
if seen[t]:
    print("Yes")
else:
    print("No")

# 入力
# 8 12 2 7
# 0 1
# 0 2
# 0 3
# 1 2
# 1 5
# 2 4
# 3 4
# 3 7
# 4 6
# 5 4
# 5 6
# 6 7

# 出力
# Yes

トポロジカルソート

N個の頂点とM個の辺からなる有向グラフGにおいて、各頂点を辺の向きが一方向になるように順序つけて並び替える。

TopologicalSort.py

# グラフ探索：トポロジカルソート
# 計算量：O(|V|+|E|)

# アルゴリズム定義
def rec(G, v, order):
    seen[v] = True
    for next_v in range(len(G[v])):
        if seen[G[v][next_v]]:
            continue
        rec(G, G[v][next_v], order)

    order.append(v) # 再帰関数を抜ける瞬間(帰りがけ順)のvを順に記憶

# 入力受取    
N, M = map(int, input().split())

# グラフ生成
G = [[] for i in range(N)]
for j in range(M):
    a, b = map(int, input().split())
    G[a].append(b)

# メモ準備    
seen = [False for i in range(N)]

# トポロジカルソート格納リスト生成
order = []

# アルゴリズム実行
for v in range(N):
    if seen[v]:
        continue
    rec(G, v, order)

# 結果出力    
order.reverse() # 再帰関数を抜けた順を逆転することでトポロジカルソートを取り出す
print(order)

# 入力
# 8 12
# 4 2
# 4 6
# 4 1
# 1 6
# 2 7
# 6 7
# 1 3
# 3 7
# 7 0
# 2 5
# 0 5
# 3 0

# 出力
# [4, 2, 1, 3, 6, 7, 0, 5]

ベルマンフォード法

N個の頂点とM個の辺からなる負の閉路を含む有向グラフGにおいて、始点sから各頂点への最短経路を計算する。

BellmanFord.py

# ベルマン・フォード法
# 計算量：O(|V||E|)

# アルゴリズム定義
def BellmanFord(G, s):
    exist_negative_cycle = False
    dist = [10000 for i in range(len(G))]
    dist[s] = 0

    for i in range(len(G)):
        update = False
        for v in range(len(G)):
            if dist[v] == 10000:
                continue
            for e in range(len(G[v])):
                if dist[G[v][e][0]] > dist[v] + G[v][e][1]:
                    dist[G[v][e][0]] = dist[v] + G[v][e][1]
                    update = True

        if update == False:
            break

        if i == len(G)-1 and update == True:
            exist_negative_cycle = True

    if exist_negative_cycle == True:
        print("NEGATIVE CYCLE")
    else:
        for v in range(len(G)):
            if dist[v] < 10000:
                print(dist[v])
            else:
                print("INF")

# 入力受取            
N, M, s = map(int, input().split())

# グラフ生成
G = [[] for i in range(N)]
for i in range(M):
    a, b, w = map(int, input().split())
    G[a].append([b, w])

# アルゴリズム実行    
BellmanFord(G, s)

# 入力
# 6 12 0
# 0 1 3
# 0 3 100
# 1 2 50
# 1 3 57
# 1 4 -4
# 2 3 -10
# 2 5 100
# 3 1 -5
# 4 2 57
# 4 3 25
# 4 5 8
# 2 4 -5

# 出力
# 0
# 3
# 53
# 24
# -1
# 7

ワーシャルフロイド法

N個の頂点とM個の辺からなる有向グラフGにおいて、全頂点間について最短路長を求める。

WarshallFloyd.py

# ワーシャル・フロイド法
# 計算量：O(|V|^3)

# アルゴリズム定義
def WarshallFloyd(dp):
    for i in range(len(dp[1])):
        for j in range(len(dp[0])):
            for k in range(len(dp[0])):
                dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j])

    exist_negative_cycle = False
    for v in range(len(dp[0])):
        if dp[v][v] < 0:
            exist_negative_cycle = True

    if exist_negative_cycle:
        print("NEGATIVE CYCLE")
    else:
        for i in range(len(dp[0])):
            for j in range(len(dp[0])):
                if j:
                    print(" ", end='')
                if dp[i][j] < 5000:
                    print(dp[i][j], end='')
                else:
                    print(10000, end='')
            print("")

# 入力受取
N, M = map(int, input().split())

# dp生成
dp = [[100000 for i in range(N)] for j in range(N)]
for e in range(M):
    a, b, w = map(int, input().split())
    dp[a][b] = w
for v in range(N):
    dp[v][v] = 0

#アルゴリズム実行
WarshallFloyd(dp)

# 入力
# 6 9
# 0 1 3
# 0 2 5
# 1 2 4
# 1 3 12
# 2 3 9
# 2 4 4
# 3 4 7
# 3 5 2
# 4 5 8

# 出力
# 0     3     5     14    9     16
# 10000 0     4     12    8     14
# 10000 10000 0     9     4     11
# 10000 10000 10000 0     7     2
# 10000 10000 10000 10000 0     8
# 10000 10000 10000 10000 10000 0

フォードファルカーソン法

N個の頂点とM個の辺からなる有向グラフGにおいて、各辺eが容量c(e)を持つ場合に、始点sから終点tへの最大流問題を計算する。

FordFulkerson.py

# フォード・ファルカーソン法

# クラス定義（アルゴリズム定義）
class FordFulkerson():

    def __init__(self):
        self.INF = 10000
        self.seen = [False for i in range(N)]

    def rev(self, G, g, v):
        for i in range(len(G[g])):
            if G[g][i][0] == v:
                return i   

    def fodfs(self, G, v, t, f):
        if  v == t:
            return f

        self.seen[v] = True
        for i in range(len(G[v])):
            if self.seen[G[v][i][0]]:
                continue

            if G[v][i][1] == 0:
                continue

            flow = self.fodfs(G, G[v][i][0], t, min(f, G[v][i][1]))

            if flow == 0:
                continue

            G[v][i][1] -= flow
            k = self.rev(G, G[v][i][0], v)
            G[G[v][i][0]][k][1] += flow

            return flow

        return 0

    def solve(self, G, s, t):

        res = 0

        while True:
            for i in range(len(G)):
                self.seen[i] = 0

            flow = self.fodfs(G, s, t, 10000)

            if flow == 0:
                return res

            res += flow

        return 0 

# 入力受取
N, M = map(int, input().split())

# グラフ生成
G = [[] for i in range(N)]
for i in range(M):
    u, v, c = map(int, input().split())
    G[u].append([v, c])
    for j in range(len(G[u])):
        if len(G[v]) > j:
            if G[v][j][0] == u:
                break
    G[v].append([u, 0])

# 初期条件
s, t = 0, N-1

# オブジェクト作成
ff = FordFulkerson()

# アルゴリズム実行
ff.solve(G, s, t)

# 入力
# 6 9
# 0 1 5
# 0 3 5
# 1 2 4
# 1 3 37
# 2 4 56
# 2 5 9
# 3 2 3
# 3 4 9
# 4 5 2

# 出力
# 9