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

幅優先探索は、深さ優先探索と並べて紹介されることが多いですが、アルゴリズムの中で出会う場面は深さ優先探索と比べると少ない印象です。

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

GraphSearch.py

# グラフ探索：幅優先探索

# アルゴリズム定義
def BFS(G, s):
    N = len(G)
    
    seen = [False for i in range(N)]
    todo = []
    
    seen[s] = True
    todo.append(s)
    
    while todo:
        v = todo[0]
        del todo[0]
        
        for x in range(len(G[v])):
            if seen[G[v][x]]:
                continue
            seen[G[v][x]] = True
            todo.append(G[v][x])
    
    return seen

# 入力受取            
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)

# アルゴリズム実行
BFS(G, 0)

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

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

###最短路
N個の頂点とM個の辺からなるグラフGにおいて、始点sから各頂点への最短路を求める。

ShortestPath.py

# 最短経路アルゴリズム
# 計算量：O(|V|+|E|)

# アルゴリズム定義
def BFS(G, s):
    N = len(G)
    dist = [-1 for i in range(N)]
    que = []
    
    dist[0] = 0
    que.append(0)
    
    while len(que) != 0:
        v = que[0]
        que.pop(0)
        
        for x in range(len(G[v])):
            if dist[G[v][x]] != -1:
                continue
            dist[G[v][x]] = dist[v]+1
            que.append(G[v][x])
    
    return dist

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

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

# アルゴリズム実行    
dist = BFS(G, 0)

# 結果出力
for v in range(N):
    print(v, ":", dist[v])

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

# 出力
# 0 : 0
# 1 : 1
# 2 : 1
# 3 : 2
# 4 : 1
# 5 : 2
# 6 : 3
# 7 : 3
# 8 : 2