How to implement topological sorting algorithm in C#

How to implement the topological sorting algorithm in C# requires specific code examples

Topological sorting is a common graph algorithm used to solve the problem of nodes in directed graphs. dependencies between. In software development, topological sorting is often used to solve problems such as task scheduling and compilation order. This article will introduce how to implement the topological sorting algorithm in C# and provide specific code examples.

1. Algorithm Principle

The topological sorting algorithm is represented by establishing an adjacency list of a directed graph, and then using depth-first search (DFS) or breadth-first search (BFS) to traverse nodes in the graph and output them in a certain order.

The specific steps are as follows:

1) Construct the adjacency list of the directed graph: represent each node in the directed graph as a structure, and represent the dependence of the nodes as To the side.

2) Count the in-degree of each node: Traverse the adjacency table and count the in-degree of each node.

3) Create a queue: put nodes with an in-degree of 0 into the queue.

4) Start traversing according to the node with in-degree 0: Take out a node with in-degree 0 from the queue, add this node to the sorting result, and add the in-degrees of all adjacent nodes of this node Decrease by 1.

5) Repeat the above steps until the queue is empty.

2. Code implementation

The following is a sample code for implementing the topological sorting algorithm using 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();
    }
}

Run the above code, the following results will be output:

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

The above is a specific code example of the topological sorting algorithm implemented in C#. Topological sorting of directed graphs can be achieved by building adjacency lists of graphs, counting in-degrees, and using queues for traversal.

The above is the detailed content of How to implement topological sorting algorithm in C#. For more information, please follow other related articles on the PHP Chinese website!