C# でトポロジカル ソート アルゴリズムを実装するには、特定のコード サンプルが必要です。
トポロジカル ソートは、有向グラフ内のノードの問題を解決するために使用される一般的なグラフ アルゴリズムです。間。ソフトウェア開発では、タスクのスケジューリングやコンパイル順序などの問題を解決するために、トポロジカル ソートがよく使用されます。この記事では、C# でトポロジカル ソート アルゴリズムを実装する方法を紹介し、具体的なコード例を示します。
トポロジカル並べ替えアルゴリズムは、有向グラフの隣接リストを確立し、深さ優先検索 (DFS) または幅優先を使用することによって表されます。検索 (BFS) を使用して、グラフ内のノードを走査し、特定の順序で出力します。
具体的な手順は次のとおりです。
1) 有向グラフの隣接リストを構築します。有向グラフ内の各ノードを構造として表し、ノードの依存関係を To として表します。サイド。
2) 各ノードの入次数をカウントします。隣接関係テーブルを調べて、各ノードの入次数をカウントします。
3) キューを作成します。入次数が 0 のノードをキューに入れます。
4) 入次数 0 のノードに従ってトラバースを開始します。キューから入次数 0 のノードを取り出し、このノードをソート結果に追加し、隣接するすべての次数のノードの入次数を加算します。このノードのノード数を 1 減らします。
5) キューが空になるまで上記の手順を繰り返します。
次は、C# を使用してトポロジカル ソート アルゴリズムを実装するためのサンプル コードです。#:
using System; using System.Collections.Generic; public class Graph { private int V; //图中节点的个数 private List<int>[] adj; //图的邻接表 public Graph(int v) { V = v; adj = new List<int>[v]; for (int i = 0; i < v; ++i) adj[i] = new List<int>(); } public void AddEdge(int v, int w) { adj[v].Add(w); //将节点w加入节点v的邻接表中 } public void TopologicalSort() { int[] indegree = new int[V]; //用于统计每个节点的入度 for (int i = 0; i < V; ++i) indegree[i] = 0; //统计每个节点的入度 for (int v = 0; v < V; ++v) { List<int> adjList = adj[v]; foreach (int w in adjList) indegree[w]++; } Queue<int> queue = new Queue<int>(); //存放入度为0的节点 for (int i = 0; i < V; ++i) { if (indegree[i] == 0) queue.Enqueue(i); } List<int> result = new List<int>(); //存放排序结果 int count = 0; //已经排序的节点个数 while (queue.Count > 0) { int v = queue.Dequeue(); result.Add(v); count++; //将与节点v相邻的节点的入度减1 List<int> adjList = adj[v]; foreach (int w in adjList) { indegree[w]--; if (indegree[w] == 0) queue.Enqueue(w); } } //判断是否有环 if (count != V) { Console.WriteLine("图中存在环!"); return; } //输出排序结果 Console.WriteLine("拓扑排序结果:"); foreach (int v in result) { Console.Write(v + " "); } } } public class Program { public static void Main(string[] args) { Graph g = new Graph(6); g.AddEdge(5, 2); g.AddEdge(5, 0); g.AddEdge(4, 0); g.AddEdge(4, 1); g.AddEdge(2, 3); g.AddEdge(3, 1); g.TopologicalSort(); } }
上記のコードを実行すると、次の結果が得られます。
拓扑排序结果: 5 4 2 3 1 0
上記は、C# で実装されたトポロジカル ソート アルゴリズムの具体的なコード例です。有向グラフのトポロジカルなソートは、グラフの隣接リストを構築し、次数を数え、走査にキューを使用することによって実現できます。
以上がC# でトポロジーソートアルゴリズムを実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。