解决方案的算法

您正在寻找一种拓扑排序算法：

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

该算法通过“访问”没有前任节点的节点来工作。例如，节点a且c没有传入边缘，因此它们首先被访问。

访问是指将节点输出并从图中删除。当访问节点时，我们遍历其后继节点，并将其传入计数减一。

例如，在访问节点中a，我们转到其后继节点以将h其传入计数减一（因此h 2变为）h 1。

同样，在访问node时c，我们遍历其后继者f和h，并将其计数减一（从而f 1成为f 0和h 1成为h 0）。

节点f和h不再具有传入边，因此我们重复输出它们并将其从图中移除的过程，直到访问完所有节点为止。在示例中，访问顺序（拓扑排序是）：

a c f h e d i b g

如果num_heads曾经达到没有节点没有传入边缘的状态，则意味着存在无法按拓扑排序的循环，并且算法退出以显示请求的结果。