欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

强连通分量

程序员文章站 2022-07-12 18:22:42
...

如果有向图的任何一对结点间是相互可达的,则称这个有向图是强连通的。

强连通分量


def tr(G):
    GT={}
    for u in G:GT[u]=set()
    for u in G:
        for v in G[u]:
            GT[v].add(u)
    return GT
def scc(G):
    GT=tr(G)
    sccs,seen=[],set()
    for u in dfs_topsort(G):
        if u in seen:continue
        C=walk(GT,u,seen)
        seen.update(C)
        sccs.append(C)
    return sccs

def dfs_topsort(G):
    S,res=set(),[]
    def recurse(u):
        if u in S:return
        S.add(u)
        for v in G[u]:
            recurse(v)
        res.append(u)
    for u in G:
        recurse(u)
    res.reverse()
    return res

def walk(G,s,S=set()):
    P,Q=dict(),set()
    P[s]=None
    Q.add(s)
    while Q:
        u=Q.pop()
        print("u: ",u)
        print("S:",S)
        for v in G[u].difference(P,S):
            Q.add(v)
            P[v]=u
    return P
        

if __name__=="__main__":
    a, b, c, d, e, f, g, h, i= range(9)

    G={  
        'a':set('bc'),  
        'b':set('edi'),  
        'c':set('d'),  
        'd':set('ah'),  
        'e':set('f'),  
        'f':set('g'),
        'g':set('eh'),
        'h':set('i'),
        'i':set('h')
        }
    sccs=scc(G)

运行:

>>> sccs
[{'a': None, 'd': 'a', 'c': 'd', 'b': 'd'}, {'e': None, 'g': 'e', 'f': 'g'}, {'h': None, 'i': 'h'}]