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 サイトの他の関連記事を参照してください。

ホットAIツール

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

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

Undress AI Tool
脱衣画像を無料で

Clothoff.io
AI衣類リムーバー

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

人気の記事

ホットツール

メモ帳++7.3.1
使いやすく無料のコードエディター

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

ゼンドスタジオ 13.0.1
強力な PHP 統合開発環境

ドリームウィーバー CS6
ビジュアル Web 開発ツール

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

ホットトピック









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

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

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

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

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

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

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