數(shù)據(jù)結(jié)構(gòu)無向圖

1、#include #include #define INFINITY100000/最大值 #define MAX_VERTEX_NUM20 /最大頂點個數(shù)typedef struct mygraphchar vexsMAX_VERTEX_NUM; /頂點向量intarcsMAX_VERTEX_NUMMAX_VERTEX_NUM;/鄰接矩陣int vexnum, arcnum;/圖的當(dāng)前頂點和弧數(shù)MGraph;typedef struct myedge intadjvex; intendvex; int lowcost; closedgeMAX_VERTEX_NUM;void CreateUDN

2、(MGraph &G) ;/創(chuàng)建無向網(wǎng)絡(luò)int LocateVex(MGraph G, char v);/結(jié)點的在頂點向量中的下標(biāo)void PrintUDN(MGraph G);/輸出存儲結(jié)構(gòu)示意圖void MiniSpanTree_PRIM(MGraph G,closedge &minedge);/求最小生成樹的算法void PrintMinEdge(MGraph G,closedge minedge); /輸出最小生成樹的邊int main() MGraph G;/定義一個圖的變量 closedge minedge; CreateUDN(G); printf(該圖的鄰接矩陣存儲示意圖如下：

3、n); PrintUDN(G); printf(n); MiniSpanTree_PRIM(G,minedge); printf(該圖生成樹的邊如下：n); PrintMinEdge(G,minedge); printf(n); return 0;void CreateUDN(MGraph &G) int i,j,k,m;char v1,v2; char ch;printf(請輸入G.vexnum 和 G.arcnum:n ); scanf(%d %d,&G.vexnum,&G.arcnum);while (ch=getchar()!=n); /* 為了去掉后面的回車符好 */for (i=0

4、; iG.vexnum; i+ ) /輸入所有的頂點，一行一個頂點 scanf(%c,&G.vexsi); / 構(gòu)造頂點向量while (ch=getchar()!=n) ;for (i=0; iG.vexnum; +i ) / 初始化所有邊之間的距離都是無窮for (j=0; jG.vexnum; +j ) G.arcsij = INFINITY;for (k=0; kG.arcnum; +k ) / 構(gòu)造鄰接矩陣scanf(%c%c %d, &v1,&v2,&m); while (ch=getchar()!=n) ;/ 確定v1和v2在G中位置i = LocateVex(G, v1); j

5、 = LocateVex(G, v2); G.arcsij=m; / 在矩陣中設(shè)置邊（v1,v2)，想通則值為1 G.arcsji=m; / 置（v1,v2)的對稱邊（v2,v1) for(i=0;iG.arcnum; +i) G.arcsii=0; / End_CreateUDNint LocateVex(MGraph G, char v)int i;for(i=0;iG.vexnum;i+)if(v=G.vexsi)break; return(i);void PrintUDN(MGraph G)int i,j; printf( ); for(i=0;iG.vexnum;i+) printf

6、( %c ,G.vexsi); printf(n); for(i=0;iG.vexnum;i+) printf(%c,G.vexsi); for(j=0;jG.vexnum;j+) if(G.arcsij = INFINITY) printf( *); else printf( %2d,G.arcsij); printf(n); void MiniSpanTree_PRIM(MGraph G,closedge &minedge) int i,j,k,z;int temp;int currentmin;k=0;for ( j=1; jG.vexnum; +j )/ 輔助數(shù)組初始化 minedge

7、j-1.adjvex=k;minedgej-1.endvex =j;minedgej-1.lowcost=G.arcskj;for (i=0; iG.vexnum-1; +i) currentmin=minedgei.lowcost; k=i;for(j=i+1;jG.vexnum-1;j+)/選擇最小的邊if(minedgej.lowcostcurrentmin)currentmin=minedgej.lowcost;k=j;/第k個元素與第i個進(jìn)行交換temp=minedgei.adjvex;minedgei.adjvex=minedgek.adjvex;minedgek.adjvex=t

8、emp;temp=minedgei.endvex;minedgei.endvex=minedgek.endvex;minedgek.endvex=temp;temp=minedgei.lowcost;minedgei.lowcost=minedgek.lowcost;minedgek.lowcost=temp;for (j=i+1; jG.vexnum-1; +j)z=minedgei.endvex ;/z為找到的新頂點k=minedgej.endvex; if(k!=z)if (G.arcszk minedgej.lowcost) minedgej.adjvex=z;minedgej.lowcost=G.arcszk; / MiniSpanTreevoid PrintMinEdge(MGraph G,closedge minedge)int i