公園導游圖：設計某公園的導游圖，游客通過終端查詢可知：從某一景點 到另一景點的最短路徑。游客從公園大門進入，選一條最佳路線，使游客可以不重復地游覽 各景點，最后回到出口（出口就在入口的旁邊）。
需要很詳細的程序
特別是實作游客從公園大門進入，選一條最佳路線，使游客可以不重復地游覽 各景點，最后回到出口（出口就在入口的旁邊）。
改一下下面的代碼 。
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#define MVNum 100//最大頂點數
#define MAXEDGE 10000
#define datatype int
#define Maxint 32767
#define MAX 100
enum boolean{FALSE,TRUE};
int D1[MVNum],p1[MVNum];
int D[MVNum][MVNum],p[MVNum][MVNum];
typedef struct
{
int begin;
int end;
int weight;
}edge;
typedef struct
{
int adj;
int weight;
}AdjMatrix[MAX][MAX];
typedef struct
{
AdjMatrix arc;
int vexnum, arcnum;
}MGraph;
void CreatGraph(MGraph *,int n,int m);//函式申明
void sort(edge* ,MGraph *,int m);
void MiniSpanTree(MGraph *,int n,int m);
int Find(int *, int );
void Swapn(edge *, int, int);
void Dijkstra(MGraph *G,int v1,int n) ;
void Floyd(MGraph *G,int n);
void save(MGraph *G,int n1,int m1)
{
FILE *fp;
fp=fopen("sheji.txt","a+");
fprintf(fp,"景點(%d ,%d)有邊，且它們之間的距離為%4d\n",n1,m1,G->arc[n1][m1].weight);
fclose(fp);
}
void CreatGraph(MGraph *G,int n,int m)//構件圖
{
int i,j,n1,m1;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
G->arc[i][j].adj=G->arc[j][i].adj=0;
G->arc[i][j].weight=G->arc[j][i].weight=Maxint;
}
}
for( i=1;i<=m;i++)//輸入邊和權值
{
printf("\n請輸入有邊的2個頂點:\n");
scanf("%d%d",&n1,&m1);
while(n1<0||m1<0||n1>n||m1>n)
{
printf("輸入的數字不符合要求 請重新輸入:");
scanf("%d%d",&n1,&m1);
}
G->arc[n1][m1].adj=G->arc[m1][n1].adj = 1;
printf("\n請輸入%d與%d之間的權值:", n1, m1);
scanf("%d",&G->arc[n1][m1].weight);
G->arc[m1][n1].weight=G->arc[n1][m1].weight;
save(G,n1,m1);
}
printf("鄰接矩陣為:\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf("%d",G->arc[i][j].adj);
}
printf("\n");
}
}
void sort(edge edges[],MGraph *G,int m)//對權值進行排序
{
int i, j;
for(i=1;i<m;i++)
{
for(j=i+1;j<=m;j++)
{
if(edges[i].weight>edges[j].weight)
{
Swapn(edges,i,j);
}
}
}
printf("權排序之后的為:\n");
for(i=1;i< m;i++)
{
printf("<<%d,%d>> %d\n",edges[i].begin,edges[i].end,edges[i].weight);
}
}
void Swapn(edge *edges,int i,int j)//交換權值 以及頭和尾
{
int temp;
temp = edges[i].begin;
edges[i].begin = edges[j].begin;
edges[j].begin = temp;
temp = edges[i].end;
edges[i].end = edges[j].end;
edges[j].end = temp;
temp = edges[i].weight;
edges[i].weight = edges[j].weight;
edges[j].weight = temp;
}
void MiniSpanTree(MGraph *G,int n,int m)//生成最小生成樹
{
int i,j,n1,m1;
int k=1;
int parent[MVNum];
edge edges[MVNum];
for(i=1;i<n;i++)
{
for(j=i+1;j<=n;j++)
{
if(G->arc[i][j].adj==1)
{
edges[k].begin=i;
edges[k].end=j;
edges[k].weight=G->arc[i][j].weight;
k++;
}
}
}
sort(edges,G,m);
for(i=1;i<=m;i++)
{
parent[i]=0;
}
printf("最小生成樹為:\n");
for(i=1;i<=m;i++)//核心部分
{
n1=Find(parent,edges[i].begin);
m1=Find(parent,edges[i].end);
if(n1!=m1)
{
parent[n1]=m1;
printf("<<%d,%d>>%d\n",edges[i].begin,edges[i].end,edges[i].weight);
}
}
}
int Find(int *parent,int f)//找尾
{
while(parent[f]>=0)
{
f=parent[f];
}
return (f);
}
void Dijkstra(MGraph *G,int v1,int n)
{
//用Dijkstra演算法求有向圖G的v1頂點到其他頂點v的最短路徑p[v]及其權D[v]
//設G是有向圖的鄰接矩陣，若邊<i,j>不存在，則G[i][j]=Maxint
//S[v]為真當且僅當v屬于s,即已求得從v1到v的最短路徑
int D2[MVNum],p2[MVNum];
int v,i,w,min;
enum boolean S[MVNum];
for(v=1;v<=n;v++)
{
//初始化S和D
S[v]=FALSE;//置空最短路徑終點集
D2[v]=G->arc[v1][v].weight;//置初始的最短路徑值
if(D2[v]<Maxint)
p2[v]=v1;//v1是v的前趨
else p2[v]=0;//v無前趨
}//end_for
D2[v1]=0;S[v1]=TRUE;//S集初始時只有源點，源點到源點的距離為0
//開始回圈，每次求得v1到某個v頂點的最短路徑，并加v到S集中
for(i=2;i<n;i++)
{//其余n-1個頂點
min=Maxint;
for(w=1;w<=n;w++)
if(!S[w]&&D2[w]<min)
{
v=w;min=D2[w];
}//w頂點離v1頂點更近
S[v]=TRUE;
for(w=1;w<=n;w++)//更新當前最短路徑及距離
if(!S[w]&&(D2[v]+G->arc[v][w].weight<D2[w]))
{ //修改D2[w]和p2[w]，w屬于V-S
D2[w]=D2[v]+G->arc[v][w].weight;
p2[w]=v;
}//end_if
}//end_for
printf("路徑長度 路徑\n");
for(i=1;i<=n;i++)
{
printf("%5d",D2[i]);
printf("%5d",i);
v=p2[i];
while(v!=0)
{
printf("<-%d",v);
v=p2[v];
}
printf("\n");
}
}
void Floyd(MGraph *G,int n)
{
int i,j,k;
for(i=1;i<=n;i++)//設定路徑長度D和路徑path初值
for(j=1;j<=n;j++)
{
if(G->arc[i][j].weight!=Maxint)
p[i][j]=j;//j是i的后繼
else
p[i][j]=0;
D[i][j]=G->arc[i][j].weight;
}
for(k=1;k<=n;k++)
{ //做k次迭代，每次均試圖將頂點k擴充到當前求得的從i到j的最短路徑pij上
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(D[i][k]+D[k][j]<D[i][j])
{
D[i][j]=D[i][k]+D[k][j];//修改長度
p[i][j]=p[i][k];
//printf("dij=%d,pij=%d\n",D[i][j],p[i][j]);
}
}
}
}
void main()
{
MGraph *G;
int n,m,v,w,k;
int xz=1;
G=(MGraph *)malloc(sizeof(MGraph));
if (G == NULL)
{
printf("memory allcation failed,goodbye");
exit(1);
}
printf("請輸入頂點數和邊數:");
scanf("%d%d",&G->vexnum,&G->arcnum);
n=G->vexnum;
m=G->arcnum;
CreatGraph(G,n,m);//建立圖的存盤結構
while(xz!=0)
{
printf("******求景點之間的最短路徑******\n");
printf("================================\n");
printf("1.求一個景點到所有景點的最短路徑\n");
printf("2.求任意的兩個景點之間的最短路徑\n");
printf("3.求從景點的入口到出口的最短路徑\n");
printf("=================================\n");
printf(" 請選擇: 1 或 2, 選擇 0 退出 :");
scanf("%d",&xz);
if(xz==2)
{
Floyd(G,n);//呼叫Floyd演算法
printf(" 輸入起點和終點: v,w : ");
scanf("%d,%d",&v,&w);
k=p[v][w];//k為起點v的后繼頂點
if(k==0)
printf("景點 %d到 %d 無路徑!\n",v,w);
else
{
printf("從景點%d到%d的最短路徑是:%d",v,w,v);
while(k!=w)
{
printf("->%d",k);//輸出后繼頂點
k=p[k][w];//繼續找下一個后繼頂點
}
printf("->%d",w);//輸出終點w
printf(" 路徑長度: %d\n",D[v][w]);
}
}
else
if(xz==1)
{
printf("求單源路徑,輸入景點 v: ");
scanf("%d",&v);
Dijkstra(G,v,n);//呼叫Dijkstra演算法
}
else
if(xz==3)
{
MiniSpanTree(G,n,m);
}
}
printf("結束求最短路徑，再見！\n");
}
uj5u.com熱心網友回復：
主要是實作不了游客從入口到出口游玩所有經典的最短路uj5u.com熱心網友回復：
如果是景點不能重復，那這個問題在很多情況下是無解的如果是路徑不能重復，那就是一筆畫問題
一筆畫問題的充要條件就是奇節點的數目為0個或者2個，先判斷是否存在不重復游覽的線路，再去求這個線路
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/74392.html
標籤：基礎類
上一篇：小波變換