圖的遍歷數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告

1、山西大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院實(shí)驗(yàn)報(bào)告姓 名學(xué) 號(hào)專業(yè)班級(jí)課程名稱 數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)日期2015/5/20成 績(jī)指導(dǎo)教師批改日期實(shí)驗(yàn)名稱 圖遍歷的演示一、實(shí)驗(yàn)?zāi)康模?1、問(wèn)題描述：很多涉及圖上操作的算法都是以圖的遍歷操作為基礎(chǔ)的。本次實(shí)驗(yàn)要求寫(xiě)一個(gè)程序，演示在連通的無(wú)向圖上訪問(wèn)全部結(jié)點(diǎn)的操作； 2、基本要求：以鄰接多重表為存儲(chǔ)結(jié)構(gòu)，實(shí)現(xiàn)連通無(wú)向圖的深度優(yōu)先和廣度優(yōu)先遍歷。以用戶指定的結(jié)點(diǎn)為起點(diǎn)，分別輸出每種遍歷下的結(jié)點(diǎn)訪問(wèn)序列和相應(yīng)生成樹(shù)的邊集； 3、測(cè)試數(shù)據(jù)：教科書(shū)圖7.33（一個(gè)表示交通網(wǎng)的例圖）。暫時(shí)忽略里程，起點(diǎn)為北京。 4、實(shí)現(xiàn)提示：設(shè)圖的結(jié)點(diǎn)不超過(guò)30個(gè)，每個(gè)結(jié)點(diǎn)用一個(gè)編號(hào)表示（如果一個(gè)

2、圖有n個(gè)結(jié)點(diǎn)，則它們的編號(hào)分別為1,2，n）。通過(guò)輸入圖的全部邊輸入一個(gè)圖，每個(gè)邊為一個(gè)數(shù)對(duì)，可以對(duì)邊的輸入順序作出某種限制。注意，生成樹(shù)的邊是有向邊，端點(diǎn)順序不能顛倒。二、實(shí)驗(yàn)內(nèi)容:1、 概要設(shè)計(jì)（1）抽象數(shù)據(jù)類型圖的定義如下：ADT Stack 數(shù)據(jù)對(duì)象V：V是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點(diǎn)集。數(shù)據(jù)關(guān)系R： R=VRVR=(v,w)|v,wV,(v,w)表示v和w之間存在的路徑基本操作P： CreateGraph（&G,V,VR） 初始條件：V是圖的頂點(diǎn)集，VR是圖中邊的集合。 操作結(jié)果：按V和VR的定義構(gòu)造圖G。DestroyGraph(&G)初始條件：圖G已存在

3、。操作結(jié)果：圖G被銷毀。 LocateVex（G,u）初始條件：圖G存在，u和G中頂點(diǎn)有相同特征。操作結(jié)果：若G中存在頂點(diǎn)u,則返回該頂點(diǎn)在圖中的位置；否則返回其他信息。 GetVex（G,v）初始條件：圖G存在，v是G中某個(gè)頂點(diǎn)。操作結(jié)果：返回v的信息。 FirsrEdge（G,v）初始條件：圖G存在，v是G中某個(gè)頂點(diǎn)。操作結(jié)果：返回依附于v的第一條邊。若該頂點(diǎn)在G中沒(méi)有鄰接點(diǎn)，則返回“空”。 NextEdge（G，v，w）初始條件：圖G存在，v是G中某個(gè)頂點(diǎn)，w是v的鄰接頂點(diǎn)。操作結(jié)果：返回依附于v的（相對(duì)于w的）下一條邊。若不存在，則返回“空”。 InsertVex（&G,v）初

4、始條件：圖G存在，v和圖中頂點(diǎn)有相同特征。操作結(jié)果：在圖G中增添新頂點(diǎn)v。DeleteVex（&G,v）初始條件：圖G存在，v是G中某個(gè)頂點(diǎn)。操作結(jié)果：刪除G中頂點(diǎn)v及其相關(guān)的邊。 InsertEdge（&G,v，w）初始條件：圖G存在，v和w是G中兩個(gè)頂點(diǎn)。操作結(jié)果：在G中增添邊（v,w）。DeleteEdge（&G,v，w）初始條件：圖G存在，v和w是G中兩個(gè)頂點(diǎn)。操作結(jié)果：在G中刪除邊（v,w）。GetShortestPath（G，st，nd，&Path）初始條件：圖G存在，st和nd是G中兩個(gè)頂點(diǎn)。操作結(jié)果：若st和nd之間存在路徑，則以Path返回兩點(diǎn)

5、之間一條最短路徑，否則返回其他信息。ADT Graph （2）本程序包含三個(gè)模塊： 1）主程序模塊 void main() 初始化； do 接受命令； 處理命令；while（“命令”！=“退出”）； 2）深度優(yōu)先遍歷void DFS(Graph *graph,int v) 3）廣度優(yōu)先遍歷void BFS(Graph *graph,int u) 2、 詳細(xì)設(shè)計(jì)#include "stdafx.h"#include<stdio.h>#include<malloc.h>#include<stdlib.h>#define MAX 30typed

6、ef struct QNode int data; struct QNode *next;QNode;typedef struct QNode *rear; QNode *front;LinkQueue;void InitQueue(LinkQueue *Q) Q->front =Q->rear =(QNode *)malloc(sizeof(QNode); Q->front ->next =NULL;void EnQueue(LinkQueue *Q,int v) QNode *p; p=(QNode *)malloc(sizeof(QNode); p->dat

7、a =v; p->next =NULL; Q->rear ->next =p; Q->rear =p;void DeQueue(LinkQueue *Q,int *v) QNode *p; if(Q->front =Q->rear ) return; p=Q->front ->next ; *v=p->data ; Q->front ->next =p->next ; if(Q->rear =p) Q->rear =Q->front ; free(p);typedef struct EdgeNode in

8、t ivex,jvex; struct EdgeNode *ilink,*jlink;EdgeNode;typedef struct VexNode int markV; char info; int num; EdgeNode *firstedge;VexNode;typedef struct VexNode adjlistMAX; int vexnum,edgenum;Graph;void Initilized(Graph *graph) graph=(Graph *)malloc (sizeof(Graph); graph->vexnum =0; graph->edgenum

9、 =0;void CreateGraph(Graph *graph) EdgeNode *p,*q,*e; int i; printf("請(qǐng)輸入連通無(wú)向圖的頂點(diǎn)個(gè)數(shù)和邊的條數(shù)：n"); scanf("%d %d",&graph->vexnum,&graph->edgenum); while(graph->vexnum>MAX|graph->edgenum >(graph->vexnum *(graph->vexnum -1)/2) printf("輸入有誤，請(qǐng)重新輸入頂點(diǎn)數(shù)與邊的條

10、數(shù)！n"); scanf("%d%d",&graph->vexnum ,&graph->edgenum ); for(i=1;i<=graph->vexnum;i+) printf("請(qǐng)輸入第%d個(gè)頂點(diǎn)的信息：n",i); scanf("%s",&graph->adjlist ); graph->adjlist i.num =i; graph->adjlisti.firstedge=NULL; graph->adjlist i.markV

11、=0; for(i=1;i<=graph->edgenum;i+) p=(EdgeNode *)malloc(sizeof(EdgeNode); printf("請(qǐng)輸入每條邊依附的兩個(gè)頂點(diǎn)(用頂點(diǎn)的編號(hào)表示)n"); scanf("%d %d",&p->ivex,&p->jvex); while(p->ivex =p->jvex|p->ivex<1|p->ivex >graph->vexnum |p->jvex <1|p->jvex >graph-&

12、gt;vexnum ) printf("輸入的頂點(diǎn)有誤，請(qǐng)重新輸入!n"); scanf("%d%d",&p->ivex,&p->jvex); p->ilink =p->jlink =NULL; if(graph->adjlist p->ivex .firstedge=NULL ) graph->adjlist p->ivex .firstedge =p; else q=graph->adjlist p->ivex .firstedge ; while(q!=NULL) e=q;

13、 if(q->ivex =p->ivex ) q=q->ilink ; else q=q->jlink ; if(e->ivex =p->ivex ) e->ilink =p; else e->jlink =p; if(graph->adjlist p->jvex .firstedge=NULL ) graph->adjlist p->jvex .firstedge =p; else q=graph->adjlist p->jvex .firstedge ; while(q!=NULL) e=q; if(q-&

14、gt;ivex =p->ivex ) q=q->ilink ; else q=q->jlink ; if(e->ivex =p->ivex ) e->ilink =p; else e->jlink =p; void SetMark(Graph *graph) int i; for(i=1;i<=graph->vexnum ;i+) graph->adjlist i.markV =0;void DFS(Graph *graph,int v) EdgeNode *p; printf("%d ",v); graph-&g

15、t;adjlist v.markV =1; p=graph->adjlist v.firstedge ; while(p!=NULL) if(p->ivex =v) if(graph->adjlist p->jvex .markV =0) printf("<%d,%d>n",p->ivex ,p->jvex ); DFS(graph,p->jvex ); p=p->ilink ; else if(graph->adjlist p->ivex.markV =0) printf("<%d,%

16、d>n",p->jvex ,p->ivex ); DFS(graph,p->ivex ); p=p->jlink ; void BFS(Graph *graph,int u) LinkQueue Q; EdgeNode *p; InitQueue(&Q); printf("%d ",u); graph->adjlist u.markV =1; EnQueue(&Q,u); while(Q.front !=Q.rear ) DeQueue(&Q,&u); p=graph->adjlist u.

17、firstedge ; while( p!=NULL) if(p->ivex =u) if(graph->adjlist p->jvex .markV =0) EnQueue(&Q,p->jvex ); graph->adjlist p->jvex .markV =1; printf("<%d,%d>n",p->ivex ,p->jvex ); printf("%d ",p->jvex ); p=p->ilink ; else if(graph->adjlist p-&

18、gt;ivex .markV =0) EnQueue(&Q,p->ivex ); graph->adjlist p->ivex .markV =1; printf("<%d,%d>n",p->jvex ,p->ivex ); printf("%d ",p->ivex ); p=p->jlink ; void main() int u,v; Graph graph; char order; Initilized(&graph); CreateGraph(&graph); printf("輸入命令（C/c：重新創(chuàng)建連通無(wú)向圖T/t深度遍歷廣度遍歷E/e：結(jié)束）：n"); scanf("%s",&order); while(order!='E'&&order!='e')