C# でトポロジーソートアルゴリズムを実装する方法

C# でトポロジカル ソート アルゴリズムを実装するには、特定のコード サンプルが必要です。

トポロジカル ソートは、有向グラフ内のノードの問題を解決するために使用される一般的なグラフ アルゴリズムです。間。ソフトウェア開発では、タスクのスケジューリングやコンパイル順序などの問題を解決するために、トポロジカル ソートがよく使用されます。この記事では、C# でトポロジカル ソート アルゴリズムを実装する方法を紹介し、具体的なコード例を示します。

1. アルゴリズム原理

トポロジカル並べ替えアルゴリズムは、有向グラフの隣接リストを確立し、深さ優先検索 (DFS) または幅優先を使用することによって表されます。検索 (BFS) を使用して、グラフ内のノードを走査し、特定の順序で出力します。

具体的な手順は次のとおりです。

1) 有向グラフの隣接リストを構築します。有向グラフ内の各ノードを構造として表し、ノードの依存関係を To として表します。サイド。

2) 各ノードの入次数をカウントします。隣接関係テーブルを調べて、各ノードの入次数をカウントします。

3) キューを作成します。入次数が 0 のノードをキューに入れます。

4) 入次数 0 のノードに従ってトラバースを開始します。キューから入次数 0 のノードを取り出し、このノードをソート結果に追加し、隣接するすべての次数のノードの入次数を加算します。このノードのノード数を 1 減らします。

5) キューが空になるまで上記の手順を繰り返します。

2. コードの実装

次は、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 サイトの他の関連記事を参照してください。