使用指示边的列表进行Python拓扑排序

Question

给定列表:[1,5,6],[2,3,5,6],[2,5]等(不一定按任何排序顺序),如果x在一个列表中先于y,则x在y之前在每个有x和y的列表中,我想找到拓扑排序的所有元素的列表(如果x在任何其他列表中的y前面,则x在此列表中的y前面.)可能有很多解决方案,在这种情况下我想要任何一位.

在Python中实现这一点的最简单方法是什么.

Answer 1

这是@ unutbu的networkx解决方案的一个稍微简单的版本:

import networkx as nx
data=[[1, 5, 6], [2, 3, 5, 6], [2, 5], [7]]
G = nx.DiGraph()
for path in data:
    G.add_nodes_from(path)
    G.add_path(path)
ts=nx.topological_sort(G)
print(ts)
# [7, 2, 3, 1, 5, 6]

Answer 2

使用networkx,特别是networkx.topological_sort:

import networkx as nx

data=[[1, 5, 6], [2, 3, 5, 6], [2, 5], [7]]
G=nx.DiGraph()
for row in data:
    if len(row)==1:
        G.add_node(row[0])
    else:
        for v,w in (row[i:i+2] for i in xrange(0, len(row)-1)):
            G.add_edge(v,w)


ts=nx.topological_sort(G)
print(ts)
# [2, 3, 1, 5, 6]