用于在多个链表上快速获得部分排序的算法

Question

我有一个情况,如下:

• 我有n个双向链表
• 每个列表都有一个哨兵的开头和结尾
• 列表都有相同的开始和结束节点(不是必需的,但为了简单起见)
• 列表是同质的,可以共享项目

我想找到所有n个列表中所有节点的部分排序,从开始节点开始到结束节点结束,这样任何出现在nx列表中的节点,其中x <n,将被排序相对于它出现的所有列表中的其他节点.

使用数组提供一组示例列表:

first  = [a, b,    d,    f,    h, i];
second = [a, b, c,       f, g,    i];
third  = [a,          e, f, g, h, i];

显然,一个可能的答案是[a,b,c,d,e,f,g,h,i],但另一个可接受的顺序是[a,b,d,e,c,f,g,h,一世].

我知道,有是一个快速算法来做到这一点,没有任何人记得是怎么一回事呢还是它叫什么？我已经有一些慢版本,但我确信在Knuth的某个地方有一个更快的版本.

(而且,在你问之前,这不是为了家庭作业或项目欧拉,我不能使这更具体.这是问题.)

编辑:我相对确定只有端点在所有列表中并且位于相同位置(开始和结束)时才定义部分排序.我不会反对线性时间搜索来找到那些端点,如果找不到它们,那么就可以在那里产生错误.

Answer 1

对我来说看起来与拓扑排序非常相似。有几种算法可以让您获得拓扑排序的状态。我特别喜欢的类似于广度优先搜索。维护两个列表，其中一个是没有入边的所有节点（例如，L最初只是a节点），另一个是具有部分有序节点的节点F。现在每一步，

pick a node from `L`, 
do some operations (explained later), 
and move the chosen node to the `F` list. 

在“做一些操作步骤”中，

choose all successors of the source node which have exactly one in-link add them to L.
Remove the link from the source node to all the successors in the previous step 

现在，该列表F已按拓扑排序了所有节点。我对这个糟糕的解释感到抱歉，维基链接有很好的图表:)