Go to Qiita Advent Calendar 2024 Top
LoginSignup
9
7

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

@zuid

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

Last updated at Posted at 2021-08-04

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

そんな深さ優先探索についてアルゴリズムをまとめます。
①組合せアルゴリズムへの適用
・ナップサック問題への適用
・編集距離への適用
②グラフアルゴリズムへの適用
・グラフ探索
・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
9
7
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
9
7

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?