python - 拓扑排序(卡恩算法)的麻烦

Question

我无法在嵌套的 for 循环中思考我的代码。我在 wiki 上遵循 Kahn 的算法:Kahn's .我不明白如何测试 outgoingEdge 是否有每个 endArray 元素 (m) 的传入边。

这是我目前所拥有的:

    def topOrdering(self, graph):

    retList = []
    candidates = set()
    left = []
    right = []

    for key in graph:
        left.append(key)
        right.append(graph[key])

    flattenedRight = [val for sublist in right for val in sublist]

    for element in left:
        if element not in flattenedRight:
            #set of all nodes with no incoming edges
            candidates.add(element)

    candidates = sorted(candidates)

    while len(candidates) != 0:
        a = candidates.pop(0)
        retList.append(a)
        endArray = graph[a]

        for outGoingEdge in endArray:

            if outGoingEdge not in flattenedRight:
                candidates.append(outGoingEdge)
                #flattenedRight.remove(outGoingEdge)

            del outGoingEdge


    if not graph:
        return "the input graph is not a DAG"
    else:
        return retList

这是一张可视化我的算法的图片。图是邻接表的形式。

Answer 1

您可以存储 indegree (传入边的数量)分开并在每次从空集中删除顶点时递减计数。当计数变为 0 时，将顶点添加到空集以供稍后处理。这是示例:

def top_sort(adj_list):
    # Find number of incoming edges for each vertex
    in_degree = {}
    for x, neighbors in adj_list.items():
        in_degree.setdefault(x, 0)
        for n in neighbors:
            in_degree[n] = in_degree.get(n, 0) + 1

    # Iterate over edges to find vertices with no incoming edges
    empty = {v for v, count in in_degree.items() if count == 0}

    result = []
    while empty:
        # Take random vertex from empty set
        v = empty.pop()
        result.append(v)

        # Remove edges originating from it, if vertex not present
        # in adjacency list use empty list as neighbors
        for neighbor in adj_list.get(v, []):
            in_degree[neighbor] -= 1

            # If neighbor has no more incoming edges add it to empty set
            if in_degree[neighbor] == 0:
                empty.add(neighbor)

    if len(result) != len(in_degree):
        return None # Not DAG
    else:
        return result

ADJ_LIST = {
    1: [2],
    2: [3],
    4: [2],
    5: [3]
}

print(top_sort(ADJ_LIST))

输出:

[1, 4, 5, 2, 3]