1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111

// Target.cs
//==-----------------------------==//
/// 这个类负责标记一个目标及其依赖
public class Target
{
    /// <summary>
    /// Target名称
    /// </summary>
    public string Name { get; init; } = "Target Name";

    /// <summary>
    /// Target的依赖
    /// </summary>
    public string[] Deps { get; init; } = Array.Empty<string>();
}


// Topological.cs
//==-----------------------------==//
using System.Collections.Generic;

/// 拓扑排序主函数
public static Queue<Target> Sort(
    // 客户需要的目标
    Target whatToSort,
    // 客户所有的目标
    Target[] total)
{
    // 用于标记一个Target的排序状态
    // 如果target对应的key未找到，则target还未被排序
    // 如果target对应的value为true，则key正在被排序
    // 如果value为false，则key已经被排序过，并被加入到输出
    Dictionary<Target, bool> targetStatus =
        new();

    // 最后的输出。使用队列来保证顺序
    Queue<Target> output = new();

    // 处理
    Visit(total, whatToSort, targetStatus, output);

    return output;
}

/// 负责对一个target进行排序
/// 是一个辅助函数，不应该设置为public
private static void Visit(
    // 所有的Target
    Target[] total,
    // 要排序的目标
    Target target,
    // target状态
    Dictionary<Target, bool> targetStatus,
    // 输出队列
    Queue<Target> output)
{

    // 检查要排序的目标的状态
    if (targetStatus.TryGetValue(target, out bool isSortting))
    {
        // 要排序的目标正在被排序
        // 说明我们再次排序了这个目标！存在循环依赖
        if (isSortting)
        {
            throw new RuntimeException($"Circular dependency detected. At target `{target.Name}`.");
        }
        // 我们要排序的目标及其依赖已经被排序过了
        // 并且已经被加入到了输出
        // 我们设计是：一个目标只完成一次，so 忽略
        else return;
    }
    // 目标没有被设置状态
    // 则目标没有被排序过
    else
    {
        // 设置目标状态为：当前正在被排序
        targetStatus.Add(target, true);

        // 排序所有依赖
        foreach (var depStr in target.Deps)
        {
            // 获取依赖
            Target? dep = null;

            foreach (var ddepStr in total)
            {
                // 找到依赖
                if (ddepStr.Name == depStr)
                {
                    dep = ddepStr;
                    break;
                }
            }

            if (dep == null)
                throw new RuntimeException($"Miss depend `{depStr}` in target `{target.Name}` !");

            // 对这些依赖进行排序
            Visit(total, dep, targetStatus, output);
        }

        // 我们已经将目标的所有依赖添加到输出了
        // 确保了执行当前目标之前，依赖目标会被执行
        // 则添加当前目标到输出
        output.Enqueue(target);

        // 将当前目标的状态标记为：已经被排序
        targetStatus.Remove(target);
        targetStatus.Add(target, false);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

Target 吃饭 = new();
吃饭.Name = "吃饭";
吃饭.Deps = new string[]{ "做饭","洗手" };

Target 做饭 = new();
吃饭.Name = "做饭";
吃饭.Deps = new string[]{ "洗手" };

Target 洗手 = new();
吃饭.Name = "洗手";
吃饭.Deps = new string[0]();

Target[] 所有事务 = new Target[]{吃饭，做饭，洗手};

var result = Sort(吃饭,所有事物);

foreach(var whatToDoNext in result){
    Console.WriteLine(whatToDoNext.Name);
}

// result:
// 洗手 做饭 吃饭