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의 알고리즘은 모두 훌륭합니다. (나는 다른 실수가 있는지 확인하지 않았다.)