引子

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

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


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