将项目添加到给定的拓扑类别中

Question

有生产者-消费者图。该图的拓扑排序是T。我想向拓扑排序T中添加其他节点，并改变T的顺序。这里假设的是，消费者关系的优先级高于生产者关系。

我能想到的解决方案是：

For new node N:
    check the last producer in the T for which N is consumer. Let it be T1
    check the last consumer in T for which N is producer. Let it be I2.
    If I1 < I2, add N after I1
    If I1 > I2, add N after I1 -- I assumed that consumer relationship is much more important than producer
    If I1 is null, add N before I2
    If I2 is null, add N before I1
    If there is a cyclic dependency make it acyclic by removing a consumer relationship

是否有任何有效的算法？我错过了任何用例吗？任何帮助都受到高度赞赏？

Answer 1

为了将节点有效地添加到诸如此类的拓扑中。必须在DAG中除了Node之外的其他组件上运行DFS。由于拓扑排序是通过查找没有传入边的节点创建的，因此必须在所有节点都存在时运行排序。意思是，如果需要新的拓扑排序，则必须提供一个DAG，其中所有需要排序的节点都存在，然后运行DFS来编译拓扑排序。