前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >《python算法教程》Day7 - 获取有向图的所有强连通分量强连通分量定义代码示例

《python算法教程》Day7 - 获取有向图的所有强连通分量强连通分量定义代码示例

作者头像
billyang916
发布2018-05-02 10:27:57
2K0
发布2018-05-02 10:27:57
举报
文章被收录于专栏:python读书笔记

今天是《python算法教程》的第7篇读书笔记,笔记的主要内容是通过python的遍历方式找出有向图的强连通分量。

强连通分量定义

在有向图G中,如果两个顶点vi,vj间(vi>vj)有一条从vi到vj的有向路径,同时还有一条从vj到vi的有向路径,则称两个顶点强连通(strongly connected)。有向图的极大强连通子图,称为强连通分量(strongly connected components)。 以下的有向图就包含了三个强连通量A、B和C。

有向图.JPG

代码示例

以下将通过代码展示求解上述有向图的三个强连通分量。

代码语言:javascript
复制
#获取翻转所有边的图
def tr(G):
    #初始化翻转边的图GT
    GT=dict()
    for u in G.keys():
        GT[u]=GT.get(u,set())
    #翻转边
    for u in G.keys():
        for v in G[u]:
            GT[v].add(u)
    return GT

#获取按节点遍历完成时间递减排序的顺序
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)
    #检查是否有遗漏的节点
    for u in G.keys():
        dfs(G,u)
    #返回拓扑排序后的节点列表
    res.reverse()
    return res

#通过给定的起始节点,获取单个连通量
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)
    #返回强连通图
    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'}
}

#记录强连通分量的节点
seen=set()
#储存强强连通分量
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)

运行结果如下:

代码语言:javascript
复制
[['a', 'b', 'c', 'd'], ['e', 'f', 'g'], ['h', 'i']]
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2018.04.18 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 强连通分量定义
  • 代码示例
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档