如何订购连接的列表 [英] How can I order a list of connections
问题描述
我现在有存储在一个列表，其中每个连接是连接两个点和无点永远链接到一个以上的点，或者被一个以上的点连接到一个有向链路连接的列表。例如：
I currently have a list of connections stored in a list where each connection is a directed link that connects two points and no point ever links to more than one point or is linked to by more than one point. For example:
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 ] ]
我尝试使用一种算法，采用输入点和连接的列表并递归调用自身找到下一个点，并将其添加到生长有序列表做到这一点。然而，我的算法发生故障时，我不正确的点开始（虽然这应该只是重复同样的逻辑算法反向的事），而且还当有多个未连接股
I have attempt to do this using an algorithm that takes an input point and a list of connections and recursively calls itself to find the next point and add it to the growing ordered list. However, my algorithm breaks down when I don't start with the correct point (though this should just be a matter of repeating the same algorithm in reverse), but also when there are multiple unconnected strands
什么是写一个有效的算法来订购这些连接的最佳方式？
What would be the best way of writing an efficient algorithm to order these connections?
推荐答案
您正在寻找一个拓扑排序算法：
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)
下面是为您的样本数据的输出：
Here is the output for your sample data:
([4, 6, 5, 3, 7, 8], [1, 2])
运行时是线性正比边缘（依赖对）的数目。
The runtime is linearly proportional to the number of edges (dependency pairs).
该算法是围绕一个查找表名为num_heads，保持一个计数predecessors（进入箭头）的数量。请考虑使用以下连接的例子： A-＆GT; H B-＆GT克C-＆GT;˚FC-＆GT; H D-＆GT;我E-＆GT; d F - ＆GT; b˚F - ＆GT克H- D 1和D H-＆GT; e I-＆GT; b 的计数是：
The algorithm is organized around a lookup table called num_heads that keeps a count the number of predecessors (incoming arrows). Consider an example with the following connections: a->h b->g c->f c->h d->i e->d f->b f->g h->d h->e i->b, the counts are:
node number of incoming edges
---- ------------------------
a 0
b 2
c 0
d 2
e 1
f 1
g 2
h 2
i 1
该算法的工作原理是，没有predecessorsvisting节点。例如，节点 A 和 C 没有入边，所以他们参观了第一位。
The algorithm works by "visting" nodes with no predecessors. For example, nodes a and c have no incoming edges, so they are visited first.
访问意味着节点是输出与从图中移除。当一个节点被访问，我们遍历其继承人和减一的来电数量。
Visiting means that the nodes are output and removed from the graph. When a node is visited, we loop over its successors and decrement their incoming count by one.
例如，在访问节点 A ，我们去它的后继 ^ h 来减一的来电数（让 H 2 变成 H 1 。
For example, in visiting node a, we go to its successor h to decrement its incoming count by one (so that h 2 becomes h 1.
同样，访问节点 C 的时候，我们遍历其继承人 F 和 ^ h ，由一个递减的计数（使 F 1 变成 F 0 和 H 1 变成 ^ h 0 ）。
Likewise, when visiting node c, we loop over its successors f and h, decrementing their counts by one (so that f 1 becomes f 0 and h 1 becomes h 0).
中的节点 F 和 ^ h 不再有入边，所以我们重复它们输出和消除的过程他们从图中，直到所有的节点都被访问。在该示例中，访问顺序（拓扑分类是）：
The nodes f and h no longer have incoming edges, so we repeat the process of outputting them and removing them from the graph until all the nodes have been visited. In the example, the visitation order (the topological sort is):
a c f h e d i b g
如果num_heads曾经到达的状态时，有没有入边没有节点，那么就意味着有不能拓扑排序一个周期，算法退出来显示所请求的结果。
If num_heads ever arrives at a state when there are no nodes without incoming edges, then it means there is a cycle that cannot be topologically sorted and the algorithm exits to show the requested results.
这篇关于如何订购连接的列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
