實(shí)驗(yàn)五圖操作實(shí)現(xiàn).doc

實(shí)驗(yàn)五 圖操作實(shí)現(xiàn)實(shí)驗(yàn)日期： 2017 年 4 月 27 日 實(shí)驗(yàn)?zāi)康募耙?. 熟練掌握?qǐng)D的鄰接矩陣和鄰接表的存儲(chǔ)方式；2. 實(shí)現(xiàn)圖的一些基本運(yùn)算，特別是深度優(yōu)先遍歷和廣度優(yōu)先遍歷；實(shí)驗(yàn)內(nèi)容用鄰接矩陣法建一個(gè)無(wú)向連通圖（頂點(diǎn)信息為順序字母A，B，C，D.，而非鍵盤輸入），分別用dfs（深度優(yōu)先搜索）和bfs(廣度優(yōu)先搜索)遍歷，輸出圖中頂點(diǎn)信息并驗(yàn)證。鄰接矩陣圖類型定義：#define MAX 40 typedef char vexType; /*頂點(diǎn)類型*/ typedef struct vexType vexMAX; int arcsMAXMAX; int vn,en; MGraph; 訪問(wèn)標(biāo)記數(shù)組定義：int visitedMAX; /*值為0時(shí)對(duì)應(yīng)頂點(diǎn)未被訪問(wèn)，值為1時(shí)對(duì)應(yīng)頂點(diǎn)已被訪問(wèn) */順序存儲(chǔ)的循環(huán)隊(duì)列類型定義：typedef int datatype; /*隊(duì)列元素為圖的頂點(diǎn)下標(biāo),int型*/typedef struct node datatype dataMAX; int front, rear; SeqQueue; /*順序存儲(chǔ)的循環(huán)隊(duì)列類型*/任務(wù)1自定義函數(shù)庫(kù)文件Queue.h，完成隊(duì)列的相關(guān)操作。2創(chuàng)建一個(gè)程序文件sy15.cpp，自定義相應(yīng)函數(shù)完成以下操作：（1）void createGraph(MGraph *g) /*建鄰接矩陣存儲(chǔ)的無(wú)向圖*/（2）void visit(MGraph *g,int v) /*訪問(wèn)v號(hào)頂點(diǎn)*/（3）void dfs(MGraph *g,int v) /*鄰接矩陣存儲(chǔ)的圖的深度優(yōu)先搜索*/（4）void bfs(MGraph *g,int v) /*鄰接矩陣存儲(chǔ)的圖的廣度優(yōu)先搜索*/3回答下列問(wèn)題（1）現(xiàn)有定義：MGraph *g，并且g指針指向的無(wú)向圖已創(chuàng)建完成，請(qǐng)寫出該圖遍歷前需初始化visited數(shù)組的C程序語(yǔ)句。for (i = 0; i g.vn; i+) /*標(biāo)記數(shù)組初始化*/visitedi = 0;（2）定義函數(shù)int count (MGraph *g)統(tǒng)計(jì)非連通圖的連同分量個(gè)數(shù)。（說(shuō)明：借助遍歷算法實(shí)現(xiàn)）int count (MGraph *g) int i, m=0; for(i=0; ivn; i+) if(visitedi=0) m+; dfs(g, i); return m;4自定義函數(shù)庫(kù)文件Queue.h 與sy15.cpp源程序清單（含必要的注釋）Queue.h:#includetypedef int datatype; /*隊(duì)列元素為圖的頂點(diǎn)下標(biāo),int型*/typedef struct node datatype dataMAX;int front, rear; SeqQueue; /*順序存儲(chǔ)的循環(huán)隊(duì)列類型*/void InitQueue(SeqQueue *Q); /*初始化隊(duì)列*/void EnQueue(SeqQueue *Q, int v); /*入隊(duì)*/datatype DeQueue(SeqQueue *Q); /*出隊(duì)*/int EmptyQueue(SeqQueue *Q); /*判隊(duì)空*/int FullQueue(SeqQueue *Q); /*判隊(duì)滿*/void InitQueue(SeqQueue *Q) Q-front = Q-rear = 0;void EnQueue(SeqQueue *Q, int v) if (FullQueue(Q) printf(隊(duì)列已滿!); /*判隊(duì)滿*/return;Q-rear = (Q-rear + 1) % MAX; /*入隊(duì)*/Q-dataQ-rear = v;datatype DeQueue(SeqQueue *Q) if (EmptyQueue(Q) printf(隊(duì)列為空!); /*判隊(duì)空*/return -1;Q-front = (Q-front + 1) % MAX; /*出隊(duì)*/return Q-dataQ-front;int EmptyQueue(SeqQueue *Q) return Q-front = Q-rear;int FullQueue(SeqQueue *Q) return (Q-rear + 1) % MAX = Q-front;sy5.cpp:#define MAX 40#includeQueue.hint visitedMAX; /*值為0時(shí)對(duì)應(yīng)頂點(diǎn)未被訪問(wèn)，值為1時(shí)對(duì)應(yīng)頂點(diǎn)已被訪問(wèn) */typedef char vexType; /*頂點(diǎn)類型*/typedef struct vexType vexMAX;int arcsMAXMAX;int vn, en; MGraph;void createGraph(MGraph *g); /*建鄰接矩陣存儲(chǔ)的無(wú)向圖*/void visit(MGraph *g, int v); /*訪問(wèn)v號(hào)頂點(diǎn)*/void dfs(MGraph *g, int v); /*鄰接矩陣存儲(chǔ)的圖的深度優(yōu)先搜索*/void bfs(MGraph *g, int v); /*鄰接矩陣存儲(chǔ)的圖的廣度優(yōu)先搜索*/void createGraph(MGraph *g) int i, j, v;char a = A;printf(輸入頂點(diǎn)數(shù):); /*輸入頂點(diǎn)數(shù)和邊數(shù)*/scanf(%d, &g-vn);printf(輸入邊數(shù):);scanf(%d, &g-en);for (i = 0; i vn; i+) /*二維數(shù)組初始化*/for (j = 0; j vn; j+) g-arcsij = 0;for (v = 0; v vn; v+) /*確定數(shù)據(jù)*/g-vexv = a;a+;printf(輸入結(jié)構(gòu):n); /*確定邊*/for (v = 0; v en; v+) scanf(%d %d, &i, &j);g-arcsij = 1;g-arcsji = 1;void visit(MGraph *g, int v) printf(%c, g-vexv);void dfs(MGraph *g, int v) int j;visit(g, v); /*輸出數(shù)據(jù)*/visitedv = 1; /*標(biāo)記已訪問(wèn)*/for (j = 0; j vn; j+) if (g-arcsvj = 1 & visitedj = 0) dfs(g, j); /*遞歸*/void bfs(MGraph *g, int v) int i, w;SeqQueue Q;InitQueue(&Q); /*隊(duì)列初始化*/EnQueue(&Q,v); /*入隊(duì)*/visitedv = 1; /*標(biāo)記已訪問(wèn)*/while (!EmptyQueue(&Q) w = DeQueue(&Q); /*出隊(duì)*/visit(g, w); /*輸出數(shù)據(jù)*/for (i = 0; i vn; i+) if (g-arcswi = 1 & visitedi = 0) EnQueue(&Q, i); /*入隊(duì)*/visitedi = 1; /*標(biāo)記已訪問(wèn)*/void main() MGraph g;int i, v;createGraph(&g); /*建圖*/for (i = 0; i g.vn; i+) /*標(biāo)記數(shù)組初始化*/visitedi = 0;printf(開(kāi)始頂點(diǎn):); /*輸入遍歷開(kāi)始頂點(diǎn)*/scanf(%d, &v);printf(輸出(dfs):); /*DFS輸出*/dfs(&g, v);pri