我正在尝试实现 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