【Python】BFS(幅優先探索)を使ってグラフ内のノードから到達可能なすべてのノードを検索する方法

グラフ構造において、特定のノードから到達可能なすべてのノードを調べたい場合、幅優先探索(BFS)を利用するのが最も一般的かつ効率的なアプローチです。本記事では、Pythonの標準ライブラリである collections.deque(両端キュー)を使ってBFSを実装し、指定した複数のノードそれぞれから到達できるノードの一覧を出力するプログラムを紹介します。

サンプルコード

from collections import deque

def add_edge(v, w):

    global visited_node, adj
    adj[v].append(w)
    adj[w].append(v)

def BFS_operation(component_num, src):

    global visited_node, adj
    queue = deque()

    queue.append(src)

    visited_node[src] = 1
    reachableNodes = []

    while (len(queue) > 0):

        u = queue.popleft()
        reachableNodes.append(u)
        for itr in adj[u]:
            if (visited_node[itr] == 0):

                visited_node[itr] = 1
                queue.append(itr)

    return reachableNodes

def displayReachableNodes(m):

    for i in m:
        print(i, end = " ")
    print()

def findReachableNodes(my_list, n):

    global V, adj, visited_node

    a = []

    component_num = 0

    for i in range(n):
        u = my_list[i]

        if (visited_node[u] == 0):
            component_num += 1

        a = BFS_operation(component_num, u)

    print("The reachable nodes from ", u, " are")
    displayReachableNodes(a)

V = 7
adj = [[] for i in range(V + 1)]
visited_node = [0 for i in range(V + 1)]
add_edge(1, 2)
add_edge(2, 3)
add_edge(3, 4)
add_edge(3, 1)
add_edge(5, 6)
add_edge(5, 7)

my_list = [ 2, 4, 5, 7 ]

arr_len = len(my_list)
findReachableNodes(my_list, arr_len)

実行結果

The reachable nodes from 2 are
2 1 3 4
The reachable nodes from 4 are
2 1 3 4
The reachable nodes from 5 are
5 6 7
The reachable nodes from 7 are
5 6 7

コードの解説

• まず、両端キューを扱うための deque を collections モジュールからインポートします。

• add_edge 関数は、グラフに無向のエッジ(辺)を追加するためのものです。隣接リスト adj の双方向に要素を登録することで、どちらの方向からも移動できるようにしています。

• BFS_operation 関数が本プログラムの中核となる部分です。始点ノードをキューに入れ、訪問済みフラグ(visited_node)を立てながら、キューが空になるまでノードを取り出しては隣接ノードを順次追加していくことで、幅優先探索を実現しています。探索が完了すると、到達可能だったノードのリストを返します。

• displayReachableNodes 関数は、引数として受け取ったノードのリストを整形してコンソールに出力します。

• findReachableNodes 関数は、指定されたノードのリストを反復処理し、まだ訪問されていないノードに対して BFS_operation を呼び出すことで、連結成分ごとの到達可能ノードを求めます。

• その後、add_edge を使って7つの頂点を持つグラフを構築します。この例では「1-2-3-4」でつながる成分と、「5-6-7」でつながる成分の2つの連結成分が存在します。

• 調べたい始点ノードのリスト [2, 4, 5, 7] を定義し、関数を呼び出して結果を表示しています。

ポイントと計算量

BFSでは訪問済み管理が非常に重要です。visited_node 配列によって一度訪れたノードを二度探索しないようにすることで、無限ループを防ぎつつ効率的な探索が可能になります。計算量は頂点数をV、エッジ数をEとすると O(V + E) となり、大規模なグラフでも高速に動作します。また、同じ連結成分に属するノードからは必ず同一の到達可能ノード集合が得られるため、実行結果のように「2」と「4」、「5」と「7」の出力が一致していることが確認できます。