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

1、實(shí)驗(yàn)五 圖操作實(shí)現(xiàn)實(shí)驗(yàn)日期： 2017 年 4 月 27 日 實(shí)驗(yàn)?zāi)康募耙?. 熟練掌握圖的鄰接矩陣和鄰接表的存儲方式；2. 實(shí)現(xiàn)圖的一些基本運(yùn)算，特別是深度優(yōu)先遍歷和廣度優(yōu)先遍歷；實(shí)驗(yàn)內(nèi)容用鄰接矩陣法建一個(gè)無向連通圖（頂點(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;

2、訪問標(biāo)記數(shù)組定義：int visitedmax; /*值為0時(shí)對應(yīng)頂點(diǎn)未被訪問，值為1時(shí)對應(yīng)頂點(diǎn)已被訪問 */順序存儲的循環(huán)隊(duì)列類型定義：typedef int datatype; /*隊(duì)列元素為圖的頂點(diǎn)下標(biāo),int型*/typedef struct node datatype datamax; int front, rear; seqqueue; /*順序存儲的循環(huán)隊(duì)列類型*/任務(wù)1自定義函數(shù)庫文件queue.h，完成隊(duì)列的相關(guān)操作。2創(chuàng)建一個(gè)程序文件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)計(jì)非連通圖的連同分量個(gè)數(shù)。

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; /*隊(duì)列元素為圖的頂點(diǎn)下標(biāo),int型*/typedef struct node datatype datamax;int front, rear; seqqueue; /*順序存儲的循環(huán)隊(duì)

5、列類型*/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) pr

6、intf("隊(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)

7、 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時(shí)對應(yīng)頂點(diǎn)未被訪問，值為1時(shí)對應(yīng)頂點(diǎn)已被訪問 */typedef char vextype; /*頂點(diǎn)類型*/typedef struct vextype vexmax;int arcsmaxmax;int vn, en; mgraph;void cr

8、eategraph(mgraph *g); /*建鄰接矩陣存儲的無向圖*/void visit(mgraph *g, int v); /*訪問v號頂點(diǎn)*/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("輸入頂點(diǎn)數(shù):"); /*輸入頂點(diǎn)數(shù)和邊數(shù)*/scanf("%d", &g-

9、>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; v+) scanf(&q

10、uot;%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) dfs(g, j); /*

11、遞歸*/void bfs(mgraph *g, int v) int i, w;seqqueue q;initqueue(&q); /*隊(duì)列初始化*/enqueue(&q,v); /*入隊(duì)*/visitedv = 1; /*標(biāo)記已訪問*/while (!emptyqueue(&q) w = dequeue(&q); /*出隊(duì)*/visit(g, w); /*輸出數(shù)據(jù)*/for (i = 0; i < g->vn; i+) if (g->arcswi = 1 && visitedi = 0) enqueue(&q, i); /*入隊(duì)*/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);printf("n");for