algorithm - 从有序集中查找包含图

Question

假设我有一组元素和它们之间的顺序关系(不是全部)。

为简单起见，我们假设它的一维片段包含在内。

从原始的分割列表中，我如何构建一个直接包含的图表(假设它可能来 self 的集合):

如何从黑色部分重建红色图？

我在 C# 中有一个 O(n^3) 解决方案，它非常丑陋，我想知道是否有更好的[伪代码]:

interface INode
{
    bool Includes(INode other);
    List<INode> Childs { get; set; }
}

class Graph
{
    public INode Root { get; set; }
}

class GraphBuilder
{
    public static Graph Build(IList<INode> nodes)
    {
        Graph result = new Graph();
        foreach (var segment in nodes) {
            segment.Childs = new List<INode>();
            bool isRoot = true;
            foreach (var segment2 in nodes)
            {
                if (segment2.Includes(segment))
                {
                    isRoot = false;
                }
                if (segment.Includes(segment2))
                {
                    bool isDirectChild = true;

                    foreach (var segment3 in nodes)
                    {
                        if (segment.Includes(segment3) && segment3.Includes(segment2))
                            isDirectChild = false;
                        break;
                    }
                    if (isDirectChild)
                        segment.Childs.Add(segment2);
                }
            }
            if (isRoot)
            {
                result.Root = segment;
            }
        }

        return result;
    }
}

Answer 1

首先使用有效算法(例如 Kahn's algorithm)对 DAG 进行拓扑排序及时 O(V+E)。

对于每个元素，只构建从它自身到它比原始 DAG 中最小的事物(按拓扑顺序)的箭头。弄清楚这些也需要时间 O(V+E)。

这是你的时间 O(V+E) 的红色图表。

请注意，仅读取 DAG 就需要时间 O(V+E)，所以这是您可能做的最好的，直到一个常数。