如何按先修依赖参数排序Course列表，保证依赖项排在对应元素前

问题描述 #

现有Course类型列表，需要按以下规则排序：如果某列表元素关联了依赖项，依赖项必须排在当前元素的前面。
示例：Id为2的记录RequiredCourse字段值为3，意味着Id为3的元素必须排在Id为2的元素之前。

当前实现存在两个问题：

• 无法正确处理多层依赖：例如Id为3的记录依赖Id为4的课程，现有逻辑无法覆盖
• 无依赖元素顺序异常：例如Id为8的记录依赖Id为10的课程，Id为9没有任何关联依赖，现有代码交换8和10的位置后，8会排到9的后面

现有实现代码 #

var list = new List<Course>();

list.Add(new Course { Id = 1 });
list.Add(new Course { Id = 2, RequiredCourse = "3" });
list.Add(new Course { Id = 3, RequiredCourse = "4" });
list.Add(new Course { Id = 4 });
list.Add(new Course { Id = 5 });
list.Add(new Course { Id = 6 });
list.Add(new Course { Id = 7 });
list.Add(new Course { Id = 8, RequiredCourse = "10" });
list.Add(new Course { Id = 9 });
list.Add(new Course { Id = 10 });
list = list.OrderBy(i => i.Id).ThenBy(i => i.RequiredCourse).ToList();

var copy = new List<Course>(list);

for (int i = 0; i < copy.Count; i++)
{
    if (!string.IsNullOrEmpty(copy[i].RequiredCourse) && Int32.Parse(copy[i].RequiredCourse) > copy[i].Id)
    {
        var index = list.FindIndex(k => k.Id == Int32.Parse(copy[i].RequiredCourse));
        if (index > -1)
        {
            var temp = list[i];
            list[i] = list[index];
            list[index] = temp;
        }
    }
}

错误输出 #

1                
3                4
4                
2                3
5                
6                
7                
10               
9                
8                10

预期输出 #

1                
4                
3                4
2                3
5                
6                
7                
10               
8                10
9                

解决方案 #

该场景属于典型的有向无环图拓扑排序场景，单次交换的方式无法处理多层依赖，也无法保证无依赖节点的相对顺序，正确实现如下：

首先补充Course类定义：

public class Course
{
    public int Id { get; set; }
    public string RequiredCourse { get; set; }
}

排序逻辑实现：

// 构建Id到Course的映射，提升查找效率
var idToCourse = list.ToDictionary(c => c.Id);
// 统计每个节点的入度，构建依赖邻接表
var inDegree = new Dictionary<int, int>();
var adjacency = new Dictionary<int, List<int>>();
foreach (var course in list)
{
    inDegree[course.Id] = 0;
    adjacency[course.Id] = new List<int>();
}
foreach (var course in list)
{
    if (string.IsNullOrEmpty(course.RequiredCourse)) continue;
    var requiredId = int.Parse(course.RequiredCourse);
    // 依赖节点指向当前节点，当前节点入度+1
    adjacency[requiredId].Add(course.Id);
    inDegree[course.Id]++;
}

// 拓扑排序：先加入入度为0的节点，按Id升序保证无依赖节点顺序符合预期
var queue = new Queue<int>(inDegree.Where(kv => kv.Value == 0).Select(kv => kv.Key).OrderBy(id => id));
var result = new List<Course>();
while (queue.Count > 0)
{
    var currentId = queue.Dequeue();
    result.Add(idToCourse[currentId]);
    // 遍历当前节点的所有后继节点，入度-1，减到0则加入队列
    foreach (var nextId in adjacency[currentId])
    {
        inDegree[nextId]--;
        if (inDegree[nextId] == 0)
        {
            queue.Enqueue(nextId);
        }
    }
}

// 最终result即为排序后的列表，若result.Count不等于原列表长度说明存在循环依赖

该实现天然支持多层依赖排序，无依赖节点默认按Id升序排列，同时支持循环依赖检测。

内容的提问来源于stack exchange，提问作者beetlejuice