引子

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

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


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个节点是在同一个连通分量了

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

参考资料