根据祖先对节点进行排序

Question

我有一个问题，我想对一组节点 {a, b, c, d} 进行排序。对于每个节点，我知道祖先，即那些需要在该节点之前出现的节点。（例如 a: {b, c} 表示 a 需要在列表中的某处，但在 b 和 c 之后）。

我可以像这样迭代地解决以下示例：

a: {b, c} --> b|c , a
b: {c} --> c , b , a
d: {b, c} --> c , b , d, a

是否有已知的算法来解决这个问题？最好在 Python.

Answer 1

这看起来像是 topological sort 的工作：

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

这道题叫做拓扑排序。可以看到伪代码here。这是 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

根据祖先对节点进行排序

Sort nodes based on ancestors

python

sorting

topological-sort