C#에서 위상 정렬 알고리즘을 구현하려면 구체적인 코드 예제가 필요합니다.
위상 정렬은 방향성 그래프에서 노드 간의 종속성을 해결하는 데 사용되는 일반적인 그래프 알고리즘입니다. 소프트웨어 개발에서 토폴로지 정렬은 작업 스케줄링 및 컴파일 순서와 같은 문제를 해결하는 데 자주 사용됩니다. 이 문서에서는 C#에서 토폴로지 정렬 알고리즘을 구현하는 방법을 소개하고 구체적인 코드 예제를 제공합니다.
위상 정렬 알고리즘은 방향성 그래프의 인접 목록을 설정한 후 깊이 우선 탐색(DFS) 또는 너비 우선 탐색(BFS)을 사용하여 그래프의 노드를 순회하고 특정 순서대로 출력합니다.
구체적인 단계는 다음과 같습니다.
1) 유향 그래프의 인접 목록을 구성합니다. 유향 그래프의 각 노드를 구조로 표현하고, 노드의 종속성을 유향 간선으로 표현합니다.
2) 각 노드의 내부 차수 계산: 인접 목록을 순회하고 각 노드의 내부 차수를 계산합니다.
3) 대기열 만들기: in차수가 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!