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

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

2、,en; MGraph; 訪問標(biāo)記數(shù)組定義：int visitedMAX; /*值為0時對應(yīng)頂點未被訪問，值為1時對應(yīng)頂點已被訪問 */順序存儲的循環(huán)隊列類型定義：typedef int datatype; /*隊列元素為圖的頂點下標(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) /*建鄰

3、接矩陣存儲的無向圖*/（2）void visit(MGraph *g,int v) /*訪問v號頂點*/（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)

4、計非連通圖的連同分量個數(shù)。（說明：借助遍歷算法實現(xiàn)）int count (MGraph *g) int i, m=0; for(i=0; i<g->vn; i+) if(visitedi=0) m+; dfs(g, i); return m;4自定義函數(shù)庫文件Queue.h 與sy15.cpp源程序清單（含必要的注釋）Queue.h:#include<stdio.h>typedef int datatype; /*隊列元素為圖的頂點下標(biāo),int型*/typedef struct node datatype dataMAX;int front, rear; SeqQueu

5、e; /*順序存儲的循環(huán)隊列類型*/void InitQueue(SeqQueue *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 (Fu

6、llQueue(Q) printf("隊列已滿!"); /*判隊滿*/return;Q->rear = (Q->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

7、(SeqQueue *Q) return Q->front = Q->rear;int FullQueue(SeqQueue *Q) return (Q->rear + 1) % MAX = Q->front;sy5.cpp:#define MAX 40#include"Queue.h"int visitedMAX; /*值為0時對應(yīng)頂點未被訪問，值為1時對應(yīng)頂點已被訪問 */typedef char vexType; /*頂點類型*/typedef struct vexType vexMAX;int arcsMAXMAX;int vn, en; M

8、Graph;void createGraph(MGraph *g); /*建鄰接矩陣存儲的無向圖*/void visit(MGraph *g, int v); /*訪問v號頂點*/void dfs(MGraph *g, int v); /*鄰接矩陣存儲的圖的深度優(yōu)先搜索*/void bfs(MGraph *g, int v); /*鄰接矩陣存儲的圖的廣度優(yōu)先搜索*/void createGraph(MGraph *g) int i, j, v;char a = 'A'printf("輸入頂點數(shù):"); /*輸入頂點數(shù)和邊數(shù)*/scanf("%d&q

9、uot;, &g->vn);printf("輸入邊數(shù):");scanf("%d", &g->en);for (i = 0; i < g->vn; i+) /*二維數(shù)組初始化*/for (j = 0; j < g->vn; j+) g->arcsij = 0;for (v = 0; v < g->vn; v+) /*確定數(shù)據(jù)*/g->vexv = a;a+;printf("輸入結(jié)構(gòu):n"); /*確定邊*/for (v = 0; v < g->en;

10、 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 < g->vn; j+) if (g->arcsvj = 1 && visitedj = 0)

11、dfs(g, j); /*遞歸*/void bfs(MGraph *g, int 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 < g->vn; i+) if (g->arcswi = 1 && visitedi = 0) EnQueu

12、e(&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("開始頂點:"); /*輸入遍歷開始頂點*/scanf("%d", &v);printf("輸出(dfs):"); /*DFS輸出*/dfs(&g, v);printf("n");for (i = 0