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

《最小生成树和迷宫求解问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、#include#includeusingnamespacestd;ifstreamfin("prim.txt");#defineMAX_VERTEX_NUM20#defineERROR-1#defineINFINITY0x7fff//图的邻接矩阵存储结构typedefstruct{char*vexs;intarcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];intvexnum,arcnum;}Graph;//记录从顶点集U到V-U的代价最小的边的辅助数组定义：typedefstruct{charadjvex;

2、intlowcost;}closedge;//图G中查找顶点c的位置intLocateVex(GraphG,charc){for(inti=0;i>G.vexnum>>G.arcnum;G.vexs=(char*)malloc((G.vexnum+1)*sizeof(char))

3、;//需要开辟多一个空间存储''//构造顶点向量for(inti=0;i>G.vexs[i];G.vexs[G.vexnum]='';//初始化邻接矩阵for(i=0;i>a>>b>>w;//输入依附于弧的权值s1=LocateVex(G,a);//找到a和b在顶点向量中的位置s2=LocateVex(G,b);

4、G.arcs[s1][s2]=G.arcs[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

5、NFINITY;cl[k].adjvex=u;//初始，U={u}cl[k].lowcost=0;for(inti=0;i

6、l[j].lowcost=G.arcs[k][j];}}}//MiniSpanTree/*算法简要：1、找到开始的结点2、对辅助数组初始化3、更新变化每一步，使得每次都选择最小边4、调整结束*/intminimum(closedgecs[MAX_VERTEX_NUM]){inti=0,j,min;min=INFINITY;while(cs[i].adjvex){if(cs[i].lowcost

7、in(){GraphG;CreateUDN(G);cout<<"result:"<#include#defineMaxSize100#defineStackIncrement10structSeat{//定义坐标结构体intx;inty;};typedefstruct{//定义入栈信息元素类型intord;Seatseat;intdi;}SElemType;structStack{//定义