ホームページ バックエンド開発 Python チュートリアル Pythonを使用してトポロジカルソートアルゴリズムを実装するにはどうすればよいですか?

Pythonを使用してトポロジカルソートアルゴリズムを実装するにはどうすればよいですか?

Sep 21, 2023 am 11:05 AM
Python はトポロジーソートを実装します トポロジカルソートアルゴリズムのPython実装 Pythonを使用してトポロジカルソートを実装する

Pythonを使用してトポロジカルソートアルゴリズムを実装するにはどうすればよいですか?

Python を使用してトポロジカル ソート アルゴリズムを実装するにはどうすればよいですか?

トポロジカル ソートはグラフ理論のソート アルゴリズムであり、有向非巡回グラフ (DAG) のソートに使用されます。トポロジカル ソートでは、グラフ内のノードはタスクまたはイベントを表し、有向エッジはタスクまたはイベント間の依存関係を表します。ソートされた結果では、すべての依存関係が満たされ、各ノードはそのすべての先行ノードの後に​​ランク付けされます。

Python でのトポロジカル ソート アルゴリズムの実装は、深さ優先検索 (DFS) のアイデアを使用して解決できます。具体的なコード例を次に示します。

from collections import defaultdict

class Graph:
    def __init__(self, num_vertices):
        self.graph = defaultdict(list)
        self.num_vertices = num_vertices

    def add_edge(self, u, v):
        self.graph[u].append(v)

    def topological_sort_util(self, v, visited, stack):
        visited[v] = True

        for i in self.graph[v]:
            if visited[i] == False:
                self.topological_sort_util(i, visited, stack)

        stack.append(v)

    def topological_sort(self):
        visited = [False] * self.num_vertices
        stack = []

        for i in range(self.num_vertices):
            if visited[i] == False:
                self.topological_sort_util(i, visited, stack)

        sorted_list = []
        while stack:
            sorted_list.append(stack.pop())

        return sorted_list

# 测试代码
g = Graph(6)
g.add_edge(5, 2)
g.add_edge(5, 0)
g.add_edge(4, 0)
g.add_edge(4, 1)
g.add_edge(2, 3)
g.add_edge(3, 1)

sorted_list = g.topological_sort()
print("拓扑排序结果:", sorted_list)
ログイン後にコピー

上記のコードは、まず、エッジの追加やトポロジカルな並べ替えなどのメソッドを含む Graph クラスを定義します。トポロジカルソート中、深さ優先検索を使用してグラフ内のノードを走査します。スタックを使用して訪問したノードを保存すると、最終的にトポロジー順序付けルールに従って配置されたノードのリストを取得できます。

上記のコードには、トポロジカル ソート アルゴリズムの正確さを検証するための簡単なテスト ケースも含まれています。このテスト ケースでは、サイズ 6 のグラフが定義され、いくつかのノードとエッジが追加されます。最後に、トポロジー的にソートされたノード リストを出力します。

Python を使用してトポロジカル並べ替えアルゴリズムを実装すると、グラフ内の依存関係を簡単に処理できるため、タスクのスケジュール設定などの問題に非常に役立ちます。このアルゴリズムを理解して適用することで、実際の問題をより適切に解決できるようになります。この記事がお役に立てば幸いです。

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

このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。

ホットAIツール

Undresser.AI Undress

Undresser.AI Undress

リアルなヌード写真を作成する AI 搭載アプリ

AI Clothes Remover

AI Clothes Remover

写真から衣服を削除するオンライン AI ツール。

Undress AI Tool

Undress AI Tool

脱衣画像を無料で

Clothoff.io

Clothoff.io

AI衣類リムーバー

Video Face Swap

Video Face Swap

完全無料の AI 顔交換ツールを使用して、あらゆるビデオの顔を簡単に交換できます。

ホットツール

メモ帳++7.3.1

メモ帳++7.3.1

使いやすく無料のコードエディター

SublimeText3 中国語版

SublimeText3 中国語版

中国語版、とても使いやすい

ゼンドスタジオ 13.0.1

ゼンドスタジオ 13.0.1

強力な PHP 統合開発環境

ドリームウィーバー CS6

ドリームウィーバー CS6

ビジュアル Web 開発ツール

SublimeText3 Mac版

SublimeText3 Mac版

神レベルのコード編集ソフト(SublimeText3)

LinuxターミナルでPythonバージョンを表示するときに発生する権限の問題を解決する方法は? LinuxターミナルでPythonバージョンを表示するときに発生する権限の問題を解決する方法は? Apr 01, 2025 pm 05:09 PM

LinuxターミナルでPythonバージョンを表示する際の許可の問題の解決策PythonターミナルでPythonバージョンを表示しようとするとき、Pythonを入力してください...

あるデータフレームの列全体を、Python内の異なる構造を持つ別のデータフレームに効率的にコピーする方法は? あるデータフレームの列全体を、Python内の異なる構造を持つ別のデータフレームに効率的にコピーする方法は? Apr 01, 2025 pm 11:15 PM

PythonのPandasライブラリを使用する場合、異なる構造を持つ2つのデータフレーム間で列全体をコピーする方法は一般的な問題です。 2つのデータがあるとします...

プロジェクトの基本と問題駆動型の方法で10時間以内にコンピューター初心者プログラミングの基本を教える方法は? プロジェクトの基本と問題駆動型の方法で10時間以内にコンピューター初心者プログラミングの基本を教える方法は? Apr 02, 2025 am 07:18 AM

10時間以内にコンピューター初心者プログラミングの基本を教える方法は?コンピューター初心者にプログラミングの知識を教えるのに10時間しかない場合、何を教えることを選びますか...

中間の読書にどこでもfiddlerを使用するときにブラウザによって検出されないようにするにはどうすればよいですか? 中間の読書にどこでもfiddlerを使用するときにブラウザによって検出されないようにするにはどうすればよいですか? Apr 02, 2025 am 07:15 AM

fiddlereveryversings for the-middleの測定値を使用するときに検出されないようにする方法

uvicornは、serving_forever()なしでhttpリクエストをどのように継続的に聞いていますか? uvicornは、serving_forever()なしでhttpリクエストをどのように継続的に聞いていますか? Apr 01, 2025 pm 10:51 PM

UvicornはどのようにしてHTTPリクエストを継続的に聞きますか? Uvicornは、ASGIに基づく軽量のWebサーバーです。そのコア機能の1つは、HTTPリクエストを聞いて続行することです...

人気のあるPythonライブラリとその用途は何ですか? 人気のあるPythonライブラリとその用途は何ですか? Mar 21, 2025 pm 06:46 PM

この記事では、numpy、pandas、matplotlib、scikit-learn、tensorflow、django、flask、and requestsなどの人気のあるPythonライブラリについて説明し、科学的コンピューティング、データ分析、視覚化、機械学習、Web開発、Hの使用について説明します。

文字列を介してオブジェクトを動的に作成し、Pythonでメソッドを呼び出す方法は? 文字列を介してオブジェクトを動的に作成し、Pythonでメソッドを呼び出す方法は? Apr 01, 2025 pm 11:18 PM

Pythonでは、文字列を介してオブジェクトを動的に作成し、そのメソッドを呼び出す方法は?これは一般的なプログラミング要件です。特に構成または実行する必要がある場合は...

See all articles