最短路径与最小生成树

《最短路径与最小生成树》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实用标准文案数据结构实验报告姓名：邱金梁班级：rJBJava101学号：201007092137指导老师：杨关时间：2012年6月13日精彩文档实用标准文案一、最小生成树#include//头文件usingnamespacestd;#defineMAX_VERTEX_NUM20//最大结点数#defineMAX200typedefstructClose//结构体{charadjvex;intlowcost;}Close,close[MAX_VERTEX_NUM];typedefstructArcNode{intadjvex;A

2、rcNode*nextarc;intinfo;}ArcNode;typedefstructVNode{chardata;ArcNode*firstarc;}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct{AdjListverties;intvexnum,arcnum;}ALGraph;ALGraphG;//对象GintLocateVek(ALGraph,char);//返回结点位置intminimum(close);//返回最小数voidMinSpanTree_PRIM(ALGraph,char);//最小

3、生成树voidCreate(ALGraph&);//创建邻接表intmain(){chara;inti=1;Create(G);/*for(inti=1;i<=G.vexnum;i++){for(s=G.verties[i].firstarc;s!=NULL;s=s->nextarc)cout<adjvex].data<<"===="<info<>a;MinSpanTr

4、ee_PRIM(G,a);cout<<"如果结束输入'0',否则输入'1':";cin>>i;}return0;}intLocateVek(ALGraphG,charu){inti;for(i=1;i<=G.vexnum;i++)if(u==G.verties[i].data)returni;return-1;}intminimum(closem)//返回最小数{inti=0,j,n=200;for(i=1;i<=G.vexnum;i++)if(m[i].lowcost

5、;}returnj;}voidMinSpanTree_PRIM(ALGraphG,charu){intj,k,a;closeclosedge;ArcNode*s,*p,*q;for(j=1;j<=MAX_VERTEX_NUM;j++)closedge[j].lowcost=MAX;//把所有值都赋为最大k=LocateVek(G,u);for(j=1;j<=G.vexnum;j++)if(j!=k){closedge[j].adjvex=u;for(s=G.verties[k].firstarc;s!=NULL;s=s->nextarc)if(j

6、==s->adjvex){closedge[j].lowcost=s->info;break;精彩文档实用标准文案}}closedge[k].lowcost=0;cout<<"最小生成树:"<<"{";//查找并输出最小生成树for(j=1;j

7、rties[k].firstarc;p!=NULL;p=p->nextarc)if(p->infoadjvex){closedge[i].adjvex=G.verties[k].data;closedge[i].lowcost=p->info;}}}cout<<"}"<=1;j--){if(closedge[j].lowcost==0&&G.verties[j].data!=u){c

8、out<<"("<