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

實驗五圖操作實現(xiàn)實驗五圖操作實現(xiàn)實驗五圖操作實現(xiàn)xxx公司實驗五圖操作實現(xiàn)文件編號：文件日期：修訂次數(shù)：第1.0次更改批準審核制定方案設(shè)計，管理制度實驗五圖操作實現(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)先搜索)遍歷，輸出圖中頂點信息并驗證。鄰接矩陣圖類型定義：#defineMAX40typedefcharvexType;/*頂點類型*/typedefstruct{vexTypevex[MAX];intarcs[MAX][MAX];intvn,en;}MGraph;訪問標記數(shù)組定義：intvisited[MAX];/*值為0時對應(yīng)頂點未被訪問，值為1時對應(yīng)頂點已被訪問*/順序存儲的循環(huán)隊列類型定義：typedefintdatatype;/*隊列元素為圖的頂點下標,int型*/typedefstructnode{datatypedata[MAX];intfront,rear;}SeqQueue;/*順序存儲的循環(huán)隊列類型*/任務(wù)1．自定義函數(shù)庫文件，完成隊列的相關(guān)操作。2．創(chuàng)建一個程序文件，自定義相應(yīng)函數(shù)完成以下操作：（1）voidcreateGraph(MGraph*g)/*建鄰接矩陣存儲的無向圖*/（2）voidvisit(MGraph*g,intv)/*訪問v號頂點*/（3）voiddfs(MGraph*g,intv)/*鄰接矩陣存儲的圖的深度優(yōu)先搜索*/（4）voidbfs(MGraph*g,intv)/*鄰接矩陣存儲的圖的廣度優(yōu)先搜索*/3．回答下列問題（1）現(xiàn)有定義：MGraph*g，并且g指針指向的無向圖已創(chuàng)建完成，請寫出該圖遍歷前需初始化visited數(shù)組的C程序語句。for(i=0;i<;i++){/*標記數(shù)組初始化*/ visited[i]=0;}（2）定義函數(shù)intcount(MGraph*g)統(tǒng)計非連通圖的連同分量個數(shù)。（說明：借助遍歷算法實現(xiàn)）intcount(MGraph*g){inti,m=0;for(i=0;i<g->vn;i++)if(visited[i]==0){m++;dfs(g,i);}returnm;}4．自定義函數(shù)庫文件與源程序清單（含必要的注釋）:#include<>typedefintdatatype;/*隊列元素為圖的頂點下標,int型*/typedefstructnode{ datatypedata[MAX]; intfront,rear;}SeqQueue;/*順序存儲的循環(huán)隊列類型*/voidInitQueue(SeqQueue*Q);/*初始化隊列*/voidEnQueue(SeqQueue*Q,intv);/*入隊*/datatypeDeQueue(SeqQueue*Q);/*出隊*/intEmptyQueue(SeqQueue*Q);/*判隊空*/intFullQueue(SeqQueue*Q);/*判隊滿*/voidInitQueue(SeqQueue*Q){ Q->front=Q->rear=0;}voidEnQueue(SeqQueue*Q,intv){ if(FullQueue(Q)){ printf("隊列已滿!");/*判隊滿*/ return; } Q->rear=(Q->rear+1)%MAX;/*入隊*/ Q->data[Q->rear]=v;}datatypeDeQueue(SeqQueue*Q){ if(EmptyQueue(Q)){ printf("隊列為空!");/*判隊空*/ return-1; } Q->front=(Q->front+1)%MAX;/*出隊*/ returnQ->data[Q->front];}intEmptyQueue(SeqQueue*Q){ returnQ->front==Q->rear;}intFullQueue(SeqQueue*Q){ return(Q->rear+1)%MAX==Q->front;}:#defineMAX40#include""intvisited[MAX];/*值為0時對應(yīng)頂點未被訪問，值為1時對應(yīng)頂點已被訪問*/typedefcharvexType;/*頂點類型*/typedefstruct{ vexTypevex[MAX]; intarcs[MAX][MAX]; intvn,en;}MGraph;voidcreateGraph(MGraph*g);/*建鄰接矩陣存儲的無向圖*/voidvisit(MGraph*g,intv);/*訪問v號頂點*/voiddfs(MGraph*g,intv);/*鄰接矩陣存儲的圖的深度優(yōu)先搜索*/voidbfs(MGraph*g,intv);/*鄰接矩陣存儲的圖的廣度優(yōu)先搜索*/voidcreateGraph(MGraph*g){ inti,j,v; chara='A'; printf("輸入頂點數(shù):");/*輸入頂點數(shù)和邊數(shù)*/ scanf("%d",&g->vn); printf("輸入邊數(shù):"); scanf("%d",&g->en); for(i=0;i<g->vn;i++){/*二維數(shù)組初始化*/ for(j=0;j<g->vn;j++){ g->arcs[i][j]=0; } } for(v=0;v<g->vn;v++){/*確定數(shù)據(jù)*/ g->vex[v]=a; a++; } printf("輸入結(jié)構(gòu):\n");/*確定邊*/ for(v=0;v<g->en;v++){ scanf("%d%d",&i,&j); g->arcs[i][j]=1; g->arcs[j][i]=1; }}voidvisit(MGraph*g,intv){ printf("%c",g->vex[v]);}voiddfs(MGraph*g,intv){ intj; visit(g,v);/*輸出數(shù)據(jù)*/ visited[v]=1;/*標記已訪問*/ for(j=0;j<g->vn;j++){ if(g->arcs[v][j]==1&&visited[j]==0){ dfs(g,j);/*遞歸*/ } }}voidbfs(MGraph*g,intv){ inti,w; SeqQueueQ; InitQueue(&Q);/*隊列初始化*/ EnQueue(&Q,v);/*入隊*/ visited[v]=1;/*標記已訪問*/ while(!EmptyQueue(&Q)){ w=DeQueue(&Q);/*出隊*/ visit(g,w);/*輸出數(shù)據(jù)*/ for(i=0;i<g->vn;i++){ if(g->arcs[w][i]==1&&visited[i]==0){ EnQueue(&Q,i);/*入隊*/ visited[i]=1;/*標記已訪問*/ } } }}voidmain(){ MGraphg; inti,v; createGraph(&g);/*建圖*/ for(i=0;i<;i++){/*標記數(shù)組初始化*/ visited[i]=0; } printf("開始頂點:");/*輸入遍歷開始頂點*/ scanf("%d",&v); printf("輸出(dfs):");/*DFS輸出*/ dfs(&g,v); printf("\n"); for(i=0;i<;i++){/*標記數(shù)組初始化*/ visited[i]=0; } printf("輸出(bfs)