實驗五圖操作實現

1、實驗五 圖操作實現實驗日期： 2017 年 4 月 27 日 實驗目的及要求1. 熟練掌握圖的鄰接矩陣和鄰接表的存儲方式；2. 實現圖的一些基本運算，特別是深度優(yōu)先遍歷和廣度優(yōu)先遍歷；實驗內容用鄰接矩陣法建一個無向連通圖（頂點信息為順序字母a，b，c，d.，而非鍵盤輸入），分別用dfs（深度優(yōu)先搜索）和bfs(廣度優(yōu)先搜索)遍歷，輸出圖中頂點信息并驗證。鄰接矩陣圖類型定義：#define max 40 typedef char vextype; /*頂點類型*/ typedef struct vextype vexmax; int arcsmaxmax; int vn,en; mgraph;

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

3、）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）現有定義：mgraph *g，并且g指針指向的無向圖已創(chuàng)建完成，請寫出該圖遍歷前需初始化visited數組的c程序語句。for (i = 0; i < g.vn; i+) /*標記數組初始化*/visitedi = 0;（2）定義函數int count (mgraph *g)統(tǒng)計非連通圖的連同分量個數。

4、（說明：借助遍歷算法實現）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自定義函數庫文件queue.h 與sy15.cpp源程序清單（含必要的注釋）queue.h:#include<stdio.h>typedef int datatype; /*隊列元素為圖的頂點下標,int型*/typedef struct node datatype datamax;int front, rear; seqqueue; /*順序存儲的循環(huán)隊

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

6、intf("隊列已滿!"); /*判隊滿*/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(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時對應頂點未被訪問，值為1時對應頂點已被訪問 */typedef char vextype; /*頂點類型*/typedef struct vextype vexmax;int arcsmaxmax;int vn, en; mgraph;void cr

8、eategraph(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("輸入頂點數:"); /*輸入頂點數和邊數*/scanf("%d", &g-

9、>vn);printf("輸入邊數:");scanf("%d", &g->en);for (i = 0; i < g->vn; i+) /*二維數組初始化*/for (j = 0; j < g->vn; j+) g->arcsij = 0;for (v = 0; v < g->vn; v+) /*確定數據*/g->vexv = a;a+;printf("輸入結構: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); /*輸出數據*/visitedv = 1; /*標記已訪問*/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); /*隊列初始化*/enqueue(&q,v); /*入隊*/visitedv = 1; /*標記已訪問*/while (!emptyqueue(&q) w = dequeue(&q); /*出隊*/visit(g, w); /*輸出數據*/for (i = 0; i < g->vn; i+) if (g->arcswi = 1 && visitedi = 0) enqueue(&q, i); /*入隊*/visitedi = 1; /*標記已訪問*/void main() mgraph g;int i, v;creategraph(&g); /*建圖*/for (i = 0; i < g.vn; i+) /*標記數組初始化*/visitedi = 0;printf("開始頂點:"); /*輸入遍歷開始頂點*/scanf("%d", &v);printf("輸出(dfs):"); /*dfs輸出*/dfs(&g, v);printf("n");for