Learning Strongly Connected Component Algorithms

引子

图论看到有向图的强连通分量部分，感觉非常有用，前面的无向图连通分量，还不知道应用在什么地方，现在来看看寻找强连通分量的算法有什么应用。

社交应用上，我们能记录每个人的聊天记录，最明显的是，我们能知道谁跟谁发过消息，比如:


chats = [
    ('Hank', 'Nick'),
    ('Nick', 'Hank'),
    ('Nick', 'Jamie'),
    ('Jamie', 'Swen'),
    ('Jamie', 'Hank'),
    ('Swen', 'Hank'),
    ('Swen', 'Nick'),
    ('Ada', 'Jamie'),
    ('Ada', 'Hank'),
    ('Micy', 'Hank'),
    ('Ada', 'Vivi'),
    ('Ada', 'Micy'),
    ('Vivi', 'Micy'),
    ('Vivi', 'White'),
    ('Micy', 'Suli'),
    ('Suli', 'Mia'),
    ('Suli', 'Ada'),
    ('Mia', 'Ada'),
    ('Hank', 'White'),
    ('White', 'Rowland'),
    ('Rowland', 'Orange'),
    ('Orange', 'White'),
    ('Orange', 'Rowland'),
    ('Orange', 'Hank')
]

第一行表示Hank给Nick发过消息。

根据谁跟谁发过消息我们就能构造一幅有向图了。

import networkx as nx
import numpy as np
import matplotlib.pyplot as plt
%matplotlib notebook

chats = [
    ('Hank', 'Nick'),
    ('Nick', 'Hank'),
    ('Nick', 'Jamie'),
    ('Jamie', 'Swen'),
    ('Jamie', 'Hank'),
    ('Swen', 'Hank'),
    ('Swen', 'Nick'),
    ('Ada', 'Jamie'),
    ('Ada', 'Hank'),
    ('Micy', 'Hank'),
    ('Ada', 'Vivi'),
    ('Ada', 'Micy'),
    ('Vivi', 'Micy'),
    ('Vivi', 'White'),
    ('Micy', 'Suli'),
    ('Suli', 'Mia'),
    ('Suli', 'Ada'),
    ('Mia', 'Ada'),
    ('Hank', 'White'),
    ('White', 'Rowland'),
    ('Rowland', 'Orange'),
    ('Orange', 'White'),
    ('Orange', 'Rowland'),
    ('Orange', 'Hank')
]

G = nx.DiGraph()
G.add_edges_from(chats)

pos = nx.shell_layout(G)
nx.draw_networkx(G, pos, node_size=500, alpha=0.6, arrowsize=10, arrowstyle='->')

<IPython.core.display.Javascript object>

现在，我们有个需求，想要知道所有人中，都有哪几伙人。一般情况下，人总是抱团的，我们现在就是要找出来一个一个圈子。

面向这种需求，抽象出来，其实就是寻找强连通分量，一个强连通分量就是一个圈子。

强连通分量算法，历史上有很多种，现在我一个一个来学习。

Kosaraju算法

这个算法实现不难，但是很难理解，我研究了整整一天才真正想明白它为什么是对的。

要理解这个算法，有几个概念需要理解清楚:

两点A, B在一个强连通分量里面，那么A一定有一条路径可以走到B，B也一定有一条路径走到A
一个有向图的反向图，就是将该图的所有边的箭头反过来得到的图

Koasaraju算法的步骤是这样的:

对原图G的反向图GR做深度优先逆后序搜索，记下来搜索的路径
根据这个路径做一次深度优先搜索，将可达的2个点归为一个连通分量中

先写代码构建一幅反图，看一下长什么样:

reverse_chats = [(chat[1], chat[0]) for chat in chats]

G = nx.DiGraph()
G.add_edges_from(reverse_chats)

pos = nx.shell_layout(G)
nx.draw_networkx(G, pos, node_size=500, alpha=0.6, arrowsize=10, arrowstyle='->')

现在，对反向图做一次逆后序遍历，得到的结果就是反向图的伪拓扑排序。这里说它是伪，是因为拓扑排序是要求图是无环的，而伪拓扑排序出来的结果是有环的情况下，依旧保持节点的依赖关系，没有任何依赖的节点排在最前面。

然后再按照伪拓扑排序的顺序，对原图做一次深度优先搜索，将同一个连通分量的节点放到一起。

from collections import deque

class DiGraph:
    def __init__(self, rules):
        # 邻接表
        self.adjacent = {}
        # 是否访问过
        self.marked = {}
        # 强连通分量列表
        self.strongly_connected_components = []
        
        for rule in rules:
            self.marked[rule[0]] = False
            self.marked[rule[1]] = False
            if rule[0] not in self.adjacent:
                self.adjacent[rule[0]] = []
            self.adjacent[rule[0]].append(rule[1])
    def get_reverse_post_order(self):
        """
        返回图的逆后序遍历结果
        """
        result = deque([])
        for node in self.adjacent:
            if not self.marked[node]:
                self.dfs_topological(node, result)
        return result
    
    def dfs_topological(self, node, result):
        self.marked[node] = True
        for neighbor in self.adjacent[node]:
            if not self.marked[neighbor]:
                self.dfs_topological(neighbor, result)
        result.appendleft(node)
        
    def get_strongly_connected_components(self, nodes):
        """
        找到图的强连通分量
        """
        count = 0
        for node in nodes:
            if not self.marked[node]:
                self.dfs(node, count)
                count += 1
            
    def dfs(self, node, count):
        if len(self.strongly_connected_components) <= count:
            self.strongly_connected_components.append([])
        self.strongly_connected_components[count].append(node)
        self.marked[node] = True
        
        for neighbor in self.adjacent[node]:
            if not self.marked[neighbor]:
                self.dfs(neighbor, count)
       
# 原图
graph = DiGraph(chats)
# 反向图
reverse_chats = [(chat[1], chat[0]) for chat in chats]
reverse_graph = DiGraph(reverse_chats)
# 得到伪拓扑排序
reverse_post_order = reverse_graph.get_reverse_post_order()
print('reverse_post_order: ', reverse_post_order)

graph.get_strongly_connected_components(reverse_post_order)
# 把结果打印出来
for i in range(0, len(graph.strongly_connected_components)):
    for item in graph.strongly_connected_components[i]:
        print(item, end=', ')
    print('')

reverse_post_order:  deque(['Nick', 'Hank', 'Orange', 'Rowland', 'White', 'Swen', 'Jamie', 'Ada', 'Mia', 'Suli', 'Micy', 'Vivi'])
Nick, Hank, White, Rowland, Orange, Jamie, Swen, 
Ada, Vivi, Micy, Suli, Mia,

看上面的结果，成功的找到了原图的2个强连通分量，可以看到，第一伙人是技术，第二伙人是财务，非常精准！

现在问题来了，凭什么先求反向图的逆后序遍历顺序，然后根据这个顺序深度优先搜索，就能得到强连通分量呢？我研究一天想明白的原理是这样的:

从强连通分量的概念里面可以得到，两个节点在同一个连通分量里面，比如Orange和White，说明Orange可以有路径到达White, White也有路径到达Orange
我们从反向图的伪拓扑排序结果看到，Orange是排在White前面的，说明Orange有路径到达White
如果我们从原图的White出发，深度搜索一次，能到达Orange(看了原图，我得找到了White->Rowland->Orange)的路径，那就说明White是有路径到达Orange的
两个结合起来，就说明这2个节点是在同一个连通分量了

整个算法的原理就是这样么简单!!

参考资料

理解强连通分量Kosaraju算法的正确性

文章目录

引子

Kosaraju算法

参考资料