C#语言实现拓扑排序（Topological Sorting）算法

C#语言实现拓扑排序（Topological Sorting）算法

在C#中，同样可以使用Kahn算法和深度优先搜索（DFS）来实现拓扑排序。以下是这两种算法的实现：

使用Kahn算法的实现

Kahn算法基于顶点的入度来进行拓扑排序。以下是具体实现：

using System;
using System.Collections.Generic;
using System.Linq;

public class TopologicalSortKahn
{
    public static List<int> TopologicalSort(int numVertices, List<Tuple<int, int>> edges)
    {
        List<int> result = new List<int>();
        int[] inDegree = new int[numVertices];
        Dictionary<int, List<int>> graph = new Dictionary<int, List<int>>();
        
        // 初始化图和入度
        for (int i = 0; i < numVertices; i++)
        {
            graph[i] = new List<int>();
        }
        
        foreach (var edge in edges)
        {
            int from = edge.Item1;
            int to = edge.Item2;
            graph[from].Add(to);
            inDegree[to]++;
        }
        
        // 将所有入度为0的顶点加入队列
        Queue<int> queue = new Queue<int>();
        for (int i = 0; i < numVertices; i++)
        {
            if (inDegree[i] == 0)
            {
                queue.Enqueue(i);
            }
        }
        
        // 处理队列中的顶点
        while (queue.Count > 0)
        {
            int current = queue.Dequeue();
            result.Add(current);
            
            foreach (var neighbor in graph[current])
            {
                inDegree[neighbor]--;
                if (inDegree[neighbor] == 0)
                {
                    queue.Enqueue(neighbor);
                }
            }
        }
        
        if (result.Count != numVertices)
        {
            throw new InvalidOperationException("The graph has a cycle!");
        }
        
        return result;
    }

    public static void Main()
    {
        int numVertices = 6;
        List<Tuple<int, int>> edges = new List<Tuple<int, int>>
        {
            new Tuple<int, int>(5, 2),
            new Tuple<int, int>(5, 0),
            new Tuple<int, int>(4, 0),
            new Tuple<int, int>(4, 1),
            new Tuple<int, int>(2, 3),
            new Tuple<int, int>(3, 1)
        };
        
        Console.WriteLine("Topological Sort (Kahn's Algorithm): " + string.Join(", ", TopologicalSort(numVertices, edges)));
    }
}

使用DFS的实现

DFS算法利用递归来实现拓扑排序。以下是具体实现：

using System;
using System.Collections.Generic;

public class TopologicalSortDFS
{
    private void Dfs(int node, bool[] visited, Stack<int> stack, Dictionary<int, List<int>> graph)
    {
        visited[node] = true;
        
        foreach (var neighbor in graph[node])
        {
            if (!visited[neighbor])
            {
                Dfs(neighbor, visited, stack, graph);
            }
        }
        
        stack.Push(node);
    }

    public List<int> TopologicalSort(int numVertices, List<Tuple<int, int>> edges)
    {
        Stack<int> stack = new Stack<int>();
        bool[] visited = new bool[numVertices];
        Dictionary<int, List<int>> graph = new Dictionary<int, List<int>>();
        
        // 初始化图
        for (int i = 0; i < numVertices; i++)
        {
            graph[i] = new List<int>();
        }
        
        foreach (var edge in edges)
        {
            int from = edge.Item1;
            int to = edge.Item2;
            graph[from].Add(to);
        }
        
        // 对每个顶点执行DFS
        for (int i = 0; i < numVertices; i++)
        {
            if (!visited[i])
            {
                Dfs(i, visited, stack, graph);
            }
        }
        
        List<int> result = new List<int>();
        while (stack.Count > 0)
        {
            result.Add(stack.Pop());
        }
        
        return result;
    }

    public static void Main()
    {
        int numVertices = 6;
        List<Tuple<int, int>> edges = new List<Tuple<int, int>>
        {
            new Tuple<int, int>(5, 2),
            new Tuple<int, int>(5, 0),
            new Tuple<int, int>(4, 0),
            new Tuple<int, int>(4, 1),
            new Tuple<int, int>(2, 3),
            new Tuple<int, int>(3, 1)
        };
        
        TopologicalSortDFS ts = new TopologicalSortDFS();
        Console.WriteLine("Topological Sort (DFS): " + string.Join(", ", ts.TopologicalSort(numVertices, edges)));
    }
}

这两种方法都可以有效地实现拓扑排序，选择哪种方法取决于具体的应用场景和个人偏好。