Tarjan アルゴリズムを Python で記述するにはどうすればよいですか?

Tarjan アルゴリズムを Python で記述するにはどうすればよいですか?

Tarjan アルゴリズムは、深さ優先探索 (DFS) に基づくグラフ アルゴリズムであり、強接続コンポーネント (SCC) 問題を解決するために使用されます。この記事では、Python で Tarjan アルゴリズムを記述する方法を、具体的なコード例とともに紹介します。

Tarjan のアルゴリズムの基本的な考え方は、各ノードのトラバーサル シーケンス番号と到達可能な最小シーケンス番号を記録しながら、DFS を介してグラフ内のノードをトラバースすることです。トラバーサル中に、現在のノードが到達可能なシーケンス番号の小さいノードがあった場合、それを一時スタックに追加し、トラバーサル終了後にスタックの最上位ノードがルートノードであるかどうかを判断します強く結合したコンポーネントのこと。その場合は、スタックからノードをポップし、結果リストに追加します。

以下は、Python を使用して Tarjan アルゴリズムを記述するコード例です。

def tarjan(graph):
    n = len(graph)
    index = [0] * n
    low_link = [0] * n
    on_stack = [False] * n
    stack = []
    result = []
    index_counter = 0

    def dfs(v):
        nonlocal index_counter
        index[v] = index_counter
        low_link[v] = index_counter
        index_counter += 1
        stack.append(v)
        on_stack[v] = True

        for w in graph[v]:
            if index[w] == -1:
                dfs(w)
                low_link[v] = min(low_link[v], low_link[w])
            elif on_stack[w]:
                low_link[v] = min(low_link[v], index[w])

        if low_link[v] == index[v]:
            scc = []
            while True:
                w = stack.pop()
                on_stack[w] = False
                scc.append(w)
                if w == v:
                    break
            result.append(scc)

    for v in range(n):
        if index[v] == -1:
            dfs(v)

    return result

上記のコードでは、2 次元リスト graph を使用して、グラフの隣接関係。 graph[i] は、頂点 i が到達できる頂点のセットを表します。アルゴリズムは各頂点を反復的に走査し、頂点がまだ訪問されていない場合は、DFS 関数が呼び出されて検索されます。 DFS 関数は、再帰的手法を使用して Tarjan アルゴリズムのコア ロジックを実装します。

Tarjan アルゴリズムを使用する場合は、グラフの隣接関係を 2 次元リスト graph に変換し、tarjan(graph) を呼び出して、の強結合成分リスト。

概要:

この記事では、Python で Tarjan アルゴリズムを作成する方法を紹介し、具体的なコード例を添付します。 Tarjan アルゴリズムの基本的な考え方を理解することで、このアルゴリズムをより適切に適用して、強く接続されたコンポーネントの問題を解決できるようになります。この記事が読者の Tarjan アルゴリズムの理解と使用に役立つことを願っています。

以上がTarjan アルゴリズムを Python で記述するにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。