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

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

强连通分量定义

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

有向图.JPG

代码示例

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

#获取翻转所有边的图
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)

运行结果如下:

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏软件开发 -- 分享 互助 成长

图的遍历算法

前言:学习图的遍历算法之前,需要先了解一下图的存储方式(这里只以无向图作为讨论了)。 (1)邻接矩阵 ? (2)邻接表 ? 一、DFS(深度优先遍历)  设置一...

2037
来自专栏calmound

强连通专题

求割点(无向边): 所谓的割点,就是删除某个点,图便不连通了。  POJ  1523 #include<stdio.h> #include<string.h> ...

3618
来自专栏深度学习之tensorflow实战篇

igraph软件包创建图和网络(创建邻接矩阵)

一、igraph软件包创建图和网络 igraph 是一个独立的库,底层是 C,上层有 Python 和 R 接口,主要做图和网络方面的计算,附带绘图功能。 ...

5704
来自专栏xingoo, 一个梦想做发明家的程序员

剑指OFFER之跳台阶(九度OJ1388)

题目描述: 一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。 输入: 输入可能包含多个测试样例,对于每个测试案例, 输...

1899
来自专栏技术碎碎念

LeetCode-70-Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top. Each time y...

35712
来自专栏决胜机器学习

PHP数据结构(十) ——有向无环图与拓扑算法

PHP数据结构(十)——有向无环图与拓扑算法 (原创内容,转载请注明来源,谢谢) 一、有向无环图概念 有向无环图又称为DAG图。与其对应的还有有向树、有环图。...

53911
来自专栏数据结构与算法

洛谷P2860 [USACO06JAN]冗余路径Redundant Paths(tarjan求边双联通分量)

题目描述 In order to get from one of the F (1 <= F <= 5,000) grazing fields (which a...

42810
来自专栏Code_iOS

OpenGL ES 2.0 (iOS)[03]:熟练图元绘制,玩转二维图形

文章的大前提是,你得有《OpenGL ES 2.0 (iOS): 一步从一个小三角开始》的基础知识。

1981
来自专栏编程

数控宏程序的编程及应用

1. 什么场合会用到宏程序编程? 其实说起来宏就是用公式来加工零件,比如说椭圆,如果没有宏的话,我们要逐点算出曲线上的点,然后慢慢来用直线逼近,如果是个光洁度要...

1998
来自专栏落影的专栏

iOS开发-OpenGL ES入门教程1

前言 这里是一篇新手教程,环境是Xcode7+OpenGL ES 2.0,目标写一个OpenGL ES的hello world。 OpenGL ES系列教程在...

3309

扫码关注云+社区

领取腾讯云代金券