边双连通分量 点对 双连通分量

双连通分量定义:在无向连通图中,如果删除该图的任何一个结点都不能改变该图的连通性,则该图为双连通的无向图。一个连通的无向图是双连通的,当且仅当它没有关结点。

定义:在无向连通图中,如果删除该图的任何一个结点都不能改变该图的连通性,则该图为双连通的无向图。一个连通的无向图是双连通的,当且仅当它没有关结点。

算法:

1.对图进行先深搜索,计算每一个结点v的先深标号DFN[v]。

2. 计算所有结点v的low[v]是在先深生成树上按照后根遍历的顺序进行的。因此,当访问结点v时它的每个儿子y的low[y]已经计算完毕,这时low[v]取下面三值中最小者:

(1) dfn[v];

(2) dfn[w], 凡是有回退边(v, w)的任何结点w;

(3) low[y],对v的任何儿子y.

双连通分量一个是对点的双连通分量:(即求关节点)当在某一个点v处它的儿子为y low[y] >= dfn[v]即找到了关节点。

(代码怀疑有误,双连通分量栈应该存边而不是点,容易构造出这个代码出错的情况)

void searchB(int start)

{

dfn[start] = low[start] = cnt ++;

stack[top ++] = start;

for ( int i = 0; i < i_vec&#91;start&#93;.size(); ++i )

{

if( dfn&#91;i_vec&#91;start&#93;&#91;i&#93;&#93; == -1 )

{

father&#91;i_vec&#91;start&#93;&#91;i&#93;&#93; = start;

searchB(i_vec&#91;start&#93;&#91;i&#93;);

if( low&#91;i_vec&#91;start&#93;&#91;i&#93;&#93; >= dfn&#91;start&#93; )

{

while ( true )

{

b_con&#91;b_sn&#93;.push_back(stack&#91;top-1&#93;);

point&#91;b_sn&#93;&#91;stack&#91;top-1&#93;&#93; = true;

if( stack&#91;--top&#93; == i_vec&#91;start&#93;&#91;i&#93; )

break;

}

point&#91;b_sn&#93;&#91;start&#93; = true;

b_con&#91;b_sn++&#93;.push_back(start);

}

low&#91;start&#93; = min(low&#91;start&#93;, low&#91;i_vec&#91;start&#93;&#91;i&#93;&#93;);

}

else if( i_vec&#91;start&#93;&#91;i&#93; != father&#91;start&#93; )

low&#91;start&#93; = min(low&#91;start&#93;, dfn&#91;i_vec&#91;start&#93;&#91;i&#93;&#93;);

}

}

另一个是对边的双连通分量:(即求桥)当在某一个点v处它的儿子为y low&#91;y&#93; > dfn&#91;v&#93;即为找到了桥

void searchB(int start)

{

low&#91;start&#93; = dfn&#91;start&#93; = cnt ++;

stack&#91;top++&#93; = start;

for ( int i = 0; i < e_vec&#91;start&#93;.size(); ++i )

{

if ( e_visit&#91;e_vec&#91;start&#93;&#91;i&#93;.mark&#93; )

continue;

e_visit&#91;e_vec&#91;start&#93;&#91;i&#93;.mark&#93; = true;

if( dfn&#91;e_vec&#91;start&#93;&#91;i&#93;.to&#93; == -1 )

{

searchB(e_vec&#91;start&#93;&#91;i&#93;.to);

low&#91;start&#93; = min(low&#91;start&#93;, low&#91;e_vec&#91;start&#93;&#91;i&#93;.to&#93;);

if( low&#91;e_vec&#91;start&#93;&#91;i&#93;.to&#93; > dfn&#91;start&#93; )

{

from&#91;e_sn&#93; = start;

to&#91;e_sn ++&#93; = e_vec&#91;start&#93;&#91;i&#93;.to;

while ( top > 0 && stack&#91;top - 1&#93; != e_vec&#91;start&#93;&#91;i&#93;.to )

Map&#91;stack&#91;--top&#93;&#93; = b_sn;

Map&#91;stack&#91;--top&#93;&#93; = b_sn ++;

}

}

else

low&#91;start&#93; = min(low&#91;start&#93;, dfn&#91;e_vec&#91;start&#93;&#91;i&#93;.to&#93;);

}

}

边双连通分量 点对 双连通分量
  

爱华网本文地址 » http://www.413yy.cn/a/8103220103/15078.html

更多阅读

如何建立点对点连接以及实现网络共享 点对点连接

如何建立点对点连接以及实现网络共享——简介点对点,顾名思义,即为在无足够网线、路由器或交换机的情况下,通过一台笔记本电脑建立无线网络,与多台笔记本电脑实现资源交换与局域网络共享的目的,在win7系统(xp系统应该也可)的支持下,点对点连

点对点VS点对面_王潇 王潇旻

旺财姐妹在夜幕降临时分密谋提案------------------------------------正文-------------------------------------我想中途转换过行业的人都会有此体会:无论哪个行业做到一定阶段,

Zigbee第三天——点对点通信 zigbee点对点通信原理

搞了整整一天,参考了很多大侠的学习记录,才完成这个点对点通信实验,结果却是因为我串口TXRX接错引脚了,所以串口才一直没有显示,还是自己太马虎,下面记录下我的学习过程:1、实验设备: CC2430模块两块,一个做RX模块,一个做TX模块2、实现功能:

边双全:当好女儿的良师益友

  采访·撰文/孟岩峰  “小叶子,老爸接受采访需要在版面上放你的照片,你同意吗?”边双全在采访之前就和记者表示要先征求女儿的意见,“小孩子要是不乐意就算了,她有自己的想法,需要尊重她。”直到小叶子点了头,边双全这才答应了和记

声明:《边双连通分量 点对 双连通分量》为网友天涯为客分享!如侵犯到您的合法权益请联系我们删除