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

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

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的代价最小的边的辅

2、助数组定义：typedefstruct{charadjvex;intlowcost;}closedge;//图G中查找顶点c的位置intLocateVex(GraphG,charc){for(inti=0;i>G.ve

3、xnum>>G.arcnum;G.vexs=(char*)malloc((G.vexnum+1)*sizeof(char));//需要开辟多一个空间存储''//构造顶点向量for(inti=0;i>G.vexs[i];G.vexs[G.vexnum]='';//初始化邻接矩阵for(i=0;i

4、;i>a>>b>>w;//输入依附于弧的权值s1=LocateVex(G,a);//找到a和b在顶点向量中的位置s2=LocateVex(G,b);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中的

5、位置for(intj=0;j

6、.vexs[k]<

7、nimum(closedgecs[MAX_VERTEX_NUM]){inti=0,j,min;min=INFINITY;while(cs[i].adjvex){if(cs[i].lowcost

8、;cout<#include#defineMaxSize100#defineStackIncrement10structSeat{//定义坐标结构体intx;inty;};typedefstruct{//定义入栈信息元素类型intord;Seatseat;intdi;}SElemType;structStack{//定义