python - Tarjan 的强连通组件错误还是我的代码错误？

Question

我正在尝试实现 Tarjan 的强连通图算法 ( https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm )，这是我的代码，我很困惑为什么顶点 4 和顶点 5 也被输出作为强连通分量？

我使用的是一个非常简单的图表，只有 5 个节点要测试。我的代码是用 Python 2.7 编写的。

from collections import defaultdict
class SccGraph:
    def __init__(self, vertex_size):
        self.out_neighbour = defaultdict(list)
        self.vertex = set()
        self.visited = set()
        self.index = defaultdict(int)
        self.low_index = defaultdict(int)
        self.global_index = 0
        self.visit_stack = []
        self.scc = []
    def add_edge(self, from_node, to_node):
        self.vertex.add(from_node)
        self.vertex.add(to_node)
        self.out_neighbour[from_node].append(to_node)
    def dfs_graph(self):
        for v in self.vertex:
            if v not in self.visited:
                self.dfs_node(v)
    def dfs_node(self, v):
        # for safe protection
        if v in self.visited:
            return
        self.index[v] = self.global_index
        self.low_index[v] = self.global_index
        self.global_index += 1
        self.visit_stack.append(v)
        self.visited.add(v)
        for n in self.out_neighbour[v]:
            if n not in self.visited:
                self.dfs_node(n)
                self.low_index[v] = min(self.low_index[v], self.low_index[n])
            elif n in self.visit_stack:
                self.low_index[v] = min(self.low_index[v], self.index[n])
        result = []
        if self.low_index[v] == self.index[v]:
            w = self.visit_stack.pop(-1)
            while w != v:
                result.append(w)
                w = self.visit_stack.pop(-1)
            result.append(v)
            self.scc.append(result)

if __name__ == "__main__":
    g = SccGraph(5)
    # setup a graph 1->2->3 and 3 -> 1 which forms a scc
    # setup another two edges 3->4 and 4->5
    g.add_edge(1,2)
    g.add_edge(2,3)
    g.add_edge(3,1)
    g.add_edge(3,4)
    g.add_edge(4,5)
    g.dfs_graph()
    print g.scc

Answer 1

每个单独的顶点都是强连通的。如果它不属于任何更大的强连通子图，那么它就已经是强分量了。所以你的实现和 Tarjan 的算法都很好。 (我没有检查你是否有其他错误)。