数据结构实验(6)图的应用

计算机系数据结构实验报告（6）

实验目的：

图是应用极为广泛的数据结构，也是这门课程的重点，继续使学生更了解数据结构加操作的程序设计观点。

问题描述：

给出一张某公园的导游图，游客通过终端询问可知： a)从某一景点到另一个景点的最短路径。

b)游客从公园大门进入，选一条最佳路线，使游客可以不重复的游览各景点，最后回到出口。

实验要求：文法是一个四元

1、将导游图看作一张带权无向图，顶点表示公园的各个景点，边表示各景点之间的道路，边上的权值表示距离，选择适当的数据结构。 2、为游客提供图中任意景点相关信息的查询；

3、为游客提供任意两个景点之间的一条最短的简单路径。 4、为游客选择最佳游览路径。

算法分析：

1、设计公园平面图，选择适当的数据结构；

2、设计图的最短路径算法，如果有几条路径长度相同，选择途径景点较少的路径给游客； 3、设计图的深度优先搜索算法，如果有多种路径可选，则选带权路径最短的路线给游客；

实验内容和过程：

源程序：

#include using namespace std; #include

#define INFINITY INT_MAX #define MAX_VERTEX_NUM 20 #define VRType int #define InfoType int #define VertexType char #define MAX 10 #define FALSE 0 #define TRUE 1

typedef enum{DG,DN,UDG,UDN}GraphKind; typedef struct ArcCell {

VRType adj;

InfoType *info;

}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct {

VertexType vexs[MAX_VERTEX_NUM]; AdjMatrix arcs; int vexnum,arcnum; GraphKind kind;

- 1 -

}MGraph;

void DFS(MGraph G,int v);

void VisitFunc(MGraph 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 PathMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef int ShortPathTable[MAX_VERTEX_NUM]; int LocateVex(MGraph G,VertexType v) {

int i=0;

for(i=0;G.vexs[i]!=v;++i); return i; }

VertexType OutVex(MGraph G,int m) {

return G.vexs[m]; }

bool CreateUDN(MGraph &G) {

int i,j,k; char v1,v2; int w;

G.kind=UDN;

cout<<\输入景点个数，道路条数:\ cin>>G.vexnum>>G.arcnum; cout<<\输入各个景点:\ for(i=0;i>G.vexs[i]; for(i=0;i

G.arcs[i][j].adj=INFINITY; G.arcs[i][j].info=NULL; }

cout<<\输入每条道路依附的景点和道路长度:\ for(k=0;k

cin>>v1>>v2>>w;

i=LocateVex(G,v1); j=LocateVex(G,v2); G.arcs[i][j].adj=w;

G.arcs[j][i]=G.arcs[i][j]; }

return true; }

bool visited[MAX];

void DFSTraverse(MGraph G) {

int v;

for(v=0;v

- 2 -

for(v=0;v

if(!visited[v]) DFS(G,v); }

void DFS(MGraph G,int v) {

int w;

visited[v]=true;VisitFunc(G,v);

for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w)) if(!visited[w]) DFS(G,w); }

int FirstAdjVex(MGraph G,int v) {

int i ;

for(i = 0; i

if( G.arcs[v][i].adj!=INFINITY ) 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

if(G.arcs[v][i].adj!=INFINITY) return i; if(i == (G.vexnum-1)) return -1; return -1; }

void VisitFunc(MGraph G,int v) {

cout<

void Shortestpath_DIJ(MGraph G, int v0, PathMatrix *p, ShortPathTable *D) {

int v, w, i, j, min;

int final[MAX_VERTEX_NUM];

for (v = 0; v < G.vexnum; v++) {

final[v] = FALSE;

(*D)[v] = G.arcs[v0][v].adj; for (w = 0; w < G.vexnum; w++) {

(*p)[v][w] = FALSE; }

if ((*D)[v] < INFINITY) {

(*p)[v][v0] = TRUE; (*p)[v][v] = TRUE; } }

(*D)[v0] = 0;

- 3 -

final[v0] = TRUE;

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

min = INFINITY;

for (w = 0; w < G.vexnum; w++) {

if (!final[w]) {

if ((*D)[w] < min) {

v = w;

min = (*D)[w]; } } }

final[v] = TRUE;

for (w = 0; w < G.vexnum; w++) {

if (!final[w] && min < INFINITY &&

G.arcs[v][w].adj

< INFINITY && (min + G.arcs[v]

[w].adj < (*D)[w])) {

(*D)[w] = min + G.arcs[v][w].adj; for (j = 0; j < G.vexnum; j++) {

(*p)[w][j] = (*p)[v][j]; }

(*p)[w][w] = TRUE;

cout<

int main() {

PathMatrix p; ShortPathTable d; char n1,n2; int m,i,j; MGraph G; CreateUDN(G);

cout<<\，最佳游览路径\\n2,任意两景点最短路径\\n3，退出\ cin>>m;

if(m==1)DFSTraverse(G); else if(m==2) {

cout<<\输入起点和终点：\ cin>>n1>>n2;

- 4 -

}

cout<<\两个景点之间最短的简单路径为：\ cout<

Shortestpath_DIJ(G,LocateVex(G,n1),&p,&d); cout<

cout<<\最短路径总距离为:\}

else if(m==3)exit(0); else cout<<\

实验结果：

测试图：

- 5 -

总结和感想：

难度大，C有待加强，理论知识不够充分，之后还需测试改进。

- 6 -