c#实现图的拓扑排序

原文链接：https://blog.csdn.net/MfuuJava/article/details/132933517

拓扑排序是一种在有向无环图（DAG）中对节点进行排序的算法。

在 C# 中，我们可以使用深度优先搜索（DFS）和拓扑排序算法来解决这个问题。

深度优先代码：

using System;
using System.Collections.Generic;

class Graph
{
    private int V; // 图中节点的数量
    private List<List<int>> adj; // 邻接列表

    // 构造函数
    public Graph(int v)
    {
        V = v;
        adj = new List<List<int>>(v);
        for (int i = 0; i < v; ++i)
            adj.Add(new List<int>());
    }

    // 添加边
    public void AddEdge(int v, int w)
    {
        adj[v].Add(w);
    }

    // 拓扑排序的辅助函数
    private void TopologicalSortUtil(int v, bool[] visited, Stack<int> stack)
    {
        visited[v] = true;

        foreach (int i in adj[v])
        {
            if (!visited[i])
                TopologicalSortUtil(i, visited, stack);
        }

        stack.Push(v);
    }

    // 执行拓扑排序
    public void TopologicalSort()
    {
        Stack<int> stack = new Stack<int>();

        bool[] visited = new bool[V];
        for (int i = 0; i < V; i++)
            visited[i] = false;

        for (int i = 0; i < V; i++)
        {
            if (visited[i] == false)
                TopologicalSortUtil(i, visited, stack);
        }

        // 打印排序结果
        while (stack.Count > 0)
        {
            Console.Write(stack.Pop() + " ");
        }
    }

    // 测试
    public static void Main(string[] args)
    {
        Graph graph = new Graph(6);
        graph.AddEdge(5, 2);
        graph.AddEdge(5, 0);
        graph.AddEdge(4, 0);
        graph.AddEdge(4, 1);
        graph.AddEdge(2, 3);
        graph.AddEdge(3, 1);

        Console.WriteLine("拓扑排序结果：");
        graph.TopologicalSort();
        Console.ReadKey();
    }
}

在上述代码中，我们首先定义了一个 Graph 类，用于表示有向无环图。Graph 类包含了图中节点的数量和一个邻接列表 adj，用于存储图的边。

我们使用 AddEdge 方法向图中添加边。然后，在 TopologicalSortUtil 方法中，我们使用搜索来遍历图，并将访问过的节点压入栈中。

最后，在 TopologicalSort 方法中，我们遍历图中的所有节点，并调用 TopologicalSortUtil 方法进行拓扑排序。最终，我们打印栈中的元素，即可得到拓扑排序的结果。

在上述示例中，我们创建了一个包含6个节点的图，并添加了一些边。然后，我们执行拓扑排序，并打印排序结果。