深さ優先探索は、グラフを横断して頂点を正確に一度だけ表示する探索手法です。この記事では、pythonでグラフを走査するための深さ優先探索を研究し、実装します。
おすすめの読み物 Pythonでグラフを実装する
深さ優先探索アルゴリズムとは？
深さ優先探索では、グラフの各頂点を任意の1点から出発してちょうど1回ずつ走査します。選択された各頂点について、まずその頂点を表示し、次にその隣りの頂点の一つに移動して表示し、その隣りの頂点の一つに移動して表示する、というように繰り返します。この処理は、すべての頂点を走査し終えるまで続けられる。深さ優先探索でグラフを走査している間は、選択した頂点を起点として、すべての頂点を走査する経路を移動しているように見えます。
このことは、次の例からよく理解できます。
Algorithm DFS:Input: Graph(Adjacency list) and Source vertex
Output: DFS traversal of graphStart: 1.Create an empty stack S.
2.Create an empty list to keep record of visited vertices.
3.Insert source vertex into S, mark the source as visited.
4.If S is empty, return. Else goto 5.
5.Take out a vertex v from S.
6.Print the Vertex v.
7.Insert all the unvisited vertices in the adjacency list of v into S and mark them visited.
10.Goto 4.
Stop. |
上のグラフを0から深さ優先で見ていくと、 0->3->4->5->2->1 の順に頂点を処理していくことになります。0にいるときに3の前に1を処理する場合、グラフのBFSトラバーサルは次のようになります。0–>1–>3->4->2->5.
この記事もチェック：Pythonのグラフの深さ優先探索アルゴリズムを初心者にわかりやすく解説する
グラフの深さ優先探索アルゴリズム
深さ優先探索の一般的な考え方がわかったので，次にグラフのDFS探索の アルゴリズムを定式化する．ここでは、グラフのすべての頂点が開始頂点から到達可能であると仮定します。
グラフの隣接リスト表現と開始頂点が与えられたとします。ここで、深さ優先探索の方法でグラフを走査しなければならない。
まず、始点の値を表示し、次にその隣りの頂点に移動してその値を表示し、その隣りの頂点に移動し、グラフのすべての頂点が表示されるまで、これを繰り返す。
つまり，グラフの頂点を最初の頂点から順に走査し，すべての頂点を走査し終えるまで印刷し続けるというタスクがあるわけです．このコンセプトを実現するために、グラフを処理するためにスタック（last in first out）技術を使用することにします。また、頂点が2回表示されないように、訪問した頂点のリストを使って、その頂点が過去に走査されたかどうかをチェックします。
ある頂点を表示し、それを訪問済み頂点リストに追加し、その近傍頂点をスタックに入れる。次に、スタックから頂点を一つずつ取り出して、それを印刷した後に訪問済みリストに追加し、その近傍点をスタックに入れます。以下は、全体の処理を描いたグラフの深さ優先探索探索探索のアルゴリズムです。
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 dfs(graph, source):
S = list()
visited_vertices = list()
S.append(source)
visited_vertices.append(source)
while S:
vertex = S.pop()
print(vertex, end="-->")
for u in graph[vertex]:
if u not in visited_vertices:
S.append(u)
visited_vertices.append(u)
print("DFS traversal of graph with source 0 is:")
dfs(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: []}
DFS traversal of graph with source 0 is:
0-->3-->4-->5-->2-->1-->
|
結果を出力すると、以下の様になります。
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 dfs_explanation(graph, source):
S = list()
visited_vertices = list()
S.append(source)
visited_vertices.append(source)
while S:
vertex = S.pop()
print("processing vertex {}.".format(vertex))
for u in graph[vertex]:
if u not in visited_vertices:
print("At {}, adding {} to Stack".format(vertex, u))
S.append(u)
visited_vertices.append(u)
print("Visited vertices are:", visited_vertices)
print("Explanation of DFS traversal of graph with source 0 is:")
dfs_explanation(graph, 0)
|
もし、コードの実行が理解できなかった場合は、各ステップを説明した修正DFSアルゴリズムを紹介します。
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 DFS traversal of graph with source 0 is:
processing vertex 0.
At 0, adding 1 to Stack
At 0, adding 3 to Stack
Visited vertices are: [0, 1, 3]
processing vertex 3.
At 3, adding 4 to Stack
Visited vertices are: [0, 1, 3, 4]
processing vertex 4.
At 4, adding 2 to Stack
At 4, adding 5 to Stack
Visited vertices are: [0, 1, 3, 4, 2, 5]
processing vertex 5.
Visited vertices are: [0, 1, 3, 4, 2, 5]
processing vertex 2.
Visited vertices are: [0, 1, 3, 4, 2, 5]
processing vertex 1.
Visited vertices are: [0, 1, 3, 4, 2, 5]
|
結果は以下の通りです。
この記事もチェック：Pythonによる決定木アルゴリズムの実装を詳しく説明していく
まとめ
この記事では、グラフの深さ優先探索トラバーサルアルゴリズムの背後にある基本的な概念を見て、そのアルゴリズムを設計し、そしてpythonでそれを実装しました。今後も有益な記事をお届けします。