パンくずリスト探索は、グラフを横断して頂点を正確に一度だけ表示する探索手法です。今回は、pythonでグラフを走査するための幅優先探索を学習し、実装します。
Breadth-First Search Algorithm（幅優先探索アルゴリズム）とは？
幅優先探索では、グラフの各頂点を正確に一度だけ走査し、任意の1つの頂点から開始します。選択された各頂点について、まずその頂点を表示し、次にその近傍点をすべて表示します。この処理は、すべての頂点を走査し終えるまで続けられる。幅優先探索でグラフを巡回していると、選択した頂点を起点として何層にも移動しているように見えます。
このことは、次の例からよく理解できます。
Algorithm BFS:Input: Graph(Adjacency list) and Source vertex
Output: BFS traversal of graphStart: 1.Create an empty queue Q.
2.Create an empty set to keep record of visited vertices.
3.Insert source vertex into the Q and Mark the source as visited.
4.If Q is empty, return. Else goto 5.
5.Take out a vertex v from Q.
6.Print the Vertex.
7.Insert all the vertices in the adjacency list of v which are not in visited list into Q and mark them visited.
8.Goto 4.
Stop. |
上のグラフを0から順に広さ優先で見ていくと、 0->1->3->2->4->5 の順番で頂点を処理していくことになります。また、別のトラバーサルもありえます。0にいるときに1の前に3を処理する場合、グラフのBFSトラバーサルは次のようになります。0–>3–>1–>4–>2–>5.
Pythonで作るグラフのパンデスサーチアルゴリズム ## Breadth-First Search Algorithm
幅優先探索の概要がわかったので、次にグラフのBFS探索のアルゴリズムを定式化します。ここでは、グラフのすべての頂点が開始頂点から到達可能であると仮定します。
こちらもお読みください。Pythonでグラフを実装する
グラフの隣接リスト表現と開始頂点が与えられ、グラフを走査する必要があるとします。
まず開始頂点の値を表示し、次に開始頂点の隣接頂点の値を表示し、グラフのすべての頂点を表示するまで現在のレベルを終了して次のレベルに進みます。
つまり、グラフの現在のレベルにある頂点を、最初の頂点から始めて、すべての頂点を走査するまで印刷するというタスクがあるわけです。このコンセプトを実現するために、先入れ先出しの手法、すなわちグラフを処理するための待ち行列を使用することにします。
また、頂点が2回表示されないように、訪問した頂点のリストを使って、過去にその頂点が走査されたかどうかをチェックします。
ある頂点を表示し、それを訪問済み頂点リストに追加し、その近傍をキューに 入れる。キューから頂点を一つずつ取り出し、それを印刷した後に訪問済みリストに追加し、その近傍点をキューに入れる。以下は、全体の処理を描いたグラフの幅優先探索探索探索のアルゴリズムです。
from queue import Queue
graph = {0: [1, 3], 1: [0, 2, 3], 2: [4, 1, 5], 3: [4, 0, 1], 4: [2, 3, 5], 5: [4, 2], 6: []}
print("The adjacency List representing the graph is:")
print(graph)
def bfs(graph, source):
Q = Queue()
visited_vertices = set()
Q.put(source)
visited_vertices.update({0})
while not Q.empty():
vertex = Q.get()
print(vertex, end="-->")
for u in graph[vertex]:
if u not in visited_vertices:
Q.put(u)
visited_vertices.update({u})
print("BFS traversal of graph with source 0 is:")
bfs(graph, 0)
|
Python によるグラフのパンくずリスト検索トラバーサル関数
さて、概念とアルゴリズムに慣れたところで、グラフの幅優先探索アルゴリズムを実装し、上図の例のグラフに対してアルゴリズムを実行します。
The adjacency List representing the graph is:
{0: [1, 3], 1: [0, 2, 3], 2: [4, 1, 5], 3: [4, 0, 1], 4: [2, 3, 5], 5: [4, 2], 6: []}
BFS traversal of graph with source 0 is:
0-->1-->3-->2-->4-->5-->
|
結果は以下の通りです。
from queue import Queue
graph = {0: [1, 3], 1: [0, 2, 3], 2: [4, 1, 5], 3: [4, 0, 1], 4: [2, 3, 5], 5: [4, 2], 6: []}
print("The adjacency List representing the graph is:")
print(graph)
def bfs_explanation(graph, source):
Q = Queue()
visited_vertices = set()
Q.put(source)
visited_vertices.update({0})
while not Q.empty():
vertex = Q.get()
print("Processing {} after taking out from Q".format(vertex))
for u in graph[vertex]:
if u not in visited_vertices:
print("At {}, adding {} to Q".format(vertex, u))
Q.put(u)
visited_vertices.update({u})
print("visited vertices are: ", visited_vertices)
print("Explanation of BFS traversal of graph with source 0 is:")
bfs_explanation(graph, 0)
|
実行の仕方がよくわからないという方のために、各ステップを説明した修正BFSアルゴリズムを紹介します。
The adjacency List representing the graph is:
{0: [1, 3], 1: [0, 2, 3], 2: [4, 1, 5], 3: [4, 0, 1], 4: [2, 3, 5], 5: [4, 2], 6: []}
Explanation of BFS traversal of graph with source 0 is:
Processing 0 after taking out from Q
At 0, adding 1 to Q
At 0, adding 3 to Q
visited vertices are: {0, 1, 3}
Processing 1 after taking out from Q
At 1, adding 2 to Q
visited vertices are: {0, 1, 2, 3}
Processing 3 after taking out from Q
At 3, adding 4 to Q
visited vertices are: {0, 1, 2, 3, 4}
Processing 2 after taking out from Q
At 2, adding 5 to Q
visited vertices are: {0, 1, 2, 3, 4, 5}
Processing 4 after taking out from Q
visited vertices are: {0, 1, 2, 3, 4, 5}
Processing 5 after taking out from Q
visited vertices are: {0, 1, 2, 3, 4, 5}
|
結果は以下の通りです。
まとめ
この記事では、グラフの幅優先探索探索アルゴリズムの背後にある基本的な概念を見て、そのアルゴリズムを設計し、そしてそれをPythonで実装してきました。また、Pythonでアルゴリズムを実行するステップバイステップも見てきました。今後も有益な記事を期待しています。