• PUDN用户
    了解作者
  • Visual C++
    开发工具
  • 1KB
    文件大小
  • zip
    文件格式
  • 0
    收藏次数
  • 1 积分
    下载积分
  • 7
    下载次数
  • 2009-11-23 12:25
    上传日期
判断图的连通性。单连通,强联通和弱联通
test.zip
  • test.cpp
    1.9KB
内容介绍
//**************************************// // // // 程序编写:常后宇 // // 编写时间:2009.11.21 // // 程序内容:判断图的连通性 // // // //**************************************// #include<iostream.h> int main(void) { int T[8][8] = { {1,0,1,0,1,0,1,1}, {0,0,0,0,0,1,0,0}, {0,0,0,1,0,0,0,1}, {1,0,1,0,0,0,0,1}, {1,0,0,0,0,0,0,0}, {0,1,0,0,0,0,0,1}, {0,1,0,0,0,0,0,1}, {0,0,0,0,0,0,1,0} }; int i,j,k,m=1,n,p=1,q=1; //输出原邻接矩阵 cout<<"原邻接矩阵为:"<<endl; for(i=0;i<8;i++){ for(j=0;j<8;j++) cout<<T[i][j]<<" "; cout<<endl; } //求出对应的道路矩阵 int M[8][8]; for(i=0;i<8;i++) for(j=0;j<8;j++) M[i][j]=T[i][j]; for(j=0;j<8;j++) for(i=0;i<8;i++) { if(M[i][j]==1) for(k=0;k<8;k++) M[i][k]=(M[i][k]||M[j][k]); } cout<<"对应的道路矩阵为:"<<endl; for(i=0;i<8;i++){ for(j=0;j<8;j++) cout<<M[i][j]<<" "; cout<<endl; } for(i=0;i<8;i++) for(j=0;j<8;j++) if(i!=j) p=p*M[i][j]; if(p==1) cout<<"连通性为强联通"<<endl; for(i=0;i<8;i++) for(j=0;j<8;j++) if(i!=j){ if(M[i][j]+M[j][i]>0) q=1; else q=0; m=m*q; } if(m==1){ cout<<"连通性为单联通."<<endl; cout<<endl;} for(i=0;i<8;i++) for(j=0;j<8;j++) if(i!=j){ if(T[i][j]==1) T[j][i]=1; if(T[j][i]==1) T[i][j]=1;} cout<<"改造后的邻阶矩阵为:"<<endl; for(i=0;i<8;i++){ for(j=0;j<8;j++) cout<<T[i][j]<<" "; cout<<endl;} for(i=0;i<8;i++) for(j=0;j<8;j++) if(i!=j) n=T[i][j]; if(n==1) {cout<<"连通性为弱连通."<<endl; cout<<"多次证明单向连通图一定是弱连通图."<<endl; } else cout<<"不连通."<<endl; return 0; }
评论
    相关推荐