今天是《python算法教程》的第7篇讀書(shū)筆記，筆記的主要內(nèi)容是通過(guò)python的遍歷方式找出有向圖的強(qiáng)連通分量。

強(qiáng)連通分量定義

在有向圖G中，如果兩個(gè)頂點(diǎn)vi,vj間（vi>vj）有一條從vi到vj的有向路徑，同時(shí)還有一條從vj到vi的有向路徑，則稱(chēng)兩個(gè)頂點(diǎn)強(qiáng)連通(strongly connected)。有向圖的極大強(qiáng)連通子圖，稱(chēng)為強(qiáng)連通分量(strongly connected components)。
以下的有向圖就包含了三個(gè)強(qiáng)連通量A、B和C。

有向圖.JPG

代碼示例

以下將通過(guò)代碼展示求解上述有向圖的三個(gè)強(qiáng)連通分量。

#獲取翻轉(zhuǎn)所有邊的圖
def tr(G):
    #初始化翻轉(zhuǎn)邊的圖GT
    GT=dict()
    for u in G.keys():
        GT[u]=GT.get(u,set())
    #翻轉(zhuǎn)邊
    for u in G.keys():
        for v in G[u]:
            GT[v].add(u)
    return GT

#獲取按節(jié)點(diǎn)遍歷完成時(shí)間遞減排序的順序
def topoSort(G):
    res=[]
    S=set()
    #dfs遍歷圖
    def dfs(G,u):
        if u in S:
            return
        S.add(u)
        for v in G[u]:
            if v in S:
                continue
            dfs(G,v)
        res.append(u)
    #檢查是否有遺漏的節(jié)點(diǎn)
    for u in G.keys():
        dfs(G,u)
    #返回拓?fù)渑判蚝蟮墓?jié)點(diǎn)列表
    res.reverse()
    return res

#通過(guò)給定的起始節(jié)點(diǎn)，獲取單個(gè)連通量
def walk(G,s,S=None):
    if S is None:
        s=set()
    Q=[]
    P=dict()
    Q.append(s)
    P[s]=None
    while Q:
        u=Q.pop()
        for v in G[u]:
            if v in P.keys() or v in S:
                continue
            Q.append(v)
            P[v]=P.get(v,u)
    #返回強(qiáng)連通圖
    return P
    
G={
    'a':{'b','c'},
    'b':{'d','e','i'},
    'c':{'d'},
    'd':{'a','h'},
    'e':{'f'},
    'f':{'g'},
    'g':{'e','h'},
    'h':{'i'},
    'i':{'h'}
}

#記錄強(qiáng)連通分量的節(jié)點(diǎn)
seen=set()
#儲(chǔ)存強(qiáng)強(qiáng)連通分量
scc=[]
GT=tr(G)
for u in topoSort(G):
    if u in seen :
        continue
    C=walk(GT,u,seen)
    seen.update(C)
    scc.append(sorted(list(C.keys())))

print(scc)

運(yùn)行結(jié)果如下：

[['a', 'b', 'c', 'd'], ['e', 'f', 'g'], ['h', 'i']]