根据祖先对节点进行排序

Question

我有一个问题，我想对一组节点{a, b, c, d}进行排序。对于每个节点，我都知道祖先，即那些需要在该节点之前的节点。(例如a: {b, c}意味着a需要在列表中的某个位置，但在b和c之后(。

我可以像这样迭代地解决下面的例子：

1. a: {b, c} --> b|c , a
2. b: {c} --> c , b , a
3. d: {b, c} --> c , b , d, a

有已知的算法可以解决这个问题吗？最好使用Python。

Answer 1

这看起来像是拓扑排序的作业：

import networkx as nx
edges = {'a': ['b', 'c'], 'b': ['c'], 'd': ['b', 'c']}
G = nx.DiGraph([(k, v) for k in edges for v in edges[k]])
sorted_nodes = [*reversed([*nx.topological_sort(G)])]
print (sorted_nodes)
# ['c', 'b', 'a', 'd']

没有规则规定"；a"；以及"；d"；所以这应该是一个可以接受的解决方案。

您可以使用pip安装networkx库。

Answer 2

这个问题叫做拓扑排序。你可以在这里看到伪代码。以下是python实现：

import copy
def topological_sort(outcoming_edges):
#outcoming_edges: Dict[str,Set[str]]
# example: {'a': {'b', 'c'}, 'b': {'c'}, 'd': {'b','c'}}
outcoming_edges = copy.deepcopy(outcoming_edges) #to make sure the original variable is not changed
l = []
#find outcoming_edges which has no incoming edge
s = set(outcoming_edges.keys())
for node in outcoming_edges:
for ancestor in outcoming_edges[node]:
s.discard(ancestor)
incoming_edges = dict()
for n, next_nodes in outcoming_edges.items():
for m in next_nodes:
if m in incoming_edges:
incoming_edges[m].add(n)
else:
incoming_edges[m] = {n}
while s:
n = s.pop()
l.append(n)
next_nodes = outcoming_edges.get(n,set())
while next_nodes:
m = next_nodes.pop()
incoming_edges[m].remove(n)
if not incoming_edges[m]:
s.add(m)
if any(outcoming_edges.values()) or any(incoming_edges.values()):
return None #graph has at least one cycle
else:
return l # a topologically sorted order