資源描述:
《普里姆算法(prim)求最小生成樹(shù)c程序》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。
1、1程序測(cè)試用例如下:561425523463465程序運(yùn)行過(guò)程截圖:源程序清單如下:#include#definen6#defineMaxNum10000/*定義一個(gè)最大整數(shù)*//*定義鄰接矩陣類型*/typedefintadjmatrix[n+1][n+1];/*0號(hào)單元沒(méi)用*/typedefstruct{intfromvex,tovex;intweight;}Edge;typedefEdge*EdgeNode;intarcnum;/*邊的個(gè)數(shù)*//*建立圖的鄰接矩陣*/voidCreatMatrix(adjmatri
2、xGA){inti,j,k,e;printf("圖中有%d個(gè)頂點(diǎn)",n);for(i=1;i<=n;i++){for(j=1;j<=n;j++){if(i==j){GA[i][j]=0;/*對(duì)角線的值置為0*/}else{GA[i][j]=MaxNum;/*其它位置的值置初始化為一個(gè)最大整數(shù)*/}}}printf("請(qǐng)輸入邊的個(gè)數(shù):");scanf("%d",&arcnum);printf("請(qǐng)輸入邊的信息,按照起點(diǎn),終點(diǎn),權(quán)值的形式輸入:");for(k=1;k<=arcnum;k++){scanf("%d,%d,%d",&i,
3、&j,&e);/*讀入邊的信息*/GA[i][j]=e;GA[j][i]=e;}}/*初始化圖的邊集數(shù)組*/voidInitEdge(EdgeNodeGE,intm){inti;for(i=1;i<=m;i++){GE[i].weight=0;}}/*根據(jù)圖的鄰接矩陣生成圖的邊集數(shù)組*/voidGetEdgeSet(adjmatrixGA,EdgeNodeGE){inti,j,k=1;for(i=1;i<=n;i++){for(j=i+1;j<=n;j++){if(GA[i][j]!=0&&GA[i][j]!=MaxNum){GE[k].
4、fromvex=i;GE[k].tovex=j;GE[k].weight=GA[i][j];k++;}}}}/*按升序排列圖的邊集數(shù)組*/voidSortEdge(EdgeNodeGE,intm){inti,j,k;Edgetemp;for(i=1;iGE[j].weight){k=j;}}if(k!=i){temp=GE[i];GE[i]=GE[k];GE[k]=temp;}}}/*利用普里姆算法從初始點(diǎn)v出發(fā)求鄰接矩陣表示的圖的最小生成樹(shù)*
5、/voidPrim(adjmatrixGA,EdgeNodeT){inti,j,k,min,u,m,w;Edgetemp;/*給T賦初值,對(duì)應(yīng)為v1依次到其余各頂點(diǎn)的邊*/k=1;for(i=1;i<=n;i++){if(i!=1){T[k].fromvex=1;T[k].tovex=i;T[k].weight=GA[1][i];k++;}}/*進(jìn)行n-1次循環(huán),每次求出最小生成樹(shù)中的第k條邊*/for(k=1;k
6、=T[j].weight;m=j;}}/*把最短邊對(duì)調(diào)到k-1下標(biāo)位置*/temp=T[k];T[k]=T[m];T[m]=temp;/*把新加入最小生成樹(shù)T中的頂點(diǎn)序號(hào)賦給j*/j=T[k].tovex;/*修改有關(guān)邊,使T中到T外的每一個(gè)頂點(diǎn)保持一條到目前為止最短的邊*/for(i=k+1;i
7、e){inti;printf("按照起點(diǎn),終點(diǎn),權(quán)值的形式輸出的最小生成樹(shù)為:");for(i=1;i<=e;i++){printf("%d,%d,%d",GE[i].fromvex,GE[i].tovex,GE[i].weight);}}voidmain(){adjmatrixGA;EdgeGE[n*(n-1)/2],T[n];CreatMatrix(GA);InitEdge(GE,arcnum);GetEdgeSet(GA,GE);SortEdge(GE,arcnum);Prim(GA,T);printf("");OutE
8、dge(T,n-1);}