边连通度

第1页共8页一、实验目的：给定一个图(有向或无向)，求它的边连通度。二、实验内容：1)题目：求5阶完全图的边连通度。2)C语言代码：#includestdio.h#definem-1#definen5/*已知图的点数*/voidmain(){intf[n+1][n+1],content[n+1][n+1],b1[n+1][n+1];/*f表示流量，conten表示弧上的容量，b1表示单位费用*/intkg[n+1][n+1];/*保存任意两点间最大的内部边不交的路的条数*/intc[n+1][n+1]={0};/*最小费用最大流中的w(f)*/intd[n+1]={0};/*存放权*/ints[2*n+2]={0},s2[2*n+2]={0},s1[2*n+2]={0},r1;inti,j,k,p,l,flag,a,u,cta,flag1,flag2,p1;intb,t;/*b,t分别代表路的起点和终点的角标*/for(i=0;i=n;i++){for(j=0;j=n;j++){kg[i][j]=0;}}for(b=1;b=n;b++){for(t=b+1;t=n;t++){for(i=0;i=n;i++){for(j=0;j=n;j++){f[i][j]=m;content[i][j]=m;b1[i][j]=m;}第2页共8页}for(i=1;i=2*n;i++){s[i]=0;s2[i]=0;}for(i=1;in+1;i++)d[i]=0;for(i=1;i=n;i++){for(j=1;j=n;j++){if(i!=j){content[i][j]=1;b1[i][j]=1;f[i][j]=1;/*利用已知图构造网络*/}}}do{for(i=1;i=n;i++){for(j=1;j=n;j++){if(content[i][j]==1&&ij){if(f[i][j]content[i][j])c[i][j]=b1[i][j];if(f[i][j]==content[i][j])c[i][j]=m;if(f[i][j]0)c[j][i]=m;if(f[i][j]==0)c[j][i]=m;}第3页共8页if(content[i][j]==1&&ij){if(f[i][j]content[i][j])c[i][j]=b1[i][j];if(f[i][j]==content[i][j]){if(c[i][j]!=b1[i][j])c[i][j]=m;if(c[i][j]==b1[i][j])c[i][j]=b1[i][j];}if(f[i][j]0||f[i][j]==0){if(c[j][i]!=b1[j][i])c[j][i]=m;if(c[j][i]==b1[j][i])c[j][i]=b1[j][i];}}}}/*利用当前流构造图w(f)*/for(i=1;in+1;i++)c[i][b]=m;p=0;for(i=1;i=2*n;i++){s[i]=0;s2[i]=0;}for(i=1;in+1;i++)d[i]=0;s[1]=b;do{p=p+1;第4页共8页a=100;k=0;l=0;for(i=1;s[i]!=0;i=i+1){for(j=1;j=n;j++){if(c[s[i]][j]0&&d[s[i]]+c[s[i]][j]a&&j!=s[i]){a=c[s[i]][j]+d[s[i]];k=s[i];l=j;}}}flag=0;d[l]=a;for(i=1;i2*n+2;i++){if(s[i]!=0&&s[i+1]==0){if(i==1){s[i]=k;s[i+1]=l;i=2*n+2;}else{s[i+1]=k;s[i+2]=l;i=2*n+2;}}}for(i=1;in+1;i++)c[i][l]=m;c[k][l]=m;c[l][k]=m;for(i=1;s[i]!=0;i++){第5页共8页if(s[i]==t){flag=1;break;}}}while(flag==0&&p=n+1);flag1=0;if(pn+1){flag1=1;/*此时图不存在从Vb到Vt的最短路*/}if(flag1==0)/*此时存在从Vb到Vt的最短路*/{r1=1;for(i=2*n-1;i=1;i--){if(s[i]0)s1[r1++]=s[i];}for(i=1;s[i]!=0;i++)s[i]=0;for(i=1;s1[i]!=0;i++)s[i]=s1[i];u=1;for(i=1;s[i]0;){j=i;p=0;do{p++;flag2=0;if(s[j+2]0&&s[i+1]==s[j+2]){第6页共8页s2[u]=s[i];s2[u+1]=s[i+1];u=u+2;flag2=1;j=j+2;}elseif(u2&&s2[u-1]==s[i]&&s[i+1]==b){s2[u]=s[i];s2[u+1]=s[i+1];flag2=1;j=2*n+2;}elsej=j+2;}while(flag2==0&&pn+1);i=j;}}for(i=1;i2*n+2;i++)s[i]=0;r1=1;for(i=2*n+2-1;i=1;i--){if(s2[i]0)s[r1++]=s2[i];}for(i=1;s[i]!=0;i++)s2[i]=s[i];cta=100;for(i=1;s2[i]!=0;i=i+2){if(content[s2[i]][s2[i+1]]-f[s2[i]][s2[i+1]]cta)cta=content[s2[i]][s2[i+1]]-f[s2[i]][s2[i+1]];}if(cta0){for(i=1;s2[i]!=0;i=i+2){f[s2[i]][s2[i+1]]=f[s2[i]][s2[i+1]]+cta;第7页共8页}}}while(flag1==0);/*即一直存在最短路*/p1=0;for(i=1;i=n;i++){if(content[b][i]==1&&f[b][i]=0)p1=p1+f[b][i];}kg[b][t]=p1;}}cta=100;for(i=1;i=n;i++){for(j=i+1;j=n;j++){if(kg[i][j]0&&kg[i][j]cta)cta=kg[i][j];}}printf(Theedgeconnectivityofthegraphis%d\n,cta);printf(\n);getchar();}3)运行结果：第8页共8页三、使用环境四、调试过程五、总结