如何订购连接列表

Question

我目前有一个存储在列表中的连接列表,其中每个连接是一个连接两个点的有向链接,没有任何点链接到多个点或链接到多个点.例如:

connections = [ (3, 7), (6, 5), (4, 6), (5, 3), (7, 8), (1, 2), (2, 1) ]

应该产生:

ordered = [ [ 4, 6, 5, 3, 7, 8 ], [ 1, 2, 1 ] ]

我尝试使用一种算法来做到这一点,该算法采用输入点和连接列表,并递归调用自身以找到下一个点并将其添加到增长的有序列表中.但是,当我没有从正确的点开始时,我的算法会崩溃(尽管这应该只是反向重复相同的算法),但是当有多个未连接的链时

编写有效算法来订购这些连接的最佳方法是什么？

Answer 1

解决方案的算法

您正在寻找拓扑排序算法:

from collections import defaultdict

def topological_sort(dependency_pairs):
    'Sort values subject to dependency constraints'
    num_heads = defaultdict(int)   # num arrows pointing in
    tails = defaultdict(list)      # list of arrows going out
    for h, t in dependency_pairs:
        num_heads[t] += 1
        tails[h].append(t)

    ordered = [h for h in tails if h not in num_heads]
    for h in ordered:
        for t in tails[h]:
            num_heads[t] -= 1
            if not num_heads[t]:
                ordered.append(t)
    cyclic = [n for n, heads in num_heads.iteritems() if heads]
    return ordered, cyclic

if __name__ == '__main__':
    connections = [(3, 7), (6, 5), (4, 6), (5, 3), (7, 8), (1, 2), (2, 1)]
    print topological_sort(connections)

以下是样本数据的输出:

([4, 6, 5, 3, 7, 8], [1, 2])

运行时与边数(依赖关系)成线性比例.

这个怎么运作

该算法围绕一个名为num_heads的查找表进行组织,该查找表保持计数前驱者的数量(传入箭头).考虑具有以下连接的示例:a->h b->g c->f c->h d->i e->d f->b f->g h->d h->e i->b,计数是:

node  number of incoming edges
----  ------------------------
 a       0
 b       2
 c       0
 d       2
 e       1
 f       1  
 g       2
 h       2
 i       1

该算法通过"visting"没有前任的节点来工作.例如,节点a并c没有传入边,因此首先访问它们.

访问意味着节点将从图表中输出和删除.当访问节点时,我们遍历其后继者并将其传入计数减1.

例如,在访问节点中a,我们转到其后继者h将其传入计数减1(这样h 2就变成了h 1.

同样地,访问节点时c,我们遍历其继承人f和h,一个递减计数的(这样f 1变得f 0和h 1变h 0).

节点f并且h不再有传入边缘,因此我们重复输出它们并从图形中删除它们直到所有节点都被访问过程.在示例中,访问顺序(拓扑排序):

a c f h e d i b g

如果num_heads到达没有没有传入边缘的节点的状态,那么这意味着存在一个无法进行拓扑排序的循环,并且算法将退出以显示请求的结果.