《旅游景点线路模拟系统》由会员分享，可在线阅读，更多相关《旅游景点线路模拟系统（10页珍藏版）》请在金锄头文库上搜索。
1、/*/*旅游景点线路模拟系统*/# includestdio.h# includestring.htypedeftypedefint VRType; char * VertexType;int visited20;struct VertexType adjvex;/ U集中的顶点序号VRType lowcost;/ 边的权值 closedge20;/*数组（邻接矩阵）存储*/typedef struct / 弧（或边）VRType adj; /表示弧（或边）的信息 一权； NetArc,AdjMatrix2020;typedef struct / 网的定义VertexType vexs20;/
2、 顶点信息/int vex20;/访问信息AdjMatrix arcs; / 邻接矩阵int vexnum, arcnum; /顶点数目和弧（或边）数目Net;/*队列定义*/typedef int ElemType;typedef int Status;typedef struct ElemType *base;int front;int rear;int queuesize; SqQueue;Status InitQueue （SqQueue & Q） Q.base = newElemType50;/if （!Q.base） exit （OVERFLOW）;Q.queuesize = 50
3、;Q.front = Q.rear = 0;return 1;Status EnQueue (SqQueue &Q, ElemType e) if (Q.rea叶1) % Q.queuesize = Q.front)return 0;Q.baseQ.rear = e;Q.rear = (Q.rea 叶1) % Q.queuesize;return 1;Status DeQueue (SqQueue &Q, ElemType & e) if (Q.front = Q.rear)return 0;e = Q.baseQ.front;Q.front = (Q.front+1) % Q.queuesi
4、ze;return 1;/*图的邻接矩阵创建*/void Creatnet(Net &G)int i,j,k;int w;printf(数组(邻接矩阵)存储n);printf(请输入顶点数和弧数：”)；scanf( %d%d&G.vexnum,&G.arcnum); / 顶点数和弧数printf(请输入顶点信息：”)；for (i=O;iG.vexnum;i+)G.vexsi = new char 20;scanf( %s,G.vexsi);for (i=0;iG.vexnum;i+)for (j=0;jG.vexnum;j+)G.arcsij.adj= 1000;printf(请输入弧及其权
5、值(eg:2 3 23.4 矩阵中(2,3)权值为.4) : n); for (k=0;kG.arcnum;k+)scanf( %d%d%d&i,&j,&w);/ 读入一条弧和弧上的权值G.arcsi-1j-1.adj=w;/*寻找v的第一个结点*/int FirstAdjVex(Net G, int v)int i;for (i = 0; i G.vexnum; i+)if (visitedi=O&G.arcsvi.adj!=1000)return i;return -1;/*寻找v的下一个结点*/int NextAdjVex(Net G, int v, int w)int i;for (i
6、 =w; i G.vexnum; i+)if (visitedi=0&G.arcsvi.adj!=1000)return i;return -1;/*深度优先遍历(递归)*/void DFS(Net G, int v)int w;visitedv=1;/VisitFunc(v);printf( %s ,G.vexsv); / 访问第 v个顶点for (w=FirstAdjVex(G,v);w!=-1;w=NextAdjVex(G,v,w)if (!visitedw)DFS(G,w); /对v的尚未访问的邻接顶点 w递归调用DFS/*找到u在矩阵中的序号*/int LocateVex ( Net
7、 G, char * u )int i;for (i=0;iG.vexnum;i+)if (strcmp(u,G.vexsi)=0)return i;return -1;/*广度优先遍历*/void BFS(Net G, int k)SqQueue Q;int u,w,v;for (v=0; vG.vexnum; +v)visitedv = 0;/初始化访问标志InitQueue(Q);/置空的辅助队列Qfor ( v=k; vG.vexnum; +v )if ( !visitedv) / v 尚未访问visitedv = 1;printf( %s ,G.vexsv); / 访问第 v个顶点
8、EnQueue(Q, v);/ v 入队列while (Q.front!=Q.rear) DeQueue(Q, u);/队头元素出队并置为ufor (w=FirstAdjVex(G, u); w!=-1; w=NextAdjVex(G,u,w)if ( ! visitedw) visitedw=1;printf( %s ,G.vexsw); / 访问第 w个顶点 EnQueue(Q, w); /访问的顶点w入队列 / if / while/ BFSTraverse void Printall(Net G)int i,j;printf();for (i=0;iG.vexnum;i+)printf
9、( %8s ,G.vexsi);printf( n);for (j=0;jG.vexnum;j+)printf( %8s ,G.vexsj);for (i=0;iG.vexnum;i+)if (G.arcsji.adj=1000)printf();elseprintf( %8d,G.arcsji.adj); printf( n);int minimum(Net G) /求出加入生成树的下一个顶点(k)int i,closedgemin;closedgemin=closedge0.lowcost;for (i=0;iG.vexnum;i+) if ( closedgei.lowcost != 1
10、000 & closedgei.lowcost closedgemin ) closedgemin=closedgei.lowcost;for (i=0;iG.vexnum;i+)if (closedgei.lowcost=closedgemin)return i; /*最小生成树(prim)*/void MiniSpanTree_P(Net G, VertexType u)/用普里姆算法从顶点 u出发构造网G的最小生成树int j,k,i,x;k = LocateVex ( G, u );for ( j=0; jvG.vexnum; +j )/ 辅助数组初始化if (j!=k)/ 不邻接的
11、lowcost 为 m/closedgej = u, G.arcskj.adj ;/strcpy(closedgej.adjvex,u);closedgej.adjvex=u;closedgej.lowcost=G.arcskj.adj;closedgek.lowcost = 1001;/ 初始，U= ufor (i=0; i%d-%sn ,closedgex.adjvex,closedgex.lowcost, G.vexsx);生成树上一条边k=x;closedgek.lowcost = 1001;/ 第 k顶点并入 l集for (j=0; jvG.vexnum; +j)/修改其它顶点的最小
12、边if (closedgej.lowcost!=1001 &G.arcskj.adj closedgej.lowcost) closedgej.adjvex=G.vexsk;closedgej.lowcost=G.arcskj.adj;/最短路径(Floyd算法)void ShortestPath_Floyd(Net G)/i和j之间的最短路径为pij，最短路径长为Dij；若P【ij【k 为TRUE则k是从i到j当前求得最短路径上的顶点int P303030;int D3030;int v,w,u,i,j;for (v=0;vG.vexnum;v+) /各对结点间初始已知路径及距离for (w
13、=0;wG.vexnum;w+)Dvw=G.arcsvw.adj;for (u=0;uG.vexnum;u+)Pvwu=0;if (Dvw1000)/v 到 w有直接路径Pvwv=1;Pvww=1;for (u=0;uG.vexnum;u+)for (v=0;vG.vexnum;v+)for (w=0;wG.vexnum;w+)if (Dvu+DuwDvw)/ 从 v经u 到 w的一条路径更短Dvw=Dvu+Duw;for (i=0;iG.vexnum;i+)Pvwi=Pvui|Puwi;for (i=0;iG.vexnum;i+)for (j=0;jG.vexnum;j+)if (i!=j)printf( MIN(%s,%s)=%dn ,G.vexsi,G.vexsj,Dij);/最短路径(Dijkstra
