强连接组件

讯享网
  可以看出，强连接分量要么是一个环，要么是几个边相邻的环，要么是两个反向平行边，要么是单独的一个点。而上图覆盖了四种情况。
  求出强连接分量后，可以做什么？首先是可以凝结Condensation。凝结是将强连接分量缩成一个点，这对于大型图简化来说是非常重要的。

Kusajaru算法

  该算法分为三步：
  1. DFS算法计算完成时间。DFS算法可以计算出每个节点的发现时间与完成时间。
  2. 计算逆图，所谓逆图，就是将边进行反向后产生的图。
  3. 在逆图上继续DFS，因为前面正向了，如果反向还能访问，那无疑是一个强连接组件。DFS以最大访问时间的节点开始，如此DFS找出所有的强连接组件。
  以上图为例子，我们先计算访问时间，下图中的括号部分表示的是发现时间与访问时间：

  然后再产生逆图：

  按结束时间从大到小遍历，产生强连通组件，先是E，发现时间戳为26：

  然后是A，发现时间戳为22：

  然后是C，发现时间戳为19：

  然后是K，发现时间戳为12：

  然后是L，发现时间戳为11：

Python实现

# _*_ coding:utf-8 _*_ class UnweightedGraph: def __init__(self, vertices, edges): self.__vertices = vertices self.__edges = edges @property def vertices(self): return self.__vertices @vertices.setter def vertices(self, value): self.__vertices = value @property def edges(self): return self.__edges @edges.setter def edges(self, value): self.__edges = value def kosajaru(self): # 第一步 DFS计算时间 time_stack = self.dfs_time_stack() # 创建逆图 reversed_edges = [None] * len(self.__edges) # 遍历原图，生成逆图 for from_vertex, neighbours in enumerate(self.__edges): for to_vertex in neighbours: if reversed_edges[to_vertex] is None: reversed_edges[to_vertex] = [] reversed_edges[to_vertex].append(from_vertex) # 打印一下逆图 reversed_graph = UnweightedGraph(self.__vertices, reversed_edges) # 对逆图进行DFS # scc的列表，是一个二维数组，里面有多个scc，每个scc是一个list return UnweightedGraph.dfs_scc(time_stack, reversed_edges) white = 0 gray = 1 black = 2 def dfs_time_stack(self): # 着色 colors = [UnweightedGraph.white for _ in self.__vertices] times = [{ 
   'd': None, 'f': None} for _ in self.__vertices] time = 1 time_stack = [] for root, _ in enumerate(self.__vertices): # 其实可以用栈代替 if not colors[root] == UnweightedGraph.white: continue # 这里的i是森林的一个根 times[root]['d'] = time time += 1 stack = [root] while len(stack) > 0: # 这一步就错了，不要直接弹出 v = stack[-1] if colors[v] == UnweightedGraph.black: stack.pop() times[v]['f'] = time time += 1 time_stack.append(v) else: colors[v] = UnweightedGraph.gray for neighbor in self.__edges[v]: if colors[neighbor] == UnweightedGraph.white: times[neighbor]['d'] = time time += 1 stack.append(neighbor) colors[neighbor] = UnweightedGraph.gray colors[v] = UnweightedGraph.black return time_stack @staticmethod def dfs_scc(time_stack, edges): # 着色 visited = [False for _ in time_stack] # d代表discover f代表finish，发现时间戳和完成时间戳 scc_list = [] for root in reversed(time_stack): # 其实可以用栈代替 if visited[root]: continue # 这里的i是森林的一个根 stack = [root] scc = [] while len(stack) > 0: v = stack.pop() if visited[v]: continue for neighbor in edges[v]: if not visited[neighbor]: stack.append(neighbor) visited[v] = True scc.append(v) scc_list.append(scc) return scc_list def to_dot(self): s = 'digraph s {\n' for v in self.__vertices: s += f'"{ 
     v}";\n' for i, e in enumerate(self.__edges): for t in e: s += f'\"{ 
     self.__vertices[i]}\"->"{ 
     self.__vertices[t]}";\n' s += '}\n' return s