最小生成树和迷宫求解问题.doc

#include<iostream>#include<fstream>usingnamespacestd;ifstreamfin("");#defineMAX_VERTEX_NUM20#defineERROR-1#defineINFINITY0x7fff//图的邻接矩阵存储结构typedefstruct{char*vexs;intarcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];intvexnum,um;}Graph;//记录从顶点集U到V-U的代价最小的边的辅助数组定义:typedefstruct{charadjvex;intlowcost;}closedge;//图G中查找顶点c的位置intLocateVex(GraphG,charc){for(inti=0;i<;++i){if([i]==c)returni;}returnERROR;}intminimum(closedgecs[MAX_VERTEX_NUM]);//创建无向网voidCreateUDN(Graph&G){//采用数组(邻接矩阵)表示法,构造无向网Gfin>>>>;=(char*)malloc((+1)*sizeof(char));//需要开辟多一个空间存储'\0'//构造顶点向量for(inti=0;i<;i++)fin>>[i];[]='\0';//初始化邻接矩阵for(i=0;i<;++i)for(intj=0;j<;j++)[i][j]=INFINITY;chara,b;ints1,s2,w;for(i=0;i<;++i){fin>>a>>b>>w;//输入依附于弧的权值s1=LocateVex(G,a);//找到a和b在顶点向量中的位置s2=LocateVex(G,b);[s1][s2]=[s2][s1]=w;}}voidMiniSpanTree_PRIN(GraphG,charu){//用普里姆算法从第u个顶点出发构造网G的最小生成树T,输出T的各条边closedgecl[MAX_VERTEX_NUM];intk=LocateVex(G,u);//返回顶点u在图G中的位置for(intj=0;j<;++j){//辅助数组初始化if(j!=k){cl[j].adjvex=u;cl[j].lowcost=[k][j];}}cl[j].adjvex='\0';cl[j].lowcost=INFINITY;cl[k].adjvex=u;//初始,U={u}cl[k].lowcost=0;for(inti=0;i<;++i){k=minimum(cl);//求出T的下一个结点:第k顶点cout<<cl[k].adjvex<<"连接"<<[k]<<endl;//输出生成树的边cl[k].lowcost=0;//第k顶点并入U集for(j=0;j<;++j)if([k][j]<cl[j].lowcost){//新顶点并入U后重新选择最小边,将所有变化的