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