引子

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

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


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算法