对于连通图G，若去掉某节点后图不连通。则该节点称作割点。
若去掉某条边后图不连通，则该边称作桥。
要使图G不连通，至少须要删除多少个节点或至少须要删除多少条边，需删除的最少节点数或边数称为连通图的顶连通度和边连通度，连通图的顶连通度和边连通度问题反映了连通图的连通程度。
1.计算连通图的割点
推论1：若u不是根，则u称为割点当且仅当存在u的某一个儿子节点s，从s或s的后代点到u的祖先之间不存在反向边。即是，分支节点u成为割点的充要条件是u有一个儿子s，使得low[s]>=pre[u]。 推论2：若u被选为根，则u成为割点当且仅当它有不止一个儿子点。
计算节点的low函数
计算割点的算法
无向图仅仅有树枝边T和反向边B。
若（v，w）是树枝T，且w或w的后代没有返回v的祖先。则v是割点，low[v]取v及其全部后代返回的最早祖先编号，即low[v]=min(low[v],low[w])；否则（v,w）是反向边B，low[v]取原先v及后代返回的最早祖先编号与w的先序编号中的较小者，即low[v]=min(low[v],pre[w]);
伪代码：
procedure fund_cut_point(u,v); var w:integer; {inc(time);low[v]:=time;pre[v]:=time; for (each w∈adj[v]) and (w<>u) do if pre[w]=-1 then { fund_cut_point(v,w); if low[w]>=pre[v] then 输出v是割点; low[v]:=min(low[v],low[w])} else low[v]:=min(low[v],pre[w]); } }
main{ fillchar(pre,sizeof(pre),$ff); time:=1; pre[s]:=time; low[s]:=time; for each w∈adj[s] do { if pre[w]<>-1 then fund_cut_point(s,w); inc(p);} if p>1 then 输出s是割点并退出程序; }
2.计算连通图的桥
定理：边（u,v）为桥当且仅当它不在不论什么一个简单回路中。
判别桥的方法：在DFS遍历中发现树枝边（u,v）时，若v和它的后代不存在一条连接u或其祖先的B边，即low[v]>pre[u]（注意不能取等号），或者low[v]=pre[v]，则删除（u,v）后u和v不连通，因此（u,v）为桥。
计算桥的算法
伪代码：
procedure fund_bridge(v); var w:integer; {inc(time); low[v]:=time;pre[v]:=time; for (each w∈adj[v]) and (w<>v) do {if pre[w]=-1 then {fund_bridge(w); if (low[w]=pre[w]) or (low[w]>pre[v]) then 输出（u,v）是桥; low[v]:=min(low[v],low[w]);} else low[v]:=min(low[v],pre[w]); } }
以下是两道题：
POJ 1144 NetworkPOJ 1523 SPF
详细详见：http://download.csdn.net/download/boyxiejunboy/8910999（不用积分下载哦）
转载于:https://www.cnblogs.com/bhlsheji/p/5279520.html
