Comment implémenter un algorithme de tri topologique en C#

Comment implémenter l'algorithme de tri topologique en C#, des exemples de code spécifiques sont nécessaires

Le tri topologique est un algorithme de graphe courant utilisé pour résoudre les dépendances entre les nœuds dans les graphes orientés. Dans le développement de logiciels, le tri topologique est souvent utilisé pour résoudre des problèmes tels que la planification des tâches et l'ordre de compilation. Cet article explique comment implémenter l'algorithme de tri topologique en C# et fournit des exemples de code spécifiques.

1. Principe de l'algorithme

L'algorithme de tri topologique est représenté en établissant une liste de contiguïté d'un graphe orienté, puis utilise la recherche en profondeur d'abord (DFS) ou la recherche en largeur d'abord (BFS) pour parcourir les nœuds du graphe et sortez-le dans un certain ordre.

Les étapes spécifiques sont les suivantes :

1) Construire la liste d'adjacence du graphe orienté : représenter chaque nœud du graphe orienté comme une structure, et représenter les dépendances des nœuds comme des arêtes orientées.

2) Comptez le degré en entrée de chaque nœud : parcourez la liste de contiguïté et comptez le degré en entrée de chaque nœud.

3) Créez une file d'attente : placez les nœuds avec un degré d'entrée de 0 dans la file d'attente.

4) Commencez le parcours en fonction du nœud de degré 0 : retirez un nœud de degré 0 de la file d'attente, ajoutez ce nœud au résultat du tri et réduisez le degré de tous les nœuds adjacents de ce nœud. par 1.

5) Répétez les étapes ci-dessus jusqu'à ce que la file d'attente soit vide.

2. Implémentation du code

Ce qui suit est un exemple de code pour implémenter l'algorithme de tri topologique en utilisant 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();
    }
}

L'exécution du code ci-dessus produira les résultats suivants :

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

Ce qui précède est un exemple de code spécifique pour le tri topologique algorithme implémenté en C#. Le tri topologique des graphiques orientés peut être réalisé en créant des listes de graphiques adjacents, en comptant en degrés et en utilisant des files d'attente pour le parcours.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!