拓扑排序（Kahn算法）troub

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（传入边的数目），并在每次从空集中移除顶点时减少计数。当count变为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))

输出：

^{pr2}$