Bagaimana untuk melaksanakan algoritma pengisihan topologi dalam C#

Bagaimana untuk melaksanakan algoritma pengisihan topologi dalam C#, contoh kod khusus diperlukan

Isihan topologi ialah algoritma graf biasa yang digunakan untuk menyelesaikan kebergantungan antara nod dalam graf terarah. Dalam pembangunan perisian, pengisihan topologi sering digunakan untuk menyelesaikan masalah seperti penjadualan tugas dan susunan penyusunan. Artikel ini akan memperkenalkan cara melaksanakan algoritma pengisihan topologi dalam C# dan memberikan contoh kod khusus.

1. Prinsip algoritma

Algoritma pengisihan topologi diwakili dengan mewujudkan senarai bersebelahan graf terarah, dan kemudian menggunakan carian pertama mendalam (DFS) atau carian pertama luas (BFS) untuk merentasi nod dalam graf dan mengeluarkannya dalam susunan tertentu.

Langkah khusus adalah seperti berikut:

1) Bina senarai bersebelahan graf yang diarahkan: mewakili setiap nod dalam graf terarah sebagai struktur, dan mewakili kebergantungan nod sebagai tepi terarah.

2) Kira dalam darjah setiap nod: lalui senarai bersebelahan dan kira dalam darjah setiap nod.

3) Buat baris gilir: letakkan nod dengan darjah 0 ke dalam baris gilir.

4) Mula merentasi mengikut nod dengan dalam darjah 0: Keluarkan nod dengan darjah 0 dari baris gilir, tambahkan nod ini pada hasil pengisihan dan kurangkan dalam darjah semua nod bersebelahan nod ini oleh 1.

5) Ulang langkah di atas sehingga barisan kosong.

2. Pelaksanaan kod

Berikut ialah contoh kod untuk melaksanakan algoritma pengisihan topologi menggunakan 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();
    }
}

Menjalankan kod di atas akan mengeluarkan keputusan berikut:

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

Di atas ialah contoh kod khusus untuk pengisihan topologi algoritma dilaksanakan menggunakan C#. Pengisihan topologi graf terarah boleh dicapai dengan membina senarai bersebelahan graf, mengira dalam darjah dan menggunakan baris gilir untuk traversal.

Atas ialah kandungan terperinci Bagaimana untuk melaksanakan algoritma pengisihan topologi dalam C#. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!