无向图的割点.doc

《无向图的割点.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、DFS,NUM[I]记录访问到I的时间戳,LOW[I]=MIN{NUM[I],LOW[Q]}存在I-Q的边且Q不是I的父节点然后就可以判断了，i是割点当i是根节点且它有2个以上的儿子，或者它不是根节点且low[q]>=num[q](i,q)是桥当且仅当low[q]>num[i]#include#includeconstlongmaxn=10;longnum[maxn];longlow[maxn];longcolor[maxn];longgraph[maxn][maxn];boolcut[maxn];boolbridge[maxn][maxn];lon

2、gnow;longn;longcutnum;longbridgenum;longfather[maxn];longchild[maxn];voiddfs(int);intmain(){inti,j;FILE*in=fopen("input.txt","r");FILE*out=fopen("output.txt","w");fscanf(in,"%d",&n);for(i=1;i<=n;i++)for(j=1;j<=n;j++)fscanf(in,"%d",&graph[i][j]);for(i=1;i<=n;i++)if(color[i]==0){father[i]=0;dfs(i);

3、}fprintf(out,"共有%d个割点:",cutnum);for(i=1;i<=n;i++)if(cut[i])fprintf(out,"%d",i);fprintf(out,"");fprintf(out,"共有%d个桥:",bridgenum);for(i=1;i<=n;i++)for(j=1;j

4、olor[i]=-1;for(q=1;q<=n;q++)if(graph[i][q]==1){if(color[q]==0){father[q]=i;dfs(q);child[i]++;if(low[q]>=num[i])flag=true;}if((low[q]num[i]){bridge[q][i]=true;bridge[i][q]=true;bridgenum++;}}color[i]=1;if((father[i]==0)&&(child[i]>=2)

5、

6、(father[i]!=0

7、)&&(flag)){cut[i]=true;cutnum++;}}求无向图的割点！2008-07-2022:46求割顶(割点)，主要的算法结构就是DFS，一个点是割点，当且仅当以下两种情况:(1)该节点是根节点，且有两棵以上的子树(2)该节点的子节点中的任一个，没有到该节点祖先的反向边（就是说如果没有这个割顶，那么这个子节点和那个祖先之间就不能连通）实现的时候判断第一个条件只需要记录一下子树的数目就好第二个条件稍微麻烦，要用一个ancestor存和每个节点相连点的最小深度(最高祖先的深度)，deep存当前点深度，判断时候如果ancestor[i]>=deep[father[i]]就表示

8、不存在反向边，那么i就是割点了。//lrj书上的模板vectorv[301];intc[301],D[301],a[301],cut[301],root;//c[]记录点的颜色c[i]=0:白色c[i]=1：灰色c[i]=2：黑色//D[]记录点的深度。a[]记录能达到的祖先的深度。cut[]记录割点voiddfs(intk,intf,intd){inttot,i,n=v[k].size();c[k]=1;D[k]=d;a[k]=d;tot=0;for(i=0;i

9、D[t];if(c[t]==0){dfs(t,k,d+1);tot=tot+1;a[k]=a[k]1)

10、

11、(k!=root&&a[t]>=D[k]))cut[k]=1;}}c[k]=2;另：//最佳边割集#defineMAXN100#defineinf1000000000intmax_flow(intn,intmat[][MAXN],intsource,intsink