このレッスンでは、アルゴリズムの背景にある理論と、PythonによるBreadth-First Search and Traversalの実装を説明します。まず、ノード探索に焦点を当て、次にBFSアルゴリズムを使ったグラフの探索について、2つの主要なタスクに採用できるよう掘り下げます。
図1.2.2.3.1………(/assets/images/icon-information-circle-solid.svg)
注意：このレッスンでは、隣接リストを実装したグラフを想定しています。
ブレッドファーストサーチ – 理論編
Breadth-First Search (BFS) は、グラフを一段ずつ系統的に走査し、その過程でBFS木を形成します。
ノード v （グラフや木のデータ構造のルートノード）から探索を始めると、BFSアルゴリズムはまずノード v のすべての隣接ノード（レベル1では子ノード）を隣接リストで与えられた順番に訪れます。次に、その隣接ノードの子ノード（レベル2）を考慮し、以下同様です。
このアルゴリズムは、グラフの走査と探索の両方に用いることができる。ある条件を満たすノード（目的ノード）を探索する場合、開始ノードから目的ノードまでの距離が最も短い経路を探索する。この距離は、探索した枝の数として定義される。
Breadth-First Searchは、2つのノード間の最短経路の探索、各ノードのレベルの決定、さらにはパズルゲームや迷路の解決など、多くの問題の解決に利用することができる。
大規模な迷路やパズルを解くのに最も効率的なアルゴリズムではなく、Dijkstra’s AlgorithmやAxxxxなどのアルゴリズムに負けていますが、それでも束で重要な役割を果たし、問題によってはDFSやBFSがヒューリスティックな同類よりも優れている場合があります。
B
ブレッドファーストサーチの実装 – ターゲットノードの検索
まず、検索から始めて、ターゲット・ノードを検索してみよう。ターゲット・ノードの他に、スタート・ノードも必要である。期待される出力は、開始ノードからターゲット・ノードに至るパスである。
これらを念頭に置き、アルゴリズムのステップを考慮に入れて、実装してみましょう。BFS探索の実装を「包む」ために、Graph クラスを定義することにする。
Graph` には、グラフ表現（この場合は隣接行列）と、グラフを扱うときに必要なすべてのメソッドが含まれています。ここでは、BFS探索とBFS探索の両方をこのクラスのメソッドとして実装する。
from queue import Queue
class Graph:
# Constructor
def __init__(self, num_of_nodes, directed=True):
self.m_num_of_nodes = num_of_nodes
self.m_nodes = range(self.m_num_of_nodes)
# Directed or Undirected
self.m_directed = directed
# Graph representation - Adjacency list
# We use a dictionary to implement an adjacency list
self.m_adj_list = {node: set() for node in self.m_nodes}
# Add edge to the graph
def add_edge(self, node1, node2, weight=1):
self.m_adj_list[node1].add((node2, weight))
if not self.m_directed:
self.m_adj_list[node2].add((node1, weight))
# Print the graph representation
def print_adj_list(self):
for key in self.m_adj_list.keys():
print("node", key, ": ", self.m_adj_list[key])
ラッパークラスを実装した後、そのメソッドの一つとしてBFS探索を実装します。
def bfs(self, start_node, target_node):
# Set of visited nodes to prevent loops
visited = set()
queue = Queue()
# Add the start_node to the queue and visited list
queue.put(start_node)
visited.add(start_node)
# start_node has not parents
parent = dict()
parent[start_node] = None
# Perform step 3
path_found = False
while not queue.empty():
current_node = queue.get()
if current_node == target_node:
path_found = True
break
for (next_node, weight) in self.m_adj_list[current_node]:
if next_node not in visited:
queue.put(next_node)
parent[next_node] = current_node
visited.add(next_node)
# Path reconstruction
path = []
if path_found:
path.append(target_node)
while parent[target_node] is not None:
path.append(parent[target_node])
target_node = parent[target_node]
path.reverse()
return path
経路を再構築する場合（見つかった場合），対象ノードからその親ノードを経て，開始ノードまで逆戻りすることになります．さらに、直感的に start_node から target_node に向かうようにパスを反転させますが、このステップは省略可能です。
一方、パスが存在しない場合、アルゴリズムは空のリストを返します。
先に説明した実装を念頭に置き、例のグラフに対してBFS探索を実行することでテストすることができます。
このグラフを Graph クラスで再現してみましょう。これは6つのノードを持つ無向グラフなので、次のようにインスタンス化します。
graph = Graph(6, directed=False)
次に、作成した Graph クラスのインスタンスに、グラフのすべてのエッジを追加します。
graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(0, 3)
graph.add_edge(0, 4)
graph.add_edge(1, 2)
graph.add_edge(2, 3)
graph.add_edge(2, 5)
graph.add_edge(3, 4)
graph.add_edge(3, 5)
graph.add_edge(4, 5)
では、Graphクラスが内部的にどのようにこのグラフを表現しているかを見てみましょう。
graph.print_adj_list()
これは、作成したグラフを表現するために使われる隣接リストを表示します。
node 0 : {(3, 1), (1, 1), (4, 1), (2, 1)}
node 1 : {(0, 1), (2, 1)}
node 2 : {(0, 1), (1, 1), (5, 1), (3, 1)}
node 3 : {(0, 1), (5, 1), (4, 1), (2, 1)}
node 4 : {(0, 1), (5, 1), (3, 1)}
node 5 : {(3, 1), (4, 1), (2, 1)}
この時点で、私たちはグラフを作成し、それがどのように隣接行列として保存されるかを理解しました。これを踏まえて、検索そのものを行うことができる。例えば、ノード0からノード5を探したいとします。
path = []
path = graph.bfs(0, 5)
print(path)
このコードを実行すると、次のようになる。
[0, 3, 5]
このグラフを見てみると、0と5の間の最短経路は確かに [0, 3, 5] であることがわかる。しかし、[0, 2, 5]や[0, 4, 5]を横切ることも可能です。しかし、BFSがどのようにノードを比較するのかを考えてみましょう。BFSは左から右へ「スキャン」し、隣接リストの左側で最初に「5」につながるノードが「3」なので、他のパスではなくこのパスが使われるのです。
これはBFSの特徴で、予想されることです。BFSは左から右へと探索し、同じように有効なパスが最初のパスの「後に」見つかった場合は、それを見つけることはありません。
注意：2つのノード間のパスが見つからない場合がある。このシナリオは、パスで結ばれていないノードが少なくとも2つ存在する、切断型グラフの典型です。
切断されたグラフは次のようになります。
このグラフでノード 0 と 3 の間のパスを検索しようとすると、検索は失敗し、空のパスが返されるでしょう。
パンゲアリングの実装 – グラフトラバーサル
Breadth-First Traversalは、Breadth-First Searchの特殊なケースで、ターゲットノードを探す代わりにグラフ全体を走査します。アルゴリズムは以前定義したものと同じですが、違いはターゲットノードをチェックせず、そこに至るパスを見つける必要がないことです。
これは実装を大幅に簡略化します。トラバースされる各ノードをプリントアウトして、どのようにノードを通過するのか直感的に理解できるようにしましょう。
def bfs_traversal(self, start_node):
visited = set()
queue = Queue()
queue.put(start_node)
visited.add(start_node)
while not queue.empty():
current_node = queue.get()
print(current_node, end = " ")
for (next_node, weight) in self.m_adj_list[current_node]:
if next_node not in visited:
queue.put(next_node)
visited.add(next_node)
注意: このメソッドは、前に実装した Graph クラスの一部として実装する必要があります。
さて、先に示した方法で、次のようなグラフの例を定義してみましょう。
# Create an instance of the `Graph` class
# This graph is undirected and has 5 nodes
graph = Graph(5, directed=False)
# Add edges to the graph
graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(1, 2)
graph.add_edge(1, 4)
graph.add_edge(2, 3)
最後に、このコードを実行してみましょう。
graph.bfs_traversal(0)
このコードを実行すると、BFSがスキャンした順番にノードが表示されます。
0 1 2 4 3
ステップ・バイ・ステップ
この例をもう少し深く掘り下げて、アルゴリズムがどのように動作するかを順を追って見ていきましょう。開始ノード 0 から探索を始めると、それは visited セットと queue に入れられます。まだ queue にノードが残っている間に、最初のノードを取り出して表示し、その近傍ノードをすべてチェックします。
近傍ノードを調べていく中で、それぞれのノードが訪問済みかどうかをチェックし、訪問済みでなければ queue に追加して訪問済みとマークします。
| ステップ｜キュー｜訪問済
| — | — | — |
| 開始ノード0を追加｜[0]｜{0}｜[0]｜[0]｜[0]｜{0 |
| 0を訪問し、キューに1 & 2を追加する | [1, 2] | {0} 。|
| 訪問1、キューに4を追加｜ [2, 4] | {0, 2}｜｜ 訪問2、キューに3を追加
| 訪問2、キューに3を追加｜[4、3]｜{0、1、2}｜。
| 訪問4、訪問していない隣人はいない｜ [3] | {0, 1, 1, 4}｜ 訪問4、訪問していない隣人はいない。|
| 訪問3、訪問していない隣人なし｜ [ ]｜{0、1、2、4、3}。|
時間の複雑さ
Breadth-First Traversal では，すべてのノードに一度だけアクセスし， 有向グラフの場合はすべての枝にも一度だけアクセスする．したがって、BFSアルゴリズムの時間計算量はO(|V| + |E|)となる。ここで、Vはグラフのノードの集合、Eはそのすべての枝（エッジ）の集合である。
結論
このレッスンでは、Breadth-First Searchアルゴリズムの背後にある理論を説明し、そのステップを定義しました。
また、PythonによるBreadth-First SearchとBreadth-First Traversalの実装を説明し、グラフの例でテストして、段階的にどのように動くかを確認しました。最後に、このアルゴリズムの時間複雑性を説明しました。