I am trying to implement Tarjan's strongly connected graph algorithm (https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm), here is my code and I am confused why vertex 4 and vertex 5 are also output as strongly connected component?
I am using a very simple diagram only have 5 nodes to test. My code is written in 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
Every single vertex is strongly connected. If it does not belong to any bigger strongly connected subgraph, then it is already strong component. So both your implementation and Tarjan's algorithm are fine. (I didn't check if you have any other mistakes).