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

1、實(shí)驗五 圖操作實(shí)現(xiàn)實(shí)驗日期： 2017 年 4 月 27 日 實(shí)驗?zāi)康募耙?. 熟練掌握圖的鄰接矩陣和鄰接表的存儲方式；2. 實(shí)現(xiàn)圖的一些基本運(yùn)算，特別是深度優(yōu)先遍歷和廣度優(yōu)先遍歷；實(shí)驗內(nèi)容用鄰接矩陣法建一個無向連通圖（頂點(diǎn)信息為順序字母A，B，C，D.，而非鍵盤輸入），分別用dfs（深度優(yōu)先搜索）和bfs(廣度優(yōu)先搜索)遍歷，輸出圖中頂點(diǎn)信息并驗證。鄰接矩陣圖類型定義：#define MAX 40 typedef char vexType; /*頂點(diǎn)類型*/ typedef struct vexType vexMAX; int arcsMAXMAX; int vn,en; MGraph;

2、訪問標(biāo)記數(shù)組定義：int visitedMAX; /*值為0時對應(yīng)頂點(diǎn)未被訪問，值為1時對應(yīng)頂點(diǎn)已被訪問 */順序存儲的循環(huán)隊列類型定義：typedef int datatype; /*隊列元素為圖的頂點(diǎn)下標(biāo),int型*/typedef struct node datatype dataMAX; int front, rear; SeqQueue; /*順序存儲的循環(huán)隊列類型*/任務(wù)1自定義函數(shù)庫文件Queue.h，完成隊列的相關(guān)操作。2創(chuàng)建一個程序文件sy15.cpp，自定義相應(yīng)函數(shù)完成以下操作：（1）void createGraph(MGraph *g) /*建鄰接矩陣存儲的無向圖*/（2

3、）void visit(MGraph *g,int v) /*訪問v號頂點(diǎn)*/（3）void dfs(MGraph *g,int v) /*鄰接矩陣存儲的圖的深度優(yōu)先搜索*/（4）void bfs(MGraph *g,int v) /*鄰接矩陣存儲的圖的廣度優(yōu)先搜索*/3回答下列問題（1）現(xiàn)有定義：MGraph *g，并且g指針指向的無向圖已創(chuàng)建完成，請寫出該圖遍歷前需初始化visited數(shù)組的C程序語句。for (i = 0; i g.vn; i+) /*標(biāo)記數(shù)組初始化*/visitedi = 0;（2）定義函數(shù)int count (MGraph *g)統(tǒng)計非連通圖的連同分量個數(shù)。（說明：借

4、助遍歷算法實(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ù)庫文件Queue.h 與sy15.cpp源程序清單（含必要的注釋）Queue.h:#includetypedef int datatype; /*隊列元素為圖的頂點(diǎn)下標(biāo),int型*/typedef struct node datatype dataMAX;int front, rear; SeqQueue; /*順序存儲的循環(huán)隊列類型*/void InitQueue(SeqQueue *

5、Q); /*初始化隊列*/void EnQueue(SeqQueue *Q, int v); /*入隊*/datatype DeQueue(SeqQueue *Q); /*出隊*/int EmptyQueue(SeqQueue *Q); /*判隊空*/int FullQueue(SeqQueue *Q); /*判隊滿*/void InitQueue(SeqQueue *Q) Q-front = Q-rear = 0;void EnQueue(SeqQueue *Q, int v) if (FullQueue(Q) printf(隊列已滿!); /*判隊滿*/return;Q-rear = (Q

6、-rear + 1) % MAX; /*入隊*/Q-dataQ-rear = v;datatype DeQueue(SeqQueue *Q) if (EmptyQueue(Q) printf(隊列為空!); /*判隊空*/return -1;Q-front = (Q-front + 1) % MAX; /*出隊*/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.cp

7、p:#define MAX 40#includeQueue.hint visitedMAX; /*值為0時對應(yīng)頂點(diǎn)未被訪問，值為1時對應(yīng)頂點(diǎn)已被訪問 */typedef char vexType; /*頂點(diǎn)類型*/typedef struct vexType vexMAX;int arcsMAXMAX;int vn, en; MGraph;void createGraph(MGraph *g); /*建鄰接矩陣存儲的無向圖*/void visit(MGraph *g, int v); /*訪問v號頂點(diǎn)*/void dfs(MGraph *g, int v); /*鄰接矩陣存儲的圖的深度優(yōu)先搜索

8、*/void bfs(MGraph *g, int v); /*鄰接矩陣存儲的圖的廣度優(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):

9、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)記已訪問*/for (j = 0; j vn; j+) if (g-arcsvj = 1 & visitedj = 0) dfs(g, j); /*遞歸*/void bfs(MGraph *g, int

10、 v) int i, w;SeqQueue Q;InitQueue(&Q); /*隊列初始化*/EnQueue(&Q,v); /*入隊*/visitedv = 1; /*標(biāo)記已訪問*/while (!EmptyQueue(&Q) w = DeQueue(&Q); /*出隊*/visit(g, w); /*輸出數(shù)據(jù)*/for (i = 0; i vn; i+) if (g-arcswi = 1 & visitedi = 0) EnQueue(&Q, i); /*入隊*/visitedi = 1; /*標(biāo)記已訪問*/void main() MGraph g;int i, v;createGraph(&g); /*建圖*/for (i = 0; i g.vn; i+) /*標(biāo)記數(shù)組初始化*/visitedi = 0;printf(開始頂點(diǎn):); /*輸入遍歷開始頂點(diǎn)*/scanf(%d, &v);printf(輸出(dfs):); /*DFS輸出*/dfs(&g, v);pri