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

Question

给定一些列表，比如 [1, 5, 6]、[2, 3, 5, 6]、[2, 5] 等等（这些列表不一定是按顺序排列的），我们希望找到一个所有元素的列表，按照某种顺序排列。这个顺序的意思是，如果在某个列表中 x 在 y 前面，那么在所有包含 x 和 y 的列表中，x 也应该在 y 前面。这样我们就能得到一个“拓扑排序”的列表。如果有很多种可能的排序方式，随便给我一个都可以。

我想知道在 Python 中实现这个的最简单方法是什么。

Answer 1

我的解决方案（使用了@unutbu的一些代码）

import collections

retval = []
data = [[1,2,3], [4,5,6], [2, 5], [3, 6], [1, 7]]
in_edges = collections.defaultdict(set)
out_edges = collections.defaultdict(set)
vertices = set()
for row in data:
    vertices |= set(row)
    while len(row) >= 2:
        w = row.pop()
        v = row[-1]
        in_edges[w].add(v)
        out_edges[v].add(w)
def process(k):
    vertices.remove(k)
    retval.append(k)
    for target in out_edges[k]:
        in_edges[target].remove(k)
    for target in out_edges[k]:
        if not in_edges[target]:
            process(target)
    out_edges[k] = set()

while vertices:  # ideally, this should be a heap
    for k in vertices:
        if not in_edges[k]:
            process(k)
            break

print(retval)

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]

Answer 3

这是@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]