只做了9个节点的,无权值,使用了n-1个=8个循环,非常麻烦。一级一级判断是否连接,连接及记录所在节点,以后不再使用,确保无回路。
验证后无回路,但只试过几种情况。
代码如下:
#include<iostream> using namespace std; int w[9][9]; int e[9][9]; void Shuru() { for(int i=0;i<9;i++) { for(int j=0;j<9;j++) {cout<<"请输入节点"<<i+1<<"与节点"<<j+1<<"是否存在连通。yes=1;no=0"<<endl; cin>>w[i][j]; } } } void Panduan() { for(int p=0;p<9;p++) {for(int q=0;q<9;q++) {e[p][q]=0;}//赋值 } int d[9]; for(int k=0;k<9;k++) {d[k]=0;} d[0]=1; //判断部分 for(int a1=0;a1<9;a1++) { if(w[0][a1]==1&&d[a1]==0) {e[0][a1]=1; e[a1][0]=1; d[a1]=a1; for(int a2=1;a2<9;a2++) { if(w[a1][a2]==1&&d[a2]==0) {e[a1][a2]=1; e[a2][a1]=1; d[a2]=a2; for(int a3=1;a3<9;a3++) { if(w[a2][a3]==1&&d[a3]==0) { e[a2][a3]=1; e[a3][a2]=1; d[a3]=a3; for(int a4=1;a4<9;a4++) { if(w[a3][a4]==1&&d[a4]==0) { e[a3][a4]=1; e[a4][a3]=1; d[a4]=a4; for(int a5=1;a5<9;a5++) { if(w[a4][a5]==1&&d[a5]==0) { e[a4][a5]=1; e[a5][a4]=1; d[a5]=a5; for(int a6=1;a6<9;a6++) { if(w[a5][a6]==1&&d[a6]==0) { e[a5][a6]=1; e[a6][a5]=1; d[a6]=a6; for(int a7=1;a7<9;a7++) { if(w[a6][a7]==1&&d[a7]==0) {e[a6][a7]=1; e[a7][a6]=1; d[a7]=a7; for(int a8=1;a8<9;a8++) { if(w[a7][a8]==1&&d[a8]==0) {e[a7][a8]=1; e[a8][a7]=1; d[a8]=a8; } } } } } } } } } } } } } } } } } void main() { Shuru(); Panduan(); for(int z=0;z<9;z++) { {for(int x=0;x<9;x++) cout<<e[z][x]<<"\t";} cout<<endl; } }
示例:
结果:
利用二维矩阵求spanning tree,布布扣,bubuko.com
原文:http://www.cnblogs.com/cife/p/3612384.html