So implementieren Sie einen topologischen Sortieralgorithmus in C#

Für die Implementierung des topologischen Sortieralgorithmus in C# sind spezifische Codebeispiele erforderlich.

Topologische Sortierung ist ein gängiger Graphalgorithmus, der zum Lösen der Abhängigkeiten zwischen Knoten in gerichteten Graphen verwendet wird. In der Softwareentwicklung wird die topologische Sortierung häufig verwendet, um Probleme wie die Aufgabenplanung und die Kompilierungsreihenfolge zu lösen. In diesem Artikel wird die Implementierung des topologischen Sortieralgorithmus in C# vorgestellt und spezifische Codebeispiele bereitgestellt.

1. Algorithmusprinzip

Der topologische Sortieralgorithmus wird durch die Erstellung einer Adjazenzliste eines gerichteten Diagramms dargestellt und verwendet dann die Tiefensuche (DFS) oder die Breitensuche (BFS), um die Knoten im Diagramm zu durchqueren in einer bestimmten Reihenfolge ausgeben.

Die spezifischen Schritte sind wie folgt:

1) Erstellen Sie die Adjazenzliste des gerichteten Diagramms: Stellen Sie jeden Knoten im gerichteten Diagramm als Struktur dar und stellen Sie die Abhängigkeiten der Knoten als gerichtete Kanten dar.

2) Zählen Sie den In-Grad jedes Knotens: Durchlaufen Sie die Adjazenzliste und zählen Sie den In-Grad jedes Knotens.

3) Erstellen Sie eine Warteschlange: Fügen Sie Knoten mit einem In-Grad von 0 in die Warteschlange ein.

4) Beginnen Sie mit der Durchquerung entsprechend dem Knoten mit In-Grad 0: Nehmen Sie einen Knoten mit In-Grad 0 aus der Warteschlange, fügen Sie diesen Knoten zum Sortierergebnis hinzu und reduzieren Sie den In-Grad aller benachbarten Knoten dieses Knotens um 1.

5) Wiederholen Sie die oben genannten Schritte, bis die Warteschlange leer ist.

2. Code-Implementierung

Das Folgende ist ein Beispielcode für die Implementierung des topologischen Sortieralgorithmus mit 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();
    }
}

Beim Ausführen des obigen Codes werden die folgenden Ergebnisse ausgegeben:

拓扑排序结果：
5 4 2 3 1 0

Das Obige ist ein spezifisches Codebeispiel für die topologische Sortierung Mit C# implementierter Algorithmus. Die topologische Sortierung gerichteter Graphen kann erreicht werden, indem Adjazenzlisten von Graphen erstellt, In-Grade gezählt und Warteschlangen zum Durchlaufen verwendet werden.

Das obige ist der detaillierte Inhalt vonSo implementieren Sie einen topologischen Sortieralgorithmus in C#. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!