Python-data-structure-python-graph-algorithms
提供:Dev Guides
Python-グラフアルゴリズム
グラフは、多くの重要な数学的課題を解決する上で非常に有用なデータ構造です。 たとえば、コンピューターネットワークトポロジや、化合物の分子構造の分析。 また、都市交通やルート計画、さらには人間の言語や文法でも使用されます。 これらのすべてのアプリケーションには、エッジを使用してグラフを走査し、グラフのすべてのノードにアクセスするという共通の課題があります。 このトラバーサルを行うには、以下に説明する2つの一般的な確立された方法があります。
深さ優先走査:
深さ優先検索(DFS)とも呼ばれるこのアルゴリズムは、深さ方向にグラフを走査し、スタックを使用して、繰り返しで行き止まりが発生したときに、検索を開始する次の頂点を取得することを忘れないようにします。 訪問済みノードと未訪問ノードを追跡するために必要な機能を提供するため、設定されたデータ型を使用して、PythonのグラフにDFSを実装します。
class graph:
def __init__(self,gdict=None):
if gdict is None:
gdict = {}
self.gdict = gdict
# Check for the visisted and unvisited nodes
def dfs(graph, start, visited = None):
if visited is None:
visited = set()
visited.add(start)
print(start)
for next in graph[start] - visited:
dfs(graph, next, visited)
return visited
gdict = { "a" : set(["b","c"]),
"b" : set(["a", "d"]),
"c" : set(["a", "d"]),
"d" : set(["e"]),
"e" : set(["a"])
}
dfs(gdict, 'a')
上記のコードが実行されると、次の結果が生成されます-
a b d e c
幅優先トラバーサル
幅優先検索(BFS)とも呼ばれるこのアルゴリズムは、グラフの幅方向の動きを走査し、キューを使用して、繰り返しで行き止まりが発生したときに、検索を開始する次の頂点を取得することを忘れないようにします。 グラフのBFSステップの詳細を理解するには、当社のWebサイトのこのリンクをご覧ください。
前述のキューデータ構造を使用して、PythonのグラフにBFSを実装します。 隣接する未訪問のノードを訪問し続け、それをキューに追加し続けるとき。 次に、未訪問のノードが残っていないノードのみのデキューを開始します。 訪問する次の隣接ノードがない場合、プログラムを停止します。
import collections
class graph:
def __init__(self,gdict=None):
if gdict is None:
gdict = {}
self.gdict = gdict
def bfs(graph, startnode):
# Track the visited and unvisited nodes using queue
seen, queue = set([startnode]), collections.deque([startnode])
while queue:
vertex = queue.popleft()
marked(vertex)
for node in graph[vertex]:
if node not in seen:
seen.add(node)
queue.append(node)
def marked(n):
print(n)
# The graph dictionary
gdict = { "a" : set(["b","c"]),
"b" : set(["a", "d"]),
"c" : set(["a", "d"]),
"d" : set(["e"]),
"e" : set(["a"])
}
bfs(gdict, "a")
上記のコードが実行されると、次の結果が生成されます-
a c b d e