《算法学习：图论之图的割点,桥,双连通分支》由会员分享，可在线阅读，更多相关《算法学习：图论之图的割点,桥,双连通分支（9页珍藏版）》请在金锄头文库上搜索。
1、图的割点、桥与双连通分支点连通度与边连通度在一个无向连通图中，如果有一个顶点集合，删除这个顶点集合，以及这个集合中所有顶点相关联的边以后，原图变成多个连通块，就称这个点集为割点集合。一个图的点连通度的定义为，最小割点集合中的顶点数。类似的，如果有一个边集合，删除这个边集合以后，原图变成多个连通块，就称这个点集为割边集合。一个图的边连通度的定义为，最小割边集合中的边数。注：以上定义的意思是，即有可能删除两个或两个以上点的时候才能形成多个连通块！双连通图、割点与桥如果一个无向连通图的点连通度大于 1，则称该图是点双连通的(point biconnected)，简称双连通或重连通。一个图有割点，当且
2、仅当这个图的点连通度为 1，则割点集合的唯一元素被称为割点(cut point)，又叫关节点(articulation point)。如果一个无向连通图的边连通度大于 1，则称该图是边双连通的(edge biconnected)，简称双连通或重连通。一个图有桥，当且仅当这个图的边连通度为 1，则割边集合的唯一元素被称为桥(bridge)，又叫关节边(articulation edge)。 可以看出，点双连通与边双连通都可以简称为双连通，它们之间是有着某种联系的，下文中提到的双连通，均既可指点双连通，又可指边双连通。双连通分支在图 G 的所有子图 G中，如果 G是双连通的，则称 G为双连通子图。
3、如果一个双连通子图 G它不是任何一个双连通子图的真子集，则 G为极大双连通子图。双连通分支(biconnected component)，或重连通分支，就是图的极大双连通子图。特殊的，点双连通分支又叫做块。求割点与桥该算法是 R.Tarjan 发明的。对图深度优先搜索，定义 DFS(u)为 u 在搜索树（以下简称为树）中被遍历到的次序号。定义 Low(u)为 u 或 u 的子树中能通过非父子边追溯到的最早的节点，即 DFS 序号最小的节点。根据定义，则有：Low(u)=MinDFS(u)DFS(v) (u,v)为后向边(返祖边) 等价于 DFS(v)#include using namespa
4、ce std;const int MAXN = 5001;vector adj;int cnt,lowMAXN,preMAXN,visitMAXN,degreeMAXN;void dfs(int u,int v)visitu=1; preu=cnt+,lowu=preu;int i,len=adju.size();for(i=0;i();while(m-)scanf(%d %d,adju.push_back(v),adjv.push_back(u);memset(visit,0,sizeof(visit);cnt=0,dfs(1,1);memset(degree,0,sizeof(degree);for(i=1;inext)j=e-t;if (!DFNj)tarjan(j);if (LOWjLOWi)LOWi=LOWj;else if (instackj & DFNjLOWi)LOWi=DFNj;if (DFNi=LOWi)Bcnt+;doj=StapStop-;instackj=false;Belongj=Bcnt;while (j!=i);void solve()int i;Stop=Bcnt=Dindex=0;memset(DFN,0,sizeof(DFN);for (i=1;i=N;i+)if (!DFNi)tarjan(i);参考资料
