zuixiaoshengchengshu.rar_最小生成树c++

#include <iostream> #include "header.h" using namespace std; int main() { int dotnum,pathnum,i,j,x,mark=0,length=0,O; int square[10][10]={0}; int start,over; pic *M[10],*save[10]; cout<<"请输入节点数:"; cin>>dotnum; cout<<"请输入弧数:"; cin>>pathnum; for(i=0;i<dotnum;i++) { M[i]=(pic *)malloc(sizeof(pic)); M[i]->path1=NULL; M[i]->path2=NULL; M[i]->path3=NULL; M[i]->rpath1=NULL; M[i]->rpath2=NULL; M[i]->rpath3=NULL; M[i]->judge=0; M[i]->num=i; cout<<"请输入第"<<i<<"个节点的内容："; cin>>M[i]->data; } for(i=0;i<pathnum;i++) { cout<<"请输入弧"<<i<<"的一端结点编号:"; cin>>start; cout<<"请输入弧"<<i<<"的另一端结点编号:"; cin>>over; cout<<"请输入弧"<<i<<"的权值："; cin>>square[start][over]; //square[over][start]=square[start][over]; } for(i=0;i<10;i++) { for(j=0;j<10;j++) { if(square[i][j]!=0) { if(M[i]->path1==NULL) { M[i]->path1=M[j]; M[j]->rpath1=M[i]; goto LOOP;//如果成功则跳到if判断的最后 } else if(M[i]->path2==NULL) { M[i]->path2=M[j]; M[j]->rpath2=M[i]; goto LOOP;//如果成功则跳到if判断的最后 } else if(M[i]->path3==NULL) { M[i]->path3=M[j]; M[j]->rpath3=M[i]; goto LOOP;//如果成功则跳到if判断的最后 } else { cout<<"错误！"; return 0; } LOOP:;//跳到此处 } } } for(i=0;i<10;i++) { for(j=0;j<10;j++) { if(square[i][j]!=0) { square[j][i]=square[i][j]; } } } save[0]=M[0]; mark++; save[0]->judge=1; for(;;) { x=9999; for(i=0;i<mark;i++) { if(save[i]->path1!=NULL&&save[i]->path1->judge!=1) { if(x>square[save[i]->num][save[i]->path1->num]) { x=square[save[i]->num][save[i]->path1->num]; } } if(save[i]->path2!=NULL&&save[i]->path2->judge!=1) { if(x>square[save[i]->num][save[i]->path2->num]) { x=square[save[i]->num][save[i]->path2->num]; } } if(save[i]->path3!=NULL&&save[i]->path3->judge!=1) { if(x>square[save[i]->num][save[i]->path3->num]) { x=square[save[i]->num][save[i]->path3->num]; } } if(save[i]->rpath1!=NULL&&save[i]->rpath1->judge!=1) { if(x>square[save[i]->num][save[i]->rpath1->num]) { x=square[save[i]->num][save[i]->rpath1->num]; } } if(save[i]->rpath2!=NULL&&save[i]->rpath2->judge!=1) { if(x>square[save[i]->num][save[i]->rpath2->num]) { x=square[save[i]->num][save[i]->rpath2->num]; } } if(save[i]->rpath3!=NULL&&save[i]->rpath3->judge!=1) { if(x>square[save[i]->num][save[i]->rpath3->num]) { x=square[save[i]->num][save[i]->rpath3->num]; } } } for(i=0;i<mark;i++) { if(save[i]->path1!=NULL&&save[i]->path1->judge!=1) { if(x==square[save[i]->num][save[i]->path1->num]) { save[mark]=save[i]->path1; save[mark]->judge=1; mark++; length=length+x; break; } } if(save[i]->path2!=NULL&&save[i]->path2->judge!=1) { if(x==square[save[i]->num][save[i]->path2->num]) { save[mark]=save[i]->path2; save[mark]->judge=1; mark++; length=length+x; break; } } if(save[i]->path3!=NULL&&save[i]->path3->judge!=1) { if(x==square[save[i]->num][save[i]->path3->num]) { save[mark]=save[i]->path3; save[mark]->judge=1; mark++; length=length+x; break; } } if(save[i]->rpath1!=NULL&&save[i]->rpath1->judge!=1) { if(x==square[save[i]->num][save[i]->rpath1->num]) { save[mark]=save[i]->rpath1; save[mark]->judge=1; mark++; length=length+x; break; } } if(save[i]->rpath2!=NULL&&save[i]->rpath2->judge!=1) { if(x==square[save[i]->num][save[i]->rpath2->num]) { save[mark]=save[i]->rpath2; save[mark]->judge=1; mark++; length=length+x; break; } } if(save[i]->rpath3!=NULL&&save[i]->rpath3->judge!=1) { if(x==square[save[i]->num][save[i]->rpath3->num]) { save[mark]=save[i]->rpath3; save[mark]->judge=1; mark++; length=length+x; break; } } } O=0; for(i=0;i<dotnum;i++) { O=O+M[i]->judge; } if(O==dotnum) { break; } } cout<<"最短路径为："<<length; return 0; }