拓扑排序未按预期运行

Question

这是我在 Python 中的图表实现。这是一个有向图。

class DiGraph:
    def __init__(self):
        self.all_vertices = []
        self.vertex_map = {}
        self.size = 0

    def add(self, a, b):

        if a in self.vertex_map:
            av = self.vertex_map[a]
            if b in self.vertex_map:
                bv = self.vertex_map[b]
                av.add(bv)
            else:
                bv = Vertex(b)
                av.add(bv)
                self.vertex_map[b] = bv
                self.all_vertices.append(bv)
                self.size += 1
        else:
            av = Vertex(a)
            self.size += 1
            if b in self.vertex_map:
                bv = self.vertex_map[b]
                av.add(bv)
            else:
                bv = Vertex(b)
                av.add(bv)
                self.vertex_map[b] = bv
                self.all_vertices.append(bv)
                self.size += 1
            self.vertex_map[a] = av
            self.all_vertices.append(av)

    def __sizeof__(self):
        return self.size

    def print(self):
        for v in self.all_vertices:
            print(v.data, end='->')
            for n in v.neighbors:
                print(n.data, end=', ')
            print()


class Vertex:
    def __init__(self, data):
        self.data = data
        self.neighbors = []
        self.connections = 0

    def add(self, item):
        self.neighbors.append(item)
        self.connections += 1

这是我的拓扑排序代码

def top_sort(g):
    stack = []
    visited = set()

    for v in g.all_vertices:
        if v not in visited:
            top_sort_util(v, visited, stack)

    for ele in stack:
        print(ele, end=' ')
    print()


def top_sort_util(v, visited, stack):
    visited.add(v)
    for n in v.neighbors:
        if n in visited:
            continue
        top_sort_util(n, visited, stack)
    stack.append(n)

这是调用方图。

def main():
    graph = DiGraph()
    graph.add(1, 2)
    graph.add(1, 3)
    graph.add(3, 4)
    graph.add(3, 5)
    graph.add(2, 6)
    graph.add(2, 7)
    graph.add(2, 8)

    top_sort(graph)


if __name__ == '__main__':
    main()

这是我收到的错误消息，

stack.append(n)
UnboundLocalError: local variable 'n' referenced before assignment

在调试代码时，我可以看到在行 stack.append(n) 上没有附加任何内容，尽管递归结束，但调用堆栈不会进入遍历内部邻居的下一次迭代top_sort_util。似乎无法理解这里逻辑上不正确的地方。任何帮助表示赞赏。

Answer 1

如果 v.neighbors 为空，则永远不会设置 n，因此 stack.append(n) outside for n in v.neighbors: 失败。

如果必须将所有 n 添加到堆栈（而不仅仅是最后一个），请适当缩进 stack.append() 以使其位于循环内：

def top_sort_util(v, visited, stack):
    visited.add(v)
    for n in v.neighbors:
        if n in visited:
            continue
        top_sort_util(n, visited, stack)
        stack.append(n)

拓扑排序未按预期运行

Topological Sort not behaving as expected

python

graph

topological-sort