数据结构无向图

1、#include #include #define INFINITY100000/最大值 #define MAX_VERTEX_NUM20 /最大顶点个数typedef struct mygraphchar vexsMAX_VERTEX_NUM; /顶点向量intarcsMAX_VERTEX_NUMMAX_VERTEX_NUM;/邻接矩阵int vexnum, arcnum;/图的当前顶点和弧数MGraph;typedef struct myedge intadjvex; intendvex; int lowcost; closedgeMAX_VERTEX_NUM;void CreateUDN

2、(MGraph &G) ;/创建无向网络int LocateVex(MGraph G, char v);/结点的在顶点向量中的下标void PrintUDN(MGraph G);/输出存储结构示意图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); / 构造顶点向量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 ) / 构造邻接矩阵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; / 在矩阵中设置边（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 )/ 辅助数组初始化 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个进行交换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