圖的深度廣度優(yōu)先遍歷操作代碼

1、一、實驗?zāi)康?掌握圖的各種存儲結(jié)構(gòu)，特別要熟練掌握鄰接矩陣和鄰接表存儲結(jié)構(gòu)；2遍歷是圖各種應(yīng)用的算法的基礎(chǔ)，要熟練掌握圖的深度優(yōu)先遍歷和寬度優(yōu)先遍歷算法，復(fù)習(xí)棧和隊列的應(yīng)用；3掌握圖的各種應(yīng)用的算法：圖的連通性、連通分量和最小生成樹、拓?fù)渑判颉㈥P(guān)鍵路徑。二、實驗內(nèi)容實驗內(nèi)容1*圖的遍歷問題描述許多涉及圖上操作的算法都是以圖的遍歷為基礎(chǔ)的。寫一個程序，演示在連通無向圖上遍歷全部頂點?；疽蠼D的鄰接表的存儲結(jié)構(gòu)，實現(xiàn)無向圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷。以用戶指定的頂點為起點，分別輸出每種遍歷下的頂點訪問序列。實現(xiàn)提示設(shè)圖的頂點不超過30個，每個頂點用一個編號表示（如果一個圖有N個頂點，則它們

2、的編號分別為1，2，N）。通過輸入圖的全部邊輸入一個圖，每條邊是兩個頂點編號對，可以對邊依附頂點編號的輸入順序作出限制（例如從小到大）。編程思路 首先圖的創(chuàng)建，采用鄰接表建立，逆向插入到單鏈表中，特別注意無向是對稱插入結(jié)點，且要把輸入的字符在頂點數(shù)組中定位（LocateVex(Graph G,char *name)，以便后來的遍歷操作，深度遍歷算法采用遞歸調(diào)用，其中最主要的是NextAdjVex(Graph G, int v, int w) ；FirstAdjVex（）函數(shù)的書寫，依次遞歸下去，廣度遍歷用隊列的輔助。程序代碼 頭文件：#include<stdio.h>#includ

3、e<stdlib.h>#define MAX_VERTEX_NUM 30#define MAX_QUEUE_NUMBER 30#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2#define TRUE 1#define FALSE 0typedef int Status;typedef int InfoType;typedef int Status;/* 定義弧的結(jié)構(gòu)*/typedef struct ArcNode int adjvex; /*該邊所指向的頂點的位置*/ struct ArcNode

4、 *nextarc; /*指向下一條邊的指針*/ InfoType info; /*該弧相關(guān)信息的指針*/ArcNode; /*定義頂點的結(jié)構(gòu)*/typedef struct VNode char data40; /*頂點信息*/ ArcNode *firstarc; /*指向第一條依附該頂點的弧的指針*/VNode,AdjListMAX_VERTEX_NUM;/*定義圖的結(jié)構(gòu)*/typedef struct AdjList vertices; int vexnum,arcnum; /*圖的當(dāng)前頂點數(shù)和弧數(shù)*/ int kind; /*圖的類型標(biāo)志*/Graph;/*定義隊列的結(jié)構(gòu)*/type

5、def structint *elem;int front, rear;Queue;/*功能選擇*/void MenuSelect(int w);/*頂點定位*/int LocateVex(Graph G,char *name);/*創(chuàng)建無向圖*/void CreateGraph(Graph &G);/*求第一個頂點*/int FirstAdjVex(Graph G, int v);/*求下一個頂點*/int NextAdjVex(Graph G, int v, int w);/*深度遞歸*/void DFS(Graph G, int v) ;/*深度遍歷*/void DFSTrave

6、l(Graph G,int v);/*廣度遍歷*/void BFSTraverse(Graph G,char *name);/*初始化隊列*/Status InitQueue(Queue &Q);/*判空*/Status EmptyQueue(Queue Q);/*進(jìn)隊*/Status EnQueue(Queue &Q, int e);/*出隊*/Status DeQueue(Queue &Q, int &e);實現(xiàn)文件：#include <stdio.h>#include"malloc.h"#include "tuhe

7、ad.h"#include "stdlib.h"#include "string.h"bool visitedMAX_VERTEX_NUM;/* 頂點定位 */int LocateVex(Graph G,char *name)int i;for(i=1;i<=G.vexnum;i+) /從1號位置開始存儲if(strcmp(name,G.verticesi.data)=0) /相等則找到，返回位序return i;return -1;/* 創(chuàng)建無向圖 */void CreateGraph(Graph &G)ArcNode *p;c

8、har name110,name210;int i,j,k;printf(" 請輸入頂點數(shù),按回車鍵結(jié)束：");scanf("%d",&G.vexnum); printf(" 請輸入弧數(shù),按回車鍵結(jié)束：");scanf("%d",&G.arcnum);printf(" 請依次輸入頂點名（用空格分開且字符小于10）,按回車鍵結(jié)束：n"); printf(" ");for(i=1;i<=G.vexnum;i+) /從1號位置開始存儲 scanf("

9、%s",G.verticesi.data); /從一號位置開始初始化G.verticesi.firstarc=NULL; printf("nnnn"); printf(" 輸入小提示n"); printf(" &&&&1 為避免輸入遺漏，最好從選擇任意一點，輸入所有相鄰邊n"); printf(" &&&&2 輸入邊時格式(用空格分開，即格式為頂點（空格）頂點（空格)）n"); printf(" 輸入小提示nnnn");f

10、or(k=0;k<G.arcnum;k+)printf("請輸入相鄰的兩個頂點,按回車鍵結(jié)束：");scanf("%s%s",name1,name2);i=LocateVex(G,name1); /返回位序j=LocateVex(G,name2); p=(ArcNode *)malloc(sizeof(ArcNode); /申請邊節(jié)點p->adjvex=j; /插入到鄰接表中，注意此處為逆向插入到單鏈表中 p->nextarc=G.verticesi.firstarc;G.verticesi.firstarc=p; /無向圖，注意是對稱

11、插入結(jié)點 p=(ArcNode *)malloc(sizeof(ArcNode); p->adjvex=i; p->nextarc=G.verticesj.firstarc;G.verticesj.firstarc=p; /* 求第一個頂點 */ int FirstAdjVex(Graph G, int v) ArcNode *p; if(v>=1 && v<=G.vexnum) p=G.verticesv.firstarc; if(p->nextarc=NULL) return 0; else return (p->nextarc->

12、adjvex); /返回第一個頂點字符 return -1; /* 求下一個頂點 */int NextAdjVex(Graph G, int v, int w) /在圖G中尋找第v個頂點的相對于w的下一個鄰接頂點 ArcNode *p; if(v>=1 && v<=G.vexnum && w>=1 && w<=G.vexnum) p=G.verticesv.firstarc; while(p->adjvex!=w) p=p->nextarc; /在頂點v的弧鏈中找到頂點w if(p->nextarc!=N

13、ULL) return 0; /若已是最后一個頂點，返回0 else return(p->nextarc->adjvex); /返回下一個鄰接頂點的序號 return -1;/* 深度遞歸 */void DFS(Graph G, int v) int w; ArcNode *p; visitedv=1; printf("%s ",G.verticesv.data); /訪問第v個頂點 p=G.verticesv.firstarc; /p為依附頂點的第一條邊 while (p!=NULL) w=p->adjvex; if(visitedw=0) DFS(G,

14、w); p=p->nextarc; /下移指針 /* 深度遍歷 */void DFSTravel(Graph G,int v)for(int i=1;i<=G.vexnum;i+) visitedi=0; int w; ArcNode *p; visitedv=1; printf("%s ",G.verticesv.data); /訪問第v個頂點 p=G.verticesv.firstarc; while (p!=NULL) w=p->adjvex; if(visitedw=0) DFS(G,w); p=p->nextarc; /* 初始化隊列 */

15、 Status InitQueue(Queue &Q)Q.elem = new intMAX_QUEUE_NUMBER;Q.front = Q.rear = 0; return OK；Status EmptyQueue(Queue Q)if(Q.front=Q.rear)return 0;else return 1;/* 進(jìn)隊列 */Status EnQueue(Queue &Q, int e)if(Q.rear + 1)%MAX_QUEUE_NUMBER != Q.front)Q.elemQ.rear = e;else;Q.rear = (Q.rear + 1)%MAX_QU

16、EUE_NUMBER; return OK； /* 出隊列 */Status DeQueue(Queue &Q, int &e)if(Q.rear != Q.front)e = Q.elemQ.front;else ;Q.front = (Q.front+1)%MAX_QUEUE_NUMBER; return OK；/* 廣度遍歷 */void BFSTraverse(Graph G,char *name)ArcNode *p;int v,w,u,k=0; Queue Q;int visited20;for(v=1;v<=G.vexnum;v+) /初始化visitedv

17、=0;InitQueue(Q);for(v=LocateVex(G,name);k!=2;v=(v+1)%(G.vexnum-1) /v為輸入的字符轉(zhuǎn)化的位序if(v+1=LocateVex(G,name) /從v開始走完圖的所有頂點k+;if(visitedv=0)visitedv=1;printf("%s ",G.verticesv.data); /訪問第v個頂點 EnQueue(Q,v); / 進(jìn)隊 while(EmptyQueue(Q)!=0)DeQueue(Q,u); /出隊p=G.verticesu.firstarc;while(p!=NULL)w=p->

18、adjvex; /p邊的下一個頂點if(visitedw=0)printf("%s ",G.verticesw.data);visitedw=1;EnQueue(Q,w);p=p->nextarc; /下移指針 主文件：#include <stdio.h>#include"malloc.h"#include "tuhead.h"#include "stdlib.h"#include "string.h"/* 界面控制 */void main() printf("n#

19、圖的遍歷 #n"); printf("n $n"); printf("n"); printf(" 1 - 圖的創(chuàng)建n"); printf(" 2 - 圖的深度優(yōu)先遍歷n"); printf(" 3 - 圖的廣度優(yōu)先遍歷n"); printf(" 0 - 退出n");printf("n$n"); printf("n"); printf("請輸入選擇的操作代碼（0-3）按回車鍵結(jié)束n"); MenuSelect(1);/* 功能選擇 */ void MenuSelect(int w) int select,done; int v; Gra