7.7图的应用：强连通分支

我们关注一下互联网相关的非常巨大图：
由主机通过网线（或无线）连接而形成的图；以及由网页通过超链接连接而形成的图。

image.png

先看网页形成的图
以网页（URI作为id）为顶点，网页内包含的超链接作为边，可以转换为一个有向图。

路德学院计算机系网站链接情况，有三个有趣的现象
图中包含了许多路德学院其它系的网站，包含了一些爱荷华其它大学学院的网站，还包含了一些人文学院的网站

❖我们可以猜想，Web的底层结构可能存在某些同类网站的聚集
❖在图中发现高度聚集节点群的算法，即寻找“强连通分支Strongly Connected Components”算法
❖强连通分支，定义为图G的一个子集C，C中的任意两个顶点v,w之间都有路径来回，即(v,w)(w,v)都是C的路径，而且C是具有这样性质的最大子集

强连通分支例子
下图是具有3个强连通分支的9顶点有向图
一旦找到强连通分支，可以据此对图的顶点进行分类，并对图进行化简。

image.png
image.png

强连通分支算法：转置概念
在用深度优先搜索来发现强连通分支之前，先熟悉一个概念：Transposition转置一个有向图G的转置GT，定义为将图G的所有边的顶点交换次序，如将(v,w)转换为(w,v)可以观察到图和转置图在强连通分支的数量和划分上，是相同的。
强连通分支算法：Kosaraju算法思路
❖首先，对图G调用DFS算法，为每个顶点计算“结束时间”； ❖然后，将图G进行转置，得到GT；
❖再对GT调用DFS算法，但在dfs函数中，对每个顶点的搜索循环里，要以顶点的“结束时间”倒序的顺序来搜索
❖最后，深度优先森林中的每一棵树就是一个强连通分支

第一趟DFS
转置后第二趟DFS
结果

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()