數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)(6)圖的應(yīng)用

1、計(jì)算機(jī)系數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告（6）實(shí)驗(yàn)?zāi)康模簣D是應(yīng)用極為廣泛的數(shù)據(jù)結(jié)構(gòu)，也是這門課程的重點(diǎn)，繼續(xù)使學(xué)生更了解數(shù)據(jù)結(jié)構(gòu)加操作的程序設(shè)計(jì)觀點(diǎn)。問(wèn)題描述：給出一張某公園的導(dǎo)游圖，游客通過(guò)終端詢問(wèn)可知：a)從某一景點(diǎn)到另一個(gè)景點(diǎn)的最短路徑。b)游客從公園大門進(jìn)入，選一條最佳路線，使游客可以不重復(fù)的游覽各景點(diǎn)，最后回到出口。實(shí)驗(yàn)要求：文法是一個(gè)四元1、將導(dǎo)游圖看作一張帶權(quán)無(wú)向圖，頂點(diǎn)表示公園的各個(gè)景點(diǎn)，邊表示各景點(diǎn)之間的道路，邊上的權(quán)值表示距離，選擇適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)。2、為游客提供圖中任意景點(diǎn)相關(guān)信息的查詢；3、為游客提供任意兩個(gè)景點(diǎn)之間的一條最短的簡(jiǎn)單路徑。4、為游客選擇最佳游覽路徑。 算法分析：1、設(shè)計(jì)公

2、園平面圖，選擇適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)；2、設(shè)計(jì)圖的最短路徑算法，如果有幾條路徑長(zhǎng)度相同，選擇途徑景點(diǎn)較少的路徑給游客；3、設(shè)計(jì)圖的深度優(yōu)先搜索算法，如果有多種路徑可選，則選帶權(quán)路徑最短的路線給游客；實(shí)驗(yàn)內(nèi)容和過(guò)程：源程序：#include<iostream>using namespace std;#include<stdio.h>#define INFINITY INT_MAX#define MAX_VERTEX_NUM 20#define VRType int#define InfoType int#define VertexType char#define MAX 10#d

3、efine FALSE 0#define TRUE 1typedef enumDG,DN,UDG,UDNGraphKind;typedef struct ArcCellVRType adj;InfoType *info; ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct VertexType vexsMAX_VERTEX_NUM;AdjMatrix arcs;int vexnum,arcnum;GraphKind kind;MGraph;void DFS(MGraph G,int v);void VisitFunc(MGr

4、aph G,int v);int FirstAdjVex(MGraph G,int v);int NextAdjVex(MGraph G,int v,int w);VertexType OutVex(MGraph G,int m);typedef int PathMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef int ShortPathTableMAX_VERTEX_NUM;int LocateVex(MGraph G,VertexType v)int i=0;for(i=0;G.vexsi!=v;+i);return i;VertexType OutVe

5、x(MGraph G,int m)return G.vexsm;bool CreateUDN(MGraph &G)int i,j,k;char v1,v2;int w;G.kind=UDN;cout<<"輸入景點(diǎn)個(gè)數(shù)，道路條數(shù):"cin>>G.vexnum>>G.arcnum;cout<<"輸入各個(gè)景點(diǎn):"for(i=0;i<G.vexnum;+i)cin>>G.vexsi;for(i=0;i<G.vexnum;+i)for(j=0;j<G.vexnum;+j) G.a

6、rcsij.adj=INFINITY; G.=NULL; cout<<"輸入每條道路依附的景點(diǎn)和道路長(zhǎng)度:"<<endl;for(k=0;k<G.arcnum;+k)cin>>v1>>v2>>w;i=LocateVex(G,v1); j=LocateVex(G,v2);G.arcsij.adj=w;G.arcsji=G.arcsij;return true;bool visitedMAX;void DFSTraverse(MGraph G)int v;for(v=0;v<G.vex

7、num;+v)visitedv=false;for(v=0;v<G.vexnum;+v)if(!visitedv) DFS(G,v);void DFS(MGraph G,int v)int w;visitedv=true;VisitFunc(G,v);for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w)if(!visitedw) DFS(G,w);int FirstAdjVex(MGraph G,int v) int i ; for(i = 0; i<G.vexnum; i+) if( G.arcsvi.adj!=INFINITY )

8、 return i; if(i = (G.vexnum-1) return -1; return -1; int NextAdjVex(MGraph G,int v,int w) int i; for( i = w+1; i<G.vexnum; i+)/+1 if(G.arcsvi.adj!=INFINITY) return i; if(i = (G.vexnum-1) return -1; return -1;void VisitFunc(MGraph G,int v)cout<<G.vexsv<<" "void Shortestpath_D

9、IJ(MGraph G, int v0, PathMatrix *p, ShortPathTable *D)int v, w, i, j, min;int finalMAX_VERTEX_NUM;for (v = 0; v < G.vexnum; v+)finalv = FALSE; (*D)v = G.arcsv0v.adj;for (w = 0; w < G.vexnum; w+) (*p)vw = FALSE;if (*D)v < INFINITY)(*p)vv0 = TRUE;(*p)vv = TRUE;(*D)v0 = 0;finalv0 = TRUE;for (i

10、 = 1; i < G.vexnum; i+)min = INFINITY;for (w = 0; w < G.vexnum; w+)if (!finalw)if (*D)w < min)v = w;min = (*D)w;finalv = TRUE;for (w = 0; w < G.vexnum; w+)if (!finalw && min < INFINITY &&G.arcsvw.adj< INFINITY && (min + G.arcsvw.adj < (*D)w)(*D)w = min +

11、G.arcsvw.adj;for (j = 0; j < G.vexnum; j+)(*p)wj = (*p)vj;(*p)ww = TRUE;cout<<OutVex(G,v)<<" "int main()PathMatrix p;ShortPathTable d;char n1,n2;int m,i,j;MGraph G;CreateUDN(G);cout<<"1，最佳游覽路徑n2,任意兩景點(diǎn)最短路徑n3，退出"<<endl;cin>>m;if(m=1)DFSTraverse(G);else if(m=2)cout<<"輸入起點(diǎn)和終點(diǎn)："cin>>n1>>n2;cout<<"兩個(gè)景點(diǎn)之間最短的簡(jiǎn)單路徑為："cout<<n1<<" "Shortestpath_DIJ(G,LocateVex(G,n1),&p,&d);cout<<n2<<" "