圖的遍歷操作實(shí)驗(yàn)報(bào)告

1、實(shí)驗(yàn)三、圖的遍歷操作一、 目的掌握有向圖和無向圖的概念；掌握鄰接矩陣和鄰接鏈表建立圖的存儲(chǔ)結(jié)構(gòu)；掌握DFS及BFS對(duì)圖的遍歷操作；了解圖結(jié)構(gòu)在人工智能、工程等領(lǐng)域的廣泛應(yīng)用。二、 要求采用鄰接矩陣和鄰接鏈表作為圖的存儲(chǔ)結(jié)構(gòu)，完成有向圖和無向圖的DFS和BFS操作。三、 DFS和BFS 的基本思想深度優(yōu)先搜索法DFS的基本思想：從圖G中某個(gè)頂點(diǎn)Vo出發(fā)，首先訪問Vo，然后選擇一個(gè)與Vo相鄰且沒被訪問過的頂點(diǎn)Vi訪問，再從Vi出發(fā)選擇一個(gè)與Vi相鄰且沒被訪問過的頂點(diǎn)Vj訪問，依次繼續(xù)。如果當(dāng)前被訪問過的頂點(diǎn)的所有鄰接頂點(diǎn)都已被訪問，則回退到已被訪問的頂點(diǎn)序列中最后一個(gè)擁有未被訪問的相鄰頂點(diǎn)的頂點(diǎn)W

2、，從W出發(fā)按同樣方法向前遍歷。直到圖中所有的頂點(diǎn)都被訪問。廣度優(yōu)先算法BFS的基本思想：從圖G中某個(gè)頂點(diǎn)Vo出發(fā)，首先訪問Vo，然后訪問與Vo相鄰的所有未被訪問過的頂點(diǎn)V1，V2，Vt；再依次訪問與V1，V2，Vt相鄰的起且未被訪問過的的所有頂點(diǎn)。如此繼續(xù)，直到訪問完圖中的所有頂點(diǎn)。四、 示例程序1 鄰接矩陣作為存儲(chǔ)結(jié)構(gòu)的程序示例#include"stdio.h"#include"stdlib.h"#define MaxVertexNum 100 /定義最大頂點(diǎn)數(shù)typedef struct char vexsMaxVertexNum; /頂點(diǎn)表 int

3、 edgesMaxVertexNumMaxVertexNum; /鄰接矩陣，可看作邊表 int n,e; /圖中的頂點(diǎn)數(shù)n和邊數(shù)eMGraph; /用鄰接矩陣表示的圖的類型/=建立鄰接矩陣=void CreatMGraph(MGraph *G) int i,j,k; char a; printf("Input VertexNum(n) and EdgesNum(e): "); scanf("%d,%d",&G->n,&G->e); /輸入頂點(diǎn)數(shù)和邊數(shù) scanf("%c",&a); printf(&

4、quot;Input Vertex string:"); for(i=0;i<G->n;i+) scanf("%c",&a); G->vexsi=a; /讀入頂點(diǎn)信息，建立頂點(diǎn)表 for(i=0;i<G->n;i+)for(j=0;j<G->n;j+)G->edgesij=0; /初始化鄰接矩陣 printf("Input edges,Creat Adjacency Matrixn"); for(k=0;k<G->e;k+) /讀入e條邊，建立鄰接矩陣 scanf("

5、%d%d",&i,&j); /輸入邊（Vi，Vj）的頂點(diǎn)序號(hào) G->edgesij=1; G->edgesji=1; /若為無向圖，矩陣為對(duì)稱矩陣；若建立有向圖，去掉該條語句 /=定義標(biāo)志向量，為全局變量=typedef enumFALSE,TRUE Boolean;Boolean visitedMaxVertexNum;/=DFS：深度優(yōu)先遍歷的遞歸算法=void DFSM(MGraph *G,int i) /以Vi為出發(fā)點(diǎn)對(duì)鄰接矩陣表示的圖G進(jìn)行DFS搜索，鄰接矩陣是0，1矩陣 int j; printf("%c",G->ve

6、xsi); /訪問頂點(diǎn)Vi visitedi=TRUE; /置已訪問標(biāo)志 for(j=0;j<G->n;j+) /依次搜索Vi的鄰接點(diǎn)if(G->edgesij=1 && ! visitedj) DFSM(G,j); /（Vi，Vj）E，且Vj未訪問過，故Vj為新出發(fā)點(diǎn)void DFS(MGraph *G) int i; for(i=0;i<G->n;i+)visitedi=FALSE; /標(biāo)志向量初始化 for(i=0;i<G->n;i+)if(!visitedi) /Vi未訪問過 DFSM(G,i); /以Vi為源點(diǎn)開始DFS搜索/

7、=BFS：廣度優(yōu)先遍歷=void BFS(MGraph *G,int k) /以Vk為源點(diǎn)對(duì)用鄰接矩陣表示的圖G進(jìn)行廣度優(yōu)先搜索 int i,j,f=0,r=0; int cqMaxVertexNum; /定義隊(duì)列 for(i=0;i<G->n;i+)visitedi=FALSE; /標(biāo)志向量初始化 for(i=0;i<G->n;i+)cqi=-1; /隊(duì)列初始化 printf("%c",G->vexsk); /訪問源點(diǎn)Vk visitedk=TRUE; cqr=k; /Vk已訪問，將其入隊(duì)。注意，實(shí)際上是將其序號(hào)入隊(duì) while(cqf!=-

8、1) /隊(duì)非空則執(zhí)行 i=cqf; f=f+1; /Vf出隊(duì) for(j=0;j<G->n;j+) /依次Vi的鄰接點(diǎn)Vj if(G->edgesij=1 && !visitedj) /Vj未訪問 printf("%c",G->vexsj); /訪問Vj visitedj=TRUE; r=r+1; cqr=j; /訪問過Vj入隊(duì) /=main=void main() int i; MGraph *G; G=(MGraph *)malloc(sizeof(MGraph); /為圖G申請(qǐng)內(nèi)存空間 CreatMGraph(G); /建立鄰接

9、矩陣 printf("Print Graph DFS: "); DFS(G); /深度優(yōu)先遍歷 printf("n"); printf("Print Graph BFS: "); BFS(G,3); /以序號(hào)為3的頂點(diǎn)開始廣度優(yōu)先遍歷 printf("n");執(zhí)行順序：V6V4V5V7V2V3V1V0Vo圖G的示例Input VertexNum(n) and EdgesNum(e): 8，9Input Vertex string: 01234567Input edges,Creat Adjacency Matrix

10、0 10 21 31 42 52 63 74 75 6Print Graph DFS:01374256Print Graph BFS:317042562 鄰接鏈表作為存儲(chǔ)結(jié)構(gòu)程序示例#include"stdio.h"#include"stdlib.h"#define MaxVertexNum 50 /定義最大頂點(diǎn)數(shù)typedef struct node /邊表結(jié)點(diǎn) int adjvex; /鄰接點(diǎn)域 struct node *next; /鏈域EdgeNode;typedef struct vnode /頂點(diǎn)表結(jié)點(diǎn) char vertex; /頂點(diǎn)域 E

11、dgeNode *firstedge; /邊表頭指針VertexNode;typedef VertexNode AdjListMaxVertexNum; /AdjList是鄰接表類型typedef struct AdjList adjlist; /鄰接表 int n,e; /圖中當(dāng)前頂點(diǎn)數(shù)和邊數(shù) ALGraph; /圖類型/=建立圖的鄰接表=void CreatALGraph(ALGraph *G) int i,j,k; char a; EdgeNode *s; /定義邊表結(jié)點(diǎn) printf("Input VertexNum(n) and EdgesNum(e): ");

12、scanf("%d,%d",&G->n,&G->e); /讀入頂點(diǎn)數(shù)和邊數(shù) scanf("%c",&a); printf("Input Vertex string:"); for(i=0;i<G->n;i+) /建立邊表 scanf("%c",&a);G->adjlisti.vertex=a; /讀入頂點(diǎn)信息G->adjlisti.firstedge=NULL; /邊表置為空表 printf("Input edges,Creat Adja

13、cency Listn"); for(k=0;k<G->e;k+) /建立邊表 scanf("%d%d",&i,&j); /讀入邊（Vi，Vj）的頂點(diǎn)對(duì)序號(hào)s=(EdgeNode *)malloc(sizeof(EdgeNode); /生成邊表結(jié)點(diǎn)s->adjvex=j; /鄰接點(diǎn)序號(hào)為js->next=G->adjlisti.firstedge;G->adjlisti.firstedge=s; /將新結(jié)點(diǎn)*S插入頂點(diǎn)Vi的邊表頭部s=(EdgeNode *)malloc(sizeof(EdgeNode); s-

14、>adjvex=i; /鄰接點(diǎn)序號(hào)為is->next=G->adjlistj.firstedge; G->adjlistj.firstedge=s; /將新結(jié)點(diǎn)*S插入頂點(diǎn)Vj的邊表頭部 /=定義標(biāo)志向量，為全局變量=typedef enumFALSE,TRUE Boolean;Boolean visitedMaxVertexNum;/=DFS：深度優(yōu)先遍歷的遞歸算法=void DFSM(ALGraph *G,int i) /以Vi為出發(fā)點(diǎn)對(duì)鄰接鏈表表示的圖G進(jìn)行DFS搜索 EdgeNode *p; printf("%c",G->adjlist

15、i.vertex); /訪問頂點(diǎn)Vi visitedi=TRUE; /標(biāo)記Vi已訪問 p=G->adjlisti.firstedge; /取Vi邊表的頭指針 while(p) /依次搜索Vi的鄰接點(diǎn)Vj，這里j=p->adjvexif(! visitedp->adjvex) /若Vj尚未被訪問 DFSM(G,p->adjvex); /則以Vj為出發(fā)點(diǎn)向縱深搜索p=p->next; /找Vi的下一個(gè)鄰接點(diǎn) void DFS(ALGraph *G) int i; for(i=0;i<G->n;i+)visitedi=FALSE; /標(biāo)志向量初始化 for(

16、i=0;i<G->n;i+)if(!visitedi) /Vi未訪問過 DFSM(G,i); /以Vi為源點(diǎn)開始DFS搜索/=BFS：廣度優(yōu)先遍歷=void BFS(ALGraph *G,int k) /以Vk為源點(diǎn)對(duì)用鄰接鏈表表示的圖G進(jìn)行廣度優(yōu)先搜索 int i,f=0,r=0; EdgeNode *p; int cqMaxVertexNum; /定義FIFO隊(duì)列 for(i=0;i<G->n;i+)visitedi=FALSE; /標(biāo)志向量初始化 for(i=0;i<=G->n;i+)cqi=-1; /初始化標(biāo)志向量 printf("%c&q

17、uot;,G->adjlistk.vertex); /訪問源點(diǎn)Vk visitedk=TRUE; cqr=k; /Vk已訪問，將其入隊(duì)。注意，實(shí)際上是將其序號(hào)入隊(duì) while(cqf!=-1) 隊(duì)列非空則執(zhí)行i=cqf; f=f+1; /Vi出隊(duì)p=G->adjlisti.firstedge; /取Vi的邊表頭指針while(p) /依次搜索Vi的鄰接點(diǎn)Vj（令p->adjvex=j） if(!visitedp->adjvex) /若Vj未訪問過printf("%c",G->adjlistp->adjvex.vertex); /訪問Vjv

18、isitedp->adjvex=TRUE;r=r+1; cqr=p->adjvex; /訪問過的Vj入隊(duì) p=p->next; /找Vi的下一個(gè)鄰接點(diǎn) /endwhile/=主函數(shù)=void main() int i; ALGraph *G; G=(ALGraph *)malloc(sizeof(ALGraph); CreatALGraph(G); printf("Print Graph DFS: "); DFS(G); printf("n"); printf("Print Graph BFS: "); BFS(G,

19、3); printf("n");執(zhí)行順序：Input VertexNum(n) and EdgesNum(e): 8，9Input Vertex string: 01234567V6V4V5V7V2V3V1V0Vo圖G的示例Input edges,Creat Adjacency List0 10 21 31 42 52 63 74 75 6Print Graph DFS:02651473Print Graph BFS:37140265五、 修改后的代碼1鄰接矩陣作為存儲(chǔ)結(jié)構(gòu)的程序#include"stdio.h"#include"stdlib.

20、h"#define MaxVertexNum 100 /定義最大頂點(diǎn)數(shù)typedef struct char vexsMaxVertexNum; /頂點(diǎn)表 int edgesMaxVertexNumMaxVertexNum; /鄰接矩陣，可看作邊表 int n,e; /圖中的頂點(diǎn)數(shù)n和邊數(shù)eMGraph; /用鄰接矩陣表示的圖的類型/=建立鄰接矩陣=void CreatMGraph(MGraph *G) int i,j,k; char a; printf("Input VertexNum(n) and EdgesNum(e): "); scanf("%d

21、,%d",&G->n,&G->e); /輸入頂點(diǎn)數(shù)和邊數(shù) scanf("%c",&a); printf("Input Vertex string:"); for(i=0;i<G->n;i+) scanf("%c",&a); G->vexsi=a; /讀入頂點(diǎn)信息，建立頂點(diǎn)表 for(i=0;i<G->n;i+)for(j=0;j<G->n;j+)G->edgesij=0; /初始化鄰接矩陣 printf("Input edg

22、es,Creat Adjacency Matrixn"); for(k=0;k<G->e;k+) /讀入e條邊，建立鄰接矩陣 scanf("%d%d",&i,&j); /輸入邊（Vi，Vj）的頂點(diǎn)序號(hào) G->edgesij=1; G->edgesji=1; /若為無向圖，矩陣為對(duì)稱矩陣；若建立有向圖，去掉該條語句 /=定義標(biāo)志向量，為全局變量=typedef enumFALSE,TRUE Boolean;Boolean visitedMaxVertexNum;/=DFS：深度優(yōu)先遍歷的遞歸算法=void DFSM(MGrap

23、h *G,int i) /以Vi為出發(fā)點(diǎn)對(duì)鄰接矩陣表示的圖G進(jìn)行DFS搜索，鄰接矩陣是0，1矩陣 int j; printf("%c",G->vexsi); /訪問頂點(diǎn)Vi visitedi=TRUE; /置已訪問標(biāo)志 for(j=0;j<G->n;j+) /依次搜索Vi的鄰接點(diǎn)if(G->edgesij=1 && ! visitedj) DFSM(G,j); /（Vi，Vj）E，且Vj未訪問過，故Vj為新出發(fā)點(diǎn)void DFS(MGraph *G) int i; for(i=0;i<G->n;i+)visitedi=FA

24、LSE; /標(biāo)志向量初始化 for(i=0;i<G->n;i+)if(!visitedi) /Vi未訪問過 DFSM(G,i); /以Vi為源點(diǎn)開始DFS搜索/=BFS：廣度優(yōu)先遍歷=void BFS(MGraph *G,int k) /以Vk為源點(diǎn)對(duì)用鄰接矩陣表示的圖G進(jìn)行廣度優(yōu)先搜索 int i,j,f=0,r=0; int cqMaxVertexNum; /定義隊(duì)列 for(i=0;i<G->n;i+)visitedi=FALSE; /標(biāo)志向量初始化 for(i=0;i<G->n;i+)cqi=-1; /隊(duì)列初始化 printf("%c&qu

25、ot;,G->vexsk); /訪問源點(diǎn)Vk visitedk=TRUE; cqr=k; /Vk已訪問，將其入隊(duì)。注意，實(shí)際上是將其序號(hào)入隊(duì) while(cqf!=-1) /隊(duì)非空則執(zhí)行 i=cqf; f=f+1; /Vf出隊(duì) for(j=0;j<G->n;j+) /依次Vi的鄰接點(diǎn)Vj if(G->edgesij=1 && !visitedj) /Vj未訪問 printf("%c",G->vexsj); /訪問Vj visitedj=TRUE; r=r+1; cqr=j; /訪問過Vj入隊(duì) /=main=void main()

26、 MGraph *G; G=(MGraph *)malloc(sizeof(MGraph); /為圖G申請(qǐng)內(nèi)存空間 CreatMGraph(G); /建立鄰接矩陣 printf("Print Graph DFS: "); DFS(G); /深度優(yōu)先遍歷 printf("n"); printf("Print Graph BFS: "); BFS(G,3); /以序號(hào)為3的頂點(diǎn)開始廣度優(yōu)先遍歷 printf("n");2鄰接鏈表作為存儲(chǔ)結(jié)構(gòu)程序#include"stdio.h"#include&qu

27、ot;stdlib.h"#define MaxVertexNum 50 /定義最大頂點(diǎn)數(shù)typedef struct node /邊表結(jié)點(diǎn) int adjvex; /鄰接點(diǎn)域 struct node *next; /鏈域EdgeNode;typedef struct vnode /頂點(diǎn)表結(jié)點(diǎn) char vertex; /頂點(diǎn)域 EdgeNode *firstedge; /邊表頭指針VertexNode;typedef VertexNode AdjListMaxVertexNum; /AdjList是鄰接表類型typedef struct AdjList adjlist; /鄰接表 i

28、nt n,e; /圖中當(dāng)前頂點(diǎn)數(shù)和邊數(shù) ALGraph; /圖類型/=建立圖的鄰接表=void CreatALGraph(ALGraph *G) int i,j,k; char a; EdgeNode *s; /定義邊表結(jié)點(diǎn) printf("Input VertexNum(n) and EdgesNum(e): "); scanf("%d,%d",&G->n,&G->e); /讀入頂點(diǎn)數(shù)和邊數(shù) scanf("%c",&a); printf("Input Vertex string:&quo

29、t;); for(i=0;i<G->n;i+) /建立邊表 scanf("%c",&a);G->adjlisti.vertex=a; /讀入頂點(diǎn)信息G->adjlisti.firstedge=NULL; /邊表置為空表 printf("Input edges,Creat Adjacency Listn"); for(k=0;k<G->e;k+) /建立邊表 scanf("%d%d",&i,&j); /讀入邊（Vi，Vj）的頂點(diǎn)對(duì)序號(hào)s=(EdgeNode *)malloc(s

30、izeof(EdgeNode); /生成邊表結(jié)點(diǎn)s->adjvex=j; /鄰接點(diǎn)序號(hào)為js->next=G->adjlisti.firstedge;G->adjlisti.firstedge=s; /將新結(jié)點(diǎn)*S插入頂點(diǎn)Vi的邊表頭部s=(EdgeNode *)malloc(sizeof(EdgeNode); s->adjvex=i; /鄰接點(diǎn)序號(hào)為is->next=G->adjlistj.firstedge; G->adjlistj.firstedge=s; /將新結(jié)點(diǎn)*S插入頂點(diǎn)Vj的邊表頭部 /=定義標(biāo)志向量，為全局變量=typedef

31、enumFALSE,TRUE Boolean;Boolean visitedMaxVertexNum;/=DFS：深度優(yōu)先遍歷的遞歸算法=void DFSM(ALGraph *G,int i) /以Vi為出發(fā)點(diǎn)對(duì)鄰接鏈表表示的圖G進(jìn)行DFS搜索 EdgeNode *p; printf("%c",G->adjlisti.vertex); /訪問頂點(diǎn)Vi visitedi=TRUE; /標(biāo)記Vi已訪問 p=G->adjlisti.firstedge; /取Vi邊表的頭指針 while(p) /依次搜索Vi的鄰接點(diǎn)Vj，這里j=p->adjvexif(! vis

32、itedp->adjvex) /若Vj尚未被訪問 DFSM(G,p->adjvex); /則以Vj為出發(fā)點(diǎn)向縱深搜索p=p->next; /找Vi的下一個(gè)鄰接點(diǎn) void DFS(ALGraph *G) int i; for(i=0;i<G->n;i+)visitedi=FALSE; /標(biāo)志向量初始化 for(i=0;i<G->n;i+)if(!visitedi) /Vi未訪問過 DFSM(G,i); /以Vi為源點(diǎn)開始DFS搜索DFSM(G,i);/=BFS：廣度優(yōu)先遍歷=void BFS(ALGraph *G,int k) /以Vk為源點(diǎn)對(duì)用鄰接鏈表表示的圖G進(jìn)行廣度優(yōu)先搜索 int i,f=0,r=0; EdgeNode *p; int cqMaxVerte