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のアルゴリズムはどちらもうまくいきます。 （私はあなたが他の間違いを持っ​​ているかどうかを確認しなかった）。