圖的遍歷數(shù)據(jù)結(jié)構(gòu)實驗報告

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

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

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

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

5、之間一條最短路徑，否則返回其他信息。ADT Graph （2）本程序包含三個模塊： 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è)計#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("請輸入連通無向圖的頂點個數(shù)和邊的條數(shù)：n"); scanf("%d %d",&graph->vexnum,&graph->edgenum); while(graph->vexnum>MAX|graph->edgenum >(graph->vexnum *(graph->vexnum -1)/2) printf("輸入有誤，請重新輸入頂點數(shù)與邊的條

10、數(shù)！n"); scanf("%d%d",&graph->vexnum ,&graph->edgenum ); for(i=1;i<=graph->vexnum;i+) printf("請輸入第%d個頂點的信息：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("請輸入每條邊依附的兩個頂點(用頂點的編號表示)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("輸入的頂點有誤，請重新輸入!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)建連通無向圖T/t深度遍歷廣度遍歷E/e：結(jié)束）：n"); scanf("%s",&order); while(order!='E'&&order!='e')