侵权投诉
订阅
纠错
加入自媒体

数据结构之图论(续)

2020-04-27 16:48
程序猿声
关注

前言

在之前的推文中,我们了解了什么是图,以及一些图的DFS和BFS的基本操作,这一期本小编将继续为大家介绍一些关于图的基本算法,一起看下吧。

NO.1关节点和双联通域

在一个无向图G中,若将某个节点v去除之后后G所包含的连通域增多,则v称作切割节点(cut vertex或关节点(articulation point)。如果一个图不含任何关节点则称之为双连通图,最典型的就是完全图。任一无向图都可视作由若干个极大的双连 通子图组合而成,这样的每一子图都称作原图的一个双连通域(bi-connected component)。例如下图中的节点3和5就是关节点。

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

NO.2关节点算法

遇事不决先暴力,按照暴力来解决:首先,通过BFS或DFS搜索统计出图G所含连通域 的数目;然后逐一枚举每个顶点v,暂时将其从图G中删去,并再次通过搜索统计出图G{v}所含 连通域的数目。于是,顶点v是关节点,当且仅当图G{v}包含的连通域多于图G。这一算法需执行n趟搜索,耗时O(n(n + e)),等它算出来黄花菜都凉了。

那我们先分析下,首先在DFS树上面,叶节点不可能是关节点,因为将叶节点删去后不会影响树的连通性。另外,如果根节点有两个及两个以上的分支,则根节点一定是关节点,因为DFS会将此节点以下的所有点加入到分支中,如果有多个分支则这些分支是不相互连通的。

现在考虑内部节点。若节点C的移除导致其某一棵(比如以D为根的)真子树与其真祖先(比如A)之间无法连通,则C必为关节点。反之,若C的所有真子树都能(如以E为根的子 树那样)与C的某一真祖先连通,则C就不可能是关节点。那么只要 在DFS搜索过程记录并更新各顶点v所能(经由后向边)连通的最高祖先(highest connected ancestor, HCA)hca[v],即可及时认定关节点,并报告对应的双连通域。

思路出来了,那就是代码实现了

#include

1  2  3  下一页>  
声明: 本文由入驻维科号的作者撰写,观点仅代表作者本人,不代表OFweek立场。如有侵权或其他问题,请联系举报。

发表评论

0条评论,0人参与

请输入评论内容...

请输入评论/评论长度6~500个字

您提交的评论过于频繁,请输入验证码继续

暂无评论

暂无评论

文章纠错
x
*文字标题:
*纠错内容:
联系邮箱:
*验 证 码:

粤公网安备 44030502002758号