如何对包含有向无环图的元组列表排序？自定义IComparer测试未全通过

我需要对类型为List<(string, List<string>)>的有向图元组列表排序，尝试用自定义IComparer实现，但部分测试用例无法通过，不知道问题出在哪。

我的排序实现代码 #

public class Class1
{
    public static List<(string, List<string>)> OrderList(List<(string, List<string>)> tupleList)
    {
        // 使用自定义TupleComparer排序
        tupleList.Sort(new TupleComparer());

        return tupleList;
    }
}
public class TupleComparer : IComparer<(string, List<string>)>
{
    public int Compare((string, List<string>) x, (string, List<string>) y)
    {
        if (x.Item2.Contains(y.Item1))
        {
            return -1; // x应该在y后面
        }
        else if (y.Item2.Contains(x.Item1))
        {
            return 1; // x应该在y前面
        }
        else
        {
            // 没有依赖关系时，按原位置比较（实际返回0会导致排序不稳定）
            return 0;
        }
    }
}

测试代码 #

public class LinkedListTests
{
    [Test]
    [TestCaseSource(nameof(GetTupleLists))]
    public void Test1(List<(string, List<string>)> tupleList)
    {
        var result = Class1.OrderList(tupleList);

        Assert.AreEqual(result[0].Item1, "p1");
        Assert.AreEqual(result[1].Item1, "p3");
        Assert.AreEqual(result[2].Item1, "p4");
    }
    private static IEnumerable<List<(string, List<string>)>> GetTupleLists()
    {
        // 返回不同初始顺序的测试用例
        yield return new List<(string, List<string>)>
        {
            ("p1", new List<string> { "p2", "p3" }),
            ("p3", new List<string> { "p4" }),
            ("p4", new List<string> { "p5", "p6" })
        };
        yield return new List<(string, List<string>)>
        {
            ("p1", new List<string> { "p2", "p3" }),
            ("p4", new List<string> { "p5","p6"}),
            ("p3", new List<string> { "p4" })
        };
        yield return new List<(string, List<string>)>
        {
            ("p3", new List<string> { "p4" }),
            ("p1", new List<string> { "p2", "p3" }),
            ("p4", new List<string> { "p5","p6"})
        };
        yield return new List<(string, List<string>)>
        {
            ("p3", new List<string> { "p4" }),
            ("p4", new List<string> { "p5","p6"}),
            ("p1", new List<string> { "p2", "p3" })
        };
        yield return new List<(string, List<string>)>
        {
            ("p4", new List<string> { "p5","p6"}),
            ("p1", new List<string> { "p2", "p3" }),
            ("p3", new List<string> { "p4" })
        };
        yield return new List<(string, List<string>)>
        {
            ("p4", new List<string> { "p5","p6"}),
            ("p3", new List<string> { "p4" }),
            ("p1", new List<string> { "p2", "p3" })
        };
    }
}

问题原因 #

你用IComparer的思路根本不对，因为比较排序的核心要求是比较逻辑必须满足传递性，但你的实现不满足这个条件：

• 比如比较p1和p3：p1的依赖包含p3，所以p1应该在p3前面，返回1
• 比较p3和p4：p3的依赖包含p4，所以p3应该在p4前面，返回1
• 但比较p1和p4时，两者的依赖列表都不包含对方的节点，你的代码返回0，意味着两者“相等”，排序算法无法确定它们的相对顺序，这就会导致部分测试用例中p4出现在p3前面，或者p1出现在p3后面，不符合预期。

另外，List.Sort依赖Comparer的传递性，一旦逻辑不满足，排序结果就是不可预测的。你的场景本质是有向无环图的拓扑排序，不是普通的两两比较排序，不能用IComparer来实现。

解决方案：拓扑排序实现 #

把原来的OrderList方法替换成拓扑排序的实现，就能正确处理所有依赖关系：

public class Class1
{
    public static List<(string, List<string>)> OrderList(List<(string, List<string>)> tupleList)
    {
        // 构建节点到元组的映射
        var nodeMap = tupleList.ToDictionary(t => t.Item1, t => t);
        // 统计每个节点的入度（有多少节点依赖它）
        var inDegree = new Dictionary<string, int>();
        foreach (var tuple in tupleList)
        {
            if (!inDegree.ContainsKey(tuple.Item1))
                inDegree[tuple.Item1] = 0;
            foreach (var dep in tuple.Item2)
            {
                if (nodeMap.ContainsKey(dep)) // 只考虑列表中存在的节点
                {
                    if (!inDegree.ContainsKey(dep))
                        inDegree[dep] = 0;
                    inDegree[dep]++;
                }
            }
        }

        // 初始化队列，放入所有入度为0的节点（没有被任何列表内节点依赖的节点）
        var queue = new Queue<string>();
        foreach (var node in inDegree.Where(kv => kv.Value == 0).Select(kv => kv.Key))
        {
            queue.Enqueue(node);
        }

        var result = new List<(string, List<string>)>();
        while (queue.Count > 0)
        {
            var current = queue.Dequeue();
            result.Add(nodeMap[current]);

            // 遍历当前节点的依赖，减少它们的入度
            foreach (var dep in nodeMap[current].Item2)
            {
                if (nodeMap.ContainsKey(dep))
                {
                    inDegree[dep]--;
                    if (inDegree[dep] == 0)
                    {
                        queue.Enqueue(dep);
                    }
                }
            }
        }

        // 如果存在环的话，这里会有节点没被处理，根据需求可以抛出异常或者返回部分结果
        if (result.Count != tupleList.Count)
            throw new InvalidOperationException("图中存在环，无法拓扑排序");

        return result;
    }
}

说明 #

这个实现会：

1. 先统计每个节点的入度（即有多少个列表内的节点依赖它）
2. 从没有依赖的节点（入度为0，比如p1，因为没有其他节点依赖它）开始处理
3. 每处理一个节点，就将它依赖的节点的入度减1，当某个节点入度变为0时，加入队列处理
4. 最终得到的结果就是符合依赖顺序的拓扑排序结果，所有测试用例都会通过

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