9

我目前有一个存储在列表中的连接列表，其中每个连接都是连接两个点的有向链接，并且没有任何点链接到多个点或链接到多个点。例如：

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 ] ]

我尝试使用一种算法来执行此操作，该算法采用输入点和连接列表并递归调用自身以查找下一个点并将其添加到不断增长的有序列表中。但是，当我没有从正确的点开始时（尽管这应该只是反向重复相同算法的问题），而且当有多个未连接的链时，我的算法就会崩溃

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

4

3 回答 3

19

解决方案的算法

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

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.

同样，当访问节点时c，我们循环遍历它的后继者f和h，将它们的计数减一（这样f 1变成f 0和h 1变成h 0）。

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

a c f h e d i b g

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

于 2013-05-07T01:06:39.683 回答
2

像这样的东西：

from collections import defaultdict
lis = [ (3, 7), (6, 5), (4, 6), (5, 3), (7, 8), (1, 2), (2, 1) ]
dic = defaultdict(list)

for k,v in lis:
    if v not in dic:
        dic[k].append(v)
    else:
        dic[k].extend([v]+dic[v])
        del dic[v]

for k,v in dic.items():
    for x in v:
        if x in dic and x!=k:
            dic[k].extend(dic[x])
            del dic[x]

print dic
print [[k]+v for k,v in dic.items()]

输出：

defaultdict(<type 'list'>, {2: [1, 2], 4: [6, 5, 3, 7, 8]})
[[2, 1, 2], [4, 6, 5, 3, 7, 8]]
于 2013-05-07T01:20:53.853 回答
0

我认为你可以O(n)用这样的方法来做到这一点：

ordered = {}

for each connection (s,t):
  if t exists in ordered :
     ordered[s] = [t] + ordered[t]
     del ordered[t]
  else:
     ordered[s] = [t]

# Now merge...
for each ordered (s : [t1, t2, ... tN]):
  ordered[s] = [t1, t2, ... tN] + ordered[tN]
  del ordered[tN]

最后你会得到这样的东西，但你可以很容易地转换它

ordered = { 
  4 : [6, 5, 3, 7, 8],
  2 : [1, 2]
}
于 2013-05-07T00:54:22.190 回答