グラフのトラバーサルアルゴリズムは様々な応用が可能です。
その応用の一つに、グラフの2つのノード間の最小距離を求めることがある。
今回は、重みのない完全連結グラフにおいて、幅優先グラフ探索アルゴリズムを用いて最小距離を求めるアルゴリズムをpythonで実装します。
この記事もチェック：Pythonでグラフの深さ優先探索アルゴリズムを実装する方法を解説する
BFSアルゴリズムをGRaphに使う
Breadth-first search はグラフの探索アルゴリズムの一つで、グラフの各頂点を任意の1点から正確に1回だけ探索します。
選択された各頂点について、まずその頂点を表示し、次にその近傍点をすべて表示します。
この処理は、すべての頂点を走査し終えるまで続けられる。
幅優先探索でグラフを走査している間は、選択した頂点から何層にも移動しているように見えます。
グラフに対するBFSアルゴリズムの実装は次の通りです。
このアルゴリズムでは、グラフは無重量、無向性、完全連結であると仮定しています。
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})
|
重みのないグラフの2つのノード間の最短距離の決定
幅優先探索アルゴリズムにある種の修正を加えることで、あるソースからすべてのノードへの最短距離を求めることができる。
グラフのソースと隣接リスト表現が与えられたら、訪問したすべての頂点を含むリストを宣言し、さらに、辞書のキーが頂点を決定し、値が現在の頂点とソースの間の距離を決定する辞書を作成します。
BFSアルゴリズムの変更点は、頂点vを処理するたびに、その近傍の距離を更新することです。
vの近傍の送信元からの距離は、vの送信元からの距離を1つ足したものとなる。
この記事もチェック：Pythonのグラフの深さ優先探索アルゴリズムを初心者にわかりやすく解説する
最小距離を求めるアルゴリズム
発生源から各頂点までの最短距離の求め方は大体分かったので、そのアルゴリズムを定式化します。
Algorithm Least Distance:Input: Graph(Adjacency list) and Source vertex
Output: A list with distance of each vertex from source
Start: 1.Create an empty queue Q.
2.Create an empty set to keep record of visited vertices.
3. Create a dictionary in which keys of the dictionary determine the vertex and values determine the distance between current vertex and source.
4.Insert source vertex into the Q and Mark the source as visited.
5.If Q is empty, return. Else goto 6.
6.Take out a vertex v from Q.
7.Insert all the vertices in the adjacency list of v which are not in the visited list into Q and mark them visited after updating their distance from source.
8.Goto 5.
Stop. |
最小距離を計算するグラフのトラバーサルを実装する
ソースからの頂点の最小距離を求めるアルゴリズムを定式化したので、そのアルゴリズムを実装し、次の画像で与えられるグラフに対してアルゴリズムを実行します。
from queue import Queue
myGraph = {0: [1, 3], 1: [0, 2, 3], 2: [4, 1, 5], 3: [4, 0, 1], 4: [2, 3, 5], 5: [4, 2]}
def leastDistance(graph, source):
Q = Queue()
# create a dictionary with large distance(infinity) of each vertex from source
distance = {k: 9999999 for k in myGraph.keys()}
visited_vertices = set()
Q.put(source)
visited_vertices.update({0})
while not Q.empty():
vertex = Q.get()
if vertex == source:
distance[vertex] = 0
for u in graph[vertex]:
if u not in visited_vertices:
# update the distance
if distance[u] > distance[vertex] + 1:
distance[u] = distance[vertex] + 1
Q.put(u)
visited_vertices.update({u})
return distance
print("Least distance of vertices from vertex 0 is:")
print(leastDistance(myGraph, 0))
|
Pythonによるアルゴリズムの実装は以下の通りです。
Least distance of vertices from vertex 0 is:
{0: 0, 1: 1, 2: 2, 3: 1, 4: 2, 5: 3}
|
結果を出力すると、以下の様になります。
まとめ
今回は、深さ優先探索のトラバーサルアルゴリズムを用いて、グラフのソースと他の頂点との間の最小距離を求めるアルゴリズムを実装しました。
今後も有益な記事を期待しています。