我們關注一下互聯(lián)網(wǎng)相關的非常巨大圖：
由主機通過網(wǎng)線（或無線）連接而形成的圖弥喉；以及由網(wǎng)頁通過超鏈接連接而形成的圖馒疹。
先看網(wǎng)頁形成的圖
以網(wǎng)頁（URI作為id）為頂點穿肄，網(wǎng)頁內(nèi)包含的超鏈接作為邊凰棉，可以轉換為一個有向圖损拢。
路德學院計算機系網(wǎng)站鏈接情況，有三個有趣的現(xiàn)象
圖中包含了許多路德學院其它系的網(wǎng)站撒犀，包含了一些愛荷華其它大學學院的網(wǎng)站，還包含了一些人文學院的網(wǎng)站
?我們可以猜想掏秩，Web的底層結構可能存在某些同類網(wǎng)站的聚集
?在圖中發(fā)現(xiàn)高度聚集節(jié)點群的算法或舞，即尋找“強連通分支Strongly Connected Components”算法
?強連通分支，定義為圖G的一個子集C蒙幻，C中的任意兩個頂點v,w之間都有路徑來回映凳，即(v,w)(w,v)都是C的路徑，而且C是具有這樣性質(zhì)的最大子集
強連通分支例子
下圖是具有3個強連通分支的9頂點有向圖
一旦找到強連通分支邮破，可以據(jù)此對圖的頂點進行分類诈豌，并對圖進行化簡。
強連通分支算法：轉置概念
在用深度優(yōu)先搜索來發(fā)現(xiàn)強連通分支之前抒和，先熟悉一個概念：Transposition轉置一個有向圖G的轉置GT矫渔，定義為將圖G的所有邊的頂點交換次序，如將(v,w)轉換為(w,v)可以觀察到圖和轉置圖在強連通分支的數(shù)量和劃分上摧莽，是相同的庙洼。
強連通分支算法：Kosaraju算法思路
?首先，對圖G調(diào)用DFS算法镊辕，為每個頂點計算“結束時間”油够； ?然后，將圖G進行轉置征懈，得到GT石咬；
?再對GT調(diào)用DFS算法，但在dfs函數(shù)中卖哎，對每個頂點的搜索循環(huán)里鬼悠，要以頂點的“結束時間”倒序的順序來搜索
?最后删性，深度優(yōu)先森林中的每一棵樹就是一個強連通分支
from DFSGraph import DFSGraph
class DFSGraphStrongConnect(DFSGraph):
def __init__(self):
super().__init__()
self.time = 0
def dfs(self):
for v in self:
v.setColor('white')
v.setPred(None)
lst = list(self.verList.values())
lst.sort(key=lambda v:-v.finishTime)
mydict = {}
for v in lst:
if v.getColor() == 'white':
mydict[v.getId()] = []
self.dfsvisit(v,mydict[v.getId()])
return mydict
def dfsvisit(self, startV,path):
path.append(startV)
startV.setColor('gray')
self.time += 1
startV.discoveryTime = self.time
for nbr in startV.getConnections():
if nbr.getColor() == 'white':
nbr.setPred(startV)
self.dfsvisit(nbr,path)
startV.setColor('black')
self.time += 1
startV.finishTime = self.time
if __name__ == '__main__':
g = DFSGraph()
g.addEdge('A','B')
g.addEdge('B', 'E')
g.addEdge('B', 'C')
g.addEdge('E', 'A')
g.addEdge('E', 'D')
g.addEdge('D', 'B')
g.addEdge('C', 'F')
g.addEdge('D', 'G')
g.addEdge('G', 'E')
g.addEdge('F', 'H')
g.addEdge('H', 'I')
g.addEdge('I', 'F')
g.dfs()
for node in g:
print(node,node.discoveryTime,node.finishTime)
gt = DFSGraphStrongConnect()
for node in g:
for nbr in node.connectedTo.keys():
gt.addEdge(nbr.getId(),node.getId())
start = gt.getVertex(nbr.getId())
start.discoveryTime = nbr.discoveryTime
start.finishTime = nbr.finishTime
end = gt.getVertex(node.getId())
end.discoveryTime = node.discoveryTime
end.finishTime = node.finishTime
print('-'*70)
for node in gt:
print(node,node.discoveryTime,node.finishTime)
print('-' * 70)
mydict = gt.dfs()
for item in mydict.items():
for node in item[1]:
print(node.getId(), end=' ')
print()
