【数据结构(邓俊辉)学习笔记】图04——双连通域分解

2024-06-10 08:44

本文主要是介绍【数据结构(邓俊辉)学习笔记】图04——双连通域分解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 0. 概述
  • 1 关节点与双连通域
  • 2 蛮力算法
  • 3 可行算法
  • 4 实现
  • 5 示例
  • 6 复杂度

0. 概述

学习下双连通域分解,这里略微有一点点难,这个算是DFS算法的非常非常经典的应用,解决的问题也非常非常有用。

1 关节点与双连通域

连通性很好理解,两个点在图中只要有一条路径,不管是无向的还是有向的,只要互相可达,就说他们是连通的。但有的时候会要求更严些,不仅要保证自己和某些地方的连通,还要保证某个区域不会变成独立的,另一个角度可以从关节点来理解。
在这里插入图片描述
明确下几个术语

考查无向图G。若删除顶点v后G所包含的连通域增多,则v称作切割节点(cut vertex)或关节点(articulation point)。
~  
如图C即是一个关节点——它的删除将导致连通域增加两块。反之,不含任何关节点的图称作双连通图。任一无向图都可视作由若干个极大的双连通子图组合而成,这样的每一子图都称作原图的一个双连通域(bi-connected component)。
~  
例如右上图中的无向图,可分解为右下图所示的三个双连通域。

任何一张连通的无向图都存在着若干个关键点,而且以这些关键点为界,可以将其分割为若干个双连通部分——BCC分量。

较之其它顶点,关节点更为重要。在网络系统中它们对应于网关,决定子网之间能否连通。在航空系统中,某些机场的损坏,将同时切断其它机场之间的交通。故在资源总量有限的前提下,找出关节点并重点予以保障,是提高系统整体稳定性和鲁棒性的基本策略。

那么怎么计算?给一个任意的图,如何将其分解为一个一个又一个BCC分量呢?作为查找结果的副产品——关键点,怎么得到?

2 蛮力算法

由其定义,可直接导出蛮力算法大致如下:

  1. 首先,通过BFS或DFS搜索统计出图G所含连通域的数目;
  2. 然后逐一枚举每个顶点v,暂时将其从图G中删去,并再次通过搜索统计出图G{v}所含连通域的数目。
  3. 于是,顶点v是关节点,当且仅当图G{v}包含的连通域多于图G。
    在这里插入图片描述
    这一算法需执行n趟搜索,耗时O(n(n + e)),如此低的效率无法令人满意。

3 可行算法

经DFS搜索生成的DFS树,表面上看似乎“丢失”了原图的一些信息,但实际上就某种意义而言,依然可以提供足够多的信息。

  • 先分析下根节点 情况
    在这里插入图片描述

DFS树中的叶节点,绝不可能是原图中的关节点

此类顶点的删除既不致影响DFS树的连通性,也不致影响原图的连通性。

此外,DFS树的根节点若至少拥有两个分支,则必是一个关节点。

如上图,在原无向图中,根节点R的不同分支之间不可能通过跨边相联(算法中为什么讨论cross edge?因为讨论的是有向图),R是它们之间唯一的枢纽。
~  

因此,这里也得出个结论:在无向图的DFS中是不可能有cross edge和forward edge,只有back word 回向边
~  
反之,若根节点仅有一个分支,则与叶节点同理,它也不可能是关节点。

  • 那么,又该如何甄别一般的内部节点是否为关节点呢?
    在这里插入图片描述
    考查上图中的内部节点C。若节点C的移除导致其某一棵(比如以D为根的)真子树与其真祖先(比如A)之间无法连通,则C必为关节点。反之,若C的所有真子树都能(如以E为根的子树那样)与C的某一真祖先连通,则C就不可能是关节点。

以D为根的真子树经过一系列访问后,会生成一系列tree edge和back edge,关键在于back edge。形象来说,若back edge往上指的不是那么高,准确来讲,不会高过父亲C,则C就是关键点。因为C若消失,则以D为根的真子树就会变成孤岛。

当然,在原无向图的DFS树中,C的真子树只可能通过后向边与C的真祖先连通。因此,只要在DFS搜索过程记录并更新各顶点v所能(经由后向边)连通的最高祖先(highest connected ancestor, HCA)hca[v],即可及时认定关节点,并报告对应的双连通域。

以E为根的真子树中的back edge往上指的更高,准确来讲,高过父亲C,则C就不是关键点。因为C若消失,则以E为根的真子树也会通过back edge保持连通。

因此通过遍历需要得到很重要指标 dTime 和 HCA,算法大体框架

  • 由括号引理: dTime越小的祖先,辈份越高
  • DFS过程中,一旦发现后向边(v,u) ~~~~      即取:hca(v) = min( hca(v) , dtime(u) )
  • DFS(u) 完成并返回v时 ~~~~      若有:hca(u) < dTime(v) ~~~~      即取:hca(v) = min( hca(v), hca(u) ) ~~~~      否则,即可判定:v系关节点,且 {v} + subtree(u) 即为一个BCC。
  • 那么如何实现?

4 实现

在这里插入图片描述
算法来看就是典型的DFS,这里改个名字叫BCC,这里利用闲置的fTime充当hca。

  • 看下u分别有哪些状态需要处理?
    首先看下UNDISCOVERED状态,既tree edge
    在这里插入图片描述
    在从顶点u处深入到遍历返回后之间的代码逻辑与DFS几乎一致,当遍历返回后,v的hca便已确定。故DFS搜索在顶点v的孩子u处返回之后,通过比较hca[u]与dTime[v]的大小,即可判断v是否关节点。
  1. 若hca[u] ≥ dTime[v],则说明u及其后代无法通过后向边与v的真祖先连通,故v为关节点。既然栈S存有搜索过的顶点,与该关节点相对应的双连通域内的顶点,此时都应集中存放于S顶部,故可依次弹出这些顶点。v本身必然最后弹出,作为多个连通域的联接枢纽,它应重新进栈。
  2. 反之若hca[u] < dTime[v],则意味着u可经由后向边连通至v的真祖先。果真如此,则这一性质对v同样适用,故有必要将hca[v],更新为hca[v]与hca[u]之间的更小者。

再看下DISCOVERED 和VISITED(这个状态只有有向边才有,这里可不关注,只是为了和DFS作对比)

在这里插入图片描述
当然,每遇到一条后向边(v, u),也需要及时地将hca[v],更新为hca[v]与dTime[u]之间的更小者,以保证hca[v]能够始终记录顶点v可经由后向边向上连通的最高祖先。

5 示例

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

6 复杂度

与基本的DFS搜索算法相比,这里只增加了一个规模O(n)的辅助栈,故整体空间复杂度仍为O(n + e)。时间方面,尽管同一顶点v可能多次入栈,但每一次重复入栈都对应于某一新发现的双连通域,与之对应地必有至少另一顶点出栈且不再入栈。因此,这类重复入栈操作不会超过n次,入栈操作累计不超过2n次,故算法的整体运行时间依然是O(n + e)。

这篇关于【数据结构(邓俊辉)学习笔记】图04——双连通域分解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1047687

相关文章

HarmonyOS学习(七)——UI(五)常用布局总结

自适应布局 1.1、线性布局(LinearLayout) 通过线性容器Row和Column实现线性布局。Column容器内的子组件按照垂直方向排列,Row组件中的子组件按照水平方向排列。 属性说明space通过space参数设置主轴上子组件的间距,达到各子组件在排列上的等间距效果alignItems设置子组件在交叉轴上的对齐方式,且在各类尺寸屏幕上表现一致,其中交叉轴为垂直时,取值为Vert

Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya(不是本人,claude AI)在社交媒体上分享了他在OpenAI学习到的15个Prompt撰写技巧。 以下是详细的内容: 提示精确化:在编写提示时,力求表达清晰准确。清楚地阐述任务需求和概念定义至关重要。例:不用"分析文本",而用"判断这段话的情感倾向:积极、消极还是中性"。 快速迭代:善于快速连续调整提示。熟练的提示工程师能够灵活地进行多轮优化。例:从"总结文章"到"用

【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画(下)

【课程链接】 AntV G6:深入图形与图形分组、自定义节点、节点动画(下)_哔哩哔哩_bilibili 本章十吾老师讲解了一个复杂的自定义节点中,应该怎样去计算和绘制图形,如何给一个图形制作不间断的动画,以及在鼠标事件之后产生动画。(有点难,需要好好理解) <!DOCTYPE html><html><head><meta charset="UTF-8"><title>06

学习hash总结

2014/1/29/   最近刚开始学hash,名字很陌生,但是hash的思想却很熟悉,以前早就做过此类的题,但是不知道这就是hash思想而已,说白了hash就是一个映射,往往灵活利用数组的下标来实现算法,hash的作用:1、判重;2、统计次数;

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

零基础学习Redis(10) -- zset类型命令使用

zset是有序集合,内部除了存储元素外,还会存储一个score,存储在zset中的元素会按照score的大小升序排列,不同元素的score可以重复,score相同的元素会按照元素的字典序排列。 1. zset常用命令 1.1 zadd  zadd key [NX | XX] [GT | LT]   [CH] [INCR] score member [score member ...]

【机器学习】高斯过程的基本概念和应用领域以及在python中的实例

引言 高斯过程(Gaussian Process,简称GP)是一种概率模型,用于描述一组随机变量的联合概率分布,其中任何一个有限维度的子集都具有高斯分布 文章目录 引言一、高斯过程1.1 基本定义1.1.1 随机过程1.1.2 高斯分布 1.2 高斯过程的特性1.2.1 联合高斯性1.2.2 均值函数1.2.3 协方差函数(或核函数) 1.3 核函数1.4 高斯过程回归(Gauss

【学习笔记】 陈强-机器学习-Python-Ch15 人工神经网络(1)sklearn

系列文章目录 监督学习:参数方法 【学习笔记】 陈强-机器学习-Python-Ch4 线性回归 【学习笔记】 陈强-机器学习-Python-Ch5 逻辑回归 【课后题练习】 陈强-机器学习-Python-Ch5 逻辑回归(SAheart.csv) 【学习笔记】 陈强-机器学习-Python-Ch6 多项逻辑回归 【学习笔记 及 课后题练习】 陈强-机器学习-Python-Ch7 判别分析 【学

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)

系统架构师考试学习笔记第三篇——架构设计高级知识(20)通信系统架构设计理论与实践

本章知识考点:         第20课时主要学习通信系统架构设计的理论和工作中的实践。根据新版考试大纲,本课时知识点会涉及案例分析题(25分),而在历年考试中,案例题对该部分内容的考查并不多,虽在综合知识选择题目中经常考查,但分值也不高。本课时内容侧重于对知识点的记忆和理解,按照以往的出题规律,通信系统架构设计基础知识点多来源于教材内的基础网络设备、网络架构和教材外最新时事热点技术。本课时知识