数据结构地图导游系统含源码(5)

{

//dist数组记录各条最短路径长度，path数组记录对应路径上的各顶点 int mindist,i,j,k,t=1;

for(i=1;i<=G->vexnum;i++) //初始化 {

dist[i]=G->arcs[start][i];

if(G->arcs[start][i]!=INFINITY) path[i][1]=start; }

path[start][0]=1;

for(i=2;i<=G->vexnum;i++) //寻找各条最短路线 {

mindist=INFINITY;

for(j=1;j<=G->vexnum;j++) //选择最小权值的路线 if(!path[j][0] && dist[j]

k=j;

mindist=dist[j]; }

if(mindist == INFINITY) return ;

path[k][0]=1;

for(j=1;j<=G->vexnum;j++) //修改路线 {

if(!path[j][0]&&G->arcs[k][j]arcs[k][j]

dist[j]=dist[k]+G->arcs[k][j]; t=1;

while(path[k][t]!=0) //记录最新的最短路线 {

path[j][t]=path[k][t]; t++; }

path[j][t]=k; path[j][t+1]=0; } } }

for(i=1;i<=G->vexnum;i++) if(i == ending) break; printf(\的最短路线为：从%s\ for(j=2;path[i][j]!=0;j++)

printf(\

&& \\n printf(\距离为%dm\\n\}

void Shortcut(AdjMatrix *G) //寻找最短路线 {

char name[20]; int start,ending; int i;

int dist[MAXVEX],path[MAXVEX][MAXVEX]={0}; printf(\校园里有以下景点:\\n\ for(i=1;i<=G->vexnum;i++)

printf(\ printf(\请输入起点景点名称:\ scanf(\ start=Locate(G,name);

printf(\请输入终点景点名称:\ scanf(\

ending=Locate(G,name);

Dijkstra(G,start,ending,dist,path); }

void Prim(AdjMatrix *G,int start) //采用Prim算法求得最短连通路线 {

struct {

int adjvex; //存放顶点序号 int lowcost; //存放权值 }closedge[MAXVEX]; int i,e,k,m,mincost;

closedge[start].lowcost=0; //起始点的权值初始化为0，该顶点加入到生成树集合中

//对除了出发点以外的所有顶点初始化对应的closedge数组 for(i=1;i<=G->vexnum;i++) if(i != start) {

closedge[i].adjvex=start;

closedge[i].lowcost=G->arcs[start][i]; }

//控制选中的n-1条符合条件的边 for(e=1;e<=G->vexnum-1;e++) {

//选择最小权值的边 mincost=INFINITY;

for(k=1;k<=G->vexnum;k++) {

if(closedge[k].lowcost!=0 && closedge[k].lowcost

m=k;

mincost=closedge[k].lowcost; } }

printf(\

从%s--%s:%dm\\n\lowcost);

closedge[m].lowcost=0; //标志该顶点加入到最小生成树集合中

//更新closedge数组信息 for(i=1;i<=G->vexnum;i++)

if(i!=m && G->arcs[m][i]

//一旦发现有更小的权值边出现，则替换原有信息 {

closedge[i].lowcost=G->arcs[m][i]; closedge[i].adjvex=m; } } }

void MiniSpanTree(AdjMatrix *G) //查询从某个景点的最短连通路线 {

char name[20]; int start; int i;

for(i=1;i<=G->vexnum;i++)

printf(\ printf(\请输入起始地点名称: \ scanf(\ start=Locate(G,name);

printf(\从%s开始的最短连通路线为:\\n\\n\ Prim(G,start); }

int m=1,min=INT_MAX; int path[20]={0}; int tag;

void DFS(AdjMatrix *G,int start,int ending,int stack[],int visited[]) //深度遍历查找所有路径 {

int i, j;

for(i=1; i<=G->vexnum; i++) {

if(G->arcs[start][i] != INFINITY && visited[i]==0) {

if(i == ending)//如果深搜到了终点，就输出刚才经过的路径

{

// tag用于判断找最优路径还是所有路径

if(tag==1) // 找所有路径时输出路径 { for(j=0; j

else//如果该点不是终点 {

visited[i]=1;

stack[m] = i;//将该点存起来 m++;

DFS(G,i,ending,stack,visited);//接着深搜 visited[i]=0; m--; } } } }

void SimpleRoute(AdjMatrix *G) //查询两个景点间的最优路径（中转次数最少） {

char name[20]; int i;

int start,ending; int stack[20]={0}; int visited[20]={0};

printf(\该校园包含以下景点:\\n\ for(i=1;i<=G->vexnum;i++)

printf(\

printf(\请输入起始地点名称: \ scanf(\ start=Locate(G,name); stack[0]=start;

printf(\请输入终止地点名称: \ scanf(\

ending=Locate(G,name); visited[start]=1;

tag=0;

DFS(G,start,ending,stack,visited);

printf(\最优路径即中转次数最少的路径为：\\n\

for(i=0;i

printf(\ printf(\}

void SearchAllRoute(AdjMatrix *G) //输出两景点之间的所有路径 {

char name[20]; int start,ending; int i;

int stack[20]={0}; int visited[20]={0};

printf(\校园中有以下景点:\\n\ for(i=1;i<=G->vexnum;i++)

printf(\ printf(\请输入起始地点名称: \ scanf(\ start=Locate(G,name); stack[0]=start;

printf(\请输入终止地点名称: \ scanf(\

ending=Locate(G,name); visited[start]=1; tag=1;

DFS(G,start,ending,stack,visited); }

void menu1() //开始菜单界面 {

system(\

printf(\~~~~~~~~~~~~~*\\n\

printf(\ *\\n\ printf(\ *\\n\

printf(\ 欢迎进入西安邮电大学校园导游系统 *\\n\

printf(\ *\\n\ printf(\ *\\n\

printf(\~~~*\\n\