數(shù)據(jù)結(jié)構(gòu)——圖的基本操作

1、1. 實驗題目圖的基本操作2. 實驗?zāi)康?) 掌握圖的鄰接矩陣、鄰接表的表示方法。2) 掌握建立圖的鄰接矩陣的算法。3) 掌握建立圖的鄰接表的算法。4) 加深對圖的理解，逐步培養(yǎng)解決實際問題的編程能力3. 需求分析(1)編寫圖基本操作函數(shù)。 建立圖的鄰接表，鄰接矩陣create_graph( lgraph lg. mgraph mg ) 鄰接表表示的圖的遞歸深度優(yōu)先遍歷ldfs( lgraph g, inti) 鄰接矩陣表示的圖的遞歸深度優(yōu)先遍歷mdfs( mgraph g,int i, int vn ) 鄰接表表示的圖的廣度優(yōu)先遍歷lbfs( lgraph g, int s, int n )

2、 鄰接矩陣表示的圖的廣度優(yōu)先遍歷mbfs(mgraph g, int s, int n )(2)調(diào)用上述函數(shù)實現(xiàn)下列操作。 建立一個圖的鄰接矩陣和圖的鄰接表。 采用遞歸深度優(yōu)先遍歷輸出圖的鄰接矩陣 采用遞歸深度優(yōu)先遍歷輸出圖的鄰接表。 采用圖的廣度優(yōu)先調(diào)歷輸出圖的鄰接表。 采用圖的廣度優(yōu)先遍歷輸出圖的鄰接矩陣4.概要設(shè)計(1)/鄰接矩陣數(shù)據(jù)類型的定義/最大頂點個數(shù)typedef structcharvexsfmax_vertex_num;/ 頂點向量int acrsmax_vertex_nummax_vertex_num; / 鄰接矩陣int vexnum,arcnum;/圖當(dāng)前頂點數(shù)和弧數(shù))

3、mgraph ;/鄰接表數(shù)據(jù)類型的定義int adj vex;typedef struct arcnode/該弧所指向的頂點的位置struct arcnode *nextarc;/指向下一條弧的指針 arcnode;typedef struct vnodechar data;arcnode * firs tare;)vnode, adjlistmax_vertex_num;typedef structadjlist vertices;int vexnum,arcnum;/頂點信息/指向第一條依附該頂點的弧的指針/圖當(dāng)前頂點數(shù)和弧數(shù)jlgraph;<2) 本程序主要包含6個函數(shù): 主慚數(shù)m

4、ain() 建立圖的鄰接矩陣，鄰接表 鄰接表表示的圖的遞歸深度優(yōu)先遍歷 鄰接矩陣表示的圖的遞歸深度優(yōu)先遍歷 鄰接表表示的圖的廣度優(yōu)先遍歷 鄰接矩陣表示的圖的廣度優(yōu)先遍歷create_graph ()ldfs ()mdfs ()lbfs ()mbfs ()各函數(shù)間調(diào)用關(guān)系如下:create_graph ()ldfs ()mdfs ()lbfs ()mbfs ()main()定義鄰接矩陣和鄰接表;建立鄰接矩陣和鄰接表；鄰接矩陣mdfs深度優(yōu)先遍歷； 鄰接矩陣mbfs廣度優(yōu)先遍歷: 鄰接表ldfs深度優(yōu)先遍歷； 鄰接表lbfs廣度優(yōu)先遍歷5詳細設(shè)計/ 鄰接矩陣數(shù)據(jù)類型的定義/最大頂點個數(shù)typede

5、f structchar vexsfmax.vertex.num;/ 頂點向量int acrsmax_vertex_nummax_vertex_num; / 鄰接矩陣 int vexnum,arcnum;/圖當(dāng)前頂點數(shù)和弧數(shù)jmgraph ;/鄰接表數(shù)據(jù)類型的定義typedef struct arcnodeint adjvex; struct arcnode *nextarc;jarcnode;typedef struct vnodechar data;arcnode *firstarc;vnode,adjlistmax_vertex_num;typedef structadjlist ver

6、tices;int vexnum9arcnum;jlgraph;/該弧所指向的頂點的位置/指向下一條弧的指針/頂點信息/指向第一條依附該頂點的弧的指針/圖當(dāng)前頂點數(shù)和弧數(shù)int create_graph( mgraph *mg , lgraph *lg ) / 建立圖的鄰接矩陣，鄰接表 輸入圖的頂點個數(shù)(字符)，構(gòu)造頂點向量輸入圖的任意兩個頂點的弧構(gòu)造鄰接矩陣構(gòu)造鄰接表void ldfs(lgraph *lg,int i)鄰接表表示的圖的遞歸深度優(yōu)先遍歷 顯示頂點向量，指針指向下一個頂點向量下一個頂點沒有被訪問，繼續(xù)否則退會上一個頂點向量的另一個邊void mdfs(mgraph *mg,in

7、t i)鄰接矩陣表示的圖的遞歸深度優(yōu)先遍歷顯示頂點向量，指針指向下一個頂點向量下一個頂點沒有被訪問，繼續(xù)否則退會上一個頂點向量的另一個邊void lbfs( lgraph *lg )鄰接表表示的圖的廣度優(yōu)先遍歷初始化visitedf初始化隊列沒被訪問過顯示頂點向量入隊出隊訪問下一個頂點向量void mbfs(mgraph *mg )鄰接矩陣表示的圖的廣度優(yōu)先遍歷 初始化visited初始化隊列沒被訪問過顯示頂點向量入隊出隊訪問下一個頂點向量/主函數(shù)main()定義鄰接矩陣和鄰接表；建立鄰接矩陣和鄰接表；鄰接矩陣mdfs深度優(yōu)先遍歷；鄰接矩陣mbfs c度優(yōu)先遍歷:鄰接表ldfs深度優(yōu)先遍歷；鄰

8、接表lbfs廣度優(yōu)先遍歷6測試結(jié)果1 o回d:程序沒計c+匱的基不璨作debug匿的基本揍作a s s d a f f gasdf g asf dg af gsd af sdgas d f g> > > > >占小占小占小占八-力-力ue 頂頂頂頂耶詬一冠幵in ?<<<<<2222今夕龍哂o 飆占吿吿吿吿小的的的®先先c to 番的的的的連連連連探廣度度y 點圖圖圖圖圖邊邊邊邊f(xié)sfs探廣ke mb盼fsy 旳二二二一二屢ldlban 圏人)a-)a-)a-)a-)a-)a-)a-)a-包包卻埶 s 書請請請請請請請請鄰鄰

9、鄰鄰pr7. 參考文獻數(shù)據(jù)結(jié)構(gòu)8. 附錄#include <stdio.h> #include <malloc.h> #include <stddef.h> #include <math.h> #define ok 1 #define error 0#define max_vertex_num 20int visitedmax_vertex_num;/ 訪問標(biāo)志數(shù)組/鄰接矩陣數(shù)據(jù)類型的定義/最大頂點個數(shù)typedef structchar vexsmax_vertex_num;頂點向量int acrslmax_vertex_nummax_vert

10、ex_numj; / 鄰接矩陣 int vexnum,arcnum;/圖當(dāng)前頂點數(shù)和弧數(shù)jmgraph ;/鄰接表數(shù)據(jù)類型的定義typedef struct arcnodeint adj vex;struct arcnode *nextarc; arcnode;typedef struct vnodechar data;arcnode * firs tare;)vnode, adjlistmax_vertex_num;typedef structadjlist vertices;int vexnum.arcnum;jlgraph;/該弧所指向的頂點的位置/指向下一條弧的指針/頂點信息/指向第一

11、條依附該頂點的弧的指針/圖當(dāng)前頂點數(shù)和弧數(shù)/隊列函數(shù)typedef struct queueint arrymax_vertex_num;int front,rear;)queue;queue q;void initqueue()/ 隊列初始化q. front=q.rear=0;int queueempty(queue *q)/ 清空隊列if(q->front=q->rear)return 1;elsereturn 0;1void enqueue(queue *q,int w) 入隊if(q->rear+1 )%m ax_vertex_num=q->front)prin

12、tf(herror!");elseq->arry q->rear=w;q->rear=(q->rear+1 )%max_vertex_num;int dequeue(queue *q)/ 出隊int u;if(q->front=q->rear)return -1;u=q->front;q->front=(q->front+l)%max_vertex_num;return u;/隊歹函數(shù)end/* * * * * * * 函數(shù)：create_graph*功能：建立圖的鄰接矩陣，鄰接表*說明：該構(gòu)建的為無向網(wǎng)mg為鄰接矩陣，ig為鄰接

13、表，無權(quán)值int locatevex(mgraph *mg , char v) int i;for(i=0;mg->vexsi !=v;i+);if(i>mg->vexnum) printf(”error “)；return i;確定v元素在mg中的位置/輸入的元素不正確則顯示錯誤/返冋位置int create_graph( mgraph *mg , lgraph *lg ) / 建立圖的鄰接矩陣，鄰接表 inti ,j , k ；char vl , v2 ;arc node *q,*p;print”輸入圖的頂點數(shù)和弧數(shù):“)；scanf(”d %d",&m

14、g->vexnum,&mg->arcnum); getchar();lg->vexnum=mg->vexnum;/鄰接表的頂點數(shù)和弧數(shù)lg> arcnum=mg->arcnum;for(i=0;i<mg->vexnum;i+)/ 構(gòu)造頂點向量prints(”請輸入一個圖的頂點(字符):“)；scanf(h%cm, &mg->vexsi);getchar();lg->veilicesi.data=mg->vexsi; / 賦值lg->verticesi.firstarc=null;/指向第一條依附該頂點的弧的

15、指針 為空for(j=0;j<mg->vexnum;j+) mg->acrsij=o ;for(k=0;k<mg->arcnum;k+)/構(gòu)造鄰接矩陣和鄰接表printf(m請輸入一條邊連接的2個頂點：“)；scanf(u%c %c”,&vl,&v2);getchar();i=locatevex(mg,vl);確定 vl 在 mg 中的位置j=locatevex(mg,v2);確定 v2 在 mg 中的位置mg->acrsji=mg->acrsij=l; / 置vl,v2的對稱弧v2,vlp=(arcnode *)malloc(size

16、of(arcnode);p->adjvex=i;確認(rèn)頂點位置p->nextarc=lg->verticesj.firstarc;/ 指向下一條弧的指針 lg->vertices j . firstarc=p;/ 賦值q=(arcnode *)malloc(sizeof(arcnode);q->adjvex=j;確認(rèn)頂點位置q->nextarc=lg->verticesi.firstarc;/ 指向下一條弧的指針lg->verticesi.firstarc=q;/ 賦值return ok ;/vl#kl#/卜 卜 * 卜 卜 * .卜 卜 卜 r|

17、 卜 rj 卜 卜 r| 卜 rjrj* rj* rj* rj* rj* rj*rj* rj*rj*rjw r|* rjw*函數(shù)：ldfs *功能：鄰接表表示的圖的遞歸深度優(yōu)先遍歷*說明int ladjvex(lgraph *lgjnt k)/ 位置arcnode *p;fbr(p=lg->verticesk.firstarc;p!=null;p=p->n extarc) if(!visitedp->adjvex)return p->adjvex;return -1;void ldfs(lgraph *lg,int i)int k;visitedi=ok;printf(

18、m%c",lg->verticesi.data);for(k=ladjvex(lg,i);k>=0;k=ladjvex(lg,k)if(!visitedk)ldfs(lg,k);f<1#<1#1>k1>2 kl# kl# kl# kl1#1#/*4 rj*rj rj* 卜 卜 *w 卜 rj卜 *w .卜 .卜卜卜 rp 卜 rj* 卜 rj 卜 rp 卜 rj ryw rp rj* 卜 rw 卜 rp rj* rj* ryw rj* 卜 卜 rw 卜 rj* rj* ryw 卜 rj% rj* rj rj* rj* rj rj* rj* 評 rj

19、 rj rj rj rj rj rj rj評 rj rj rj卜 rj評 rj評 rj*函數(shù)：mdfs*功能：鄰接矩陣表示的圖的遞歸深度優(yōu)先遍歷*說明：%£#%1# <1 %1# <1£z<1>>>”/rj% 廣 rj% rj rj% rj% rj rj rj rj% rj* 卜 rj% rj% rj rj* rj% rjw rj% rj% 卜rj% "j* 卜卜卜 f "卜"卜rp rp rp 卜 rp rp rp .卜 rf* rp rp rp rp 卜 rj rf* 卜 rj rf* rj rf* 卜

20、rj% rj rj% 卜 rj% 卜 rj% rj rj% 卜 j位置int adjves(mgraph *mgjnt k)/int i;for(i=0;i<mg->vexnum;i+) if(mg->acrski&&(!visitedi) return i;return -1;void mdfs(mgraph *mg,int i)/遞歸深度優(yōu)先遍歷int k;visitedi=l;printf(n%c",mg->vexsi);for(k=adjves(mg,i)；k>=0;k=adjves(mg,k)if(!visitedk)mdfs(

21、mg,k);/訪問標(biāo)志數(shù)組某位 置1顯不/遞歸/vl vl#kl kl#kxkl kl/ *|*|* 卜 *|* 卜 * 卜 *|* 卜 * .卜 *|* 卜 rj 卜 r| 卜 rj 卜 rj 卜 r| 卜 rjrj* rj* rj* rj* rj* rj*rj* rj*rj*ry*ry* r| rj r| rj r| rj rjw rj r|* rj rjw*函數(shù)：lbfs *功能：鄰接表表示的圖的廣度優(yōu)先遍歷*說明/ 初始化 visited/初始化隊列/沒被訪問過/入隊void lbfs( lgraph *lg )int i,u,w;for(i=0;i<lg->vexnum;

22、+i) visitedil=o;initqueue(); for(i=0;i<lg->vexnum;+i) if(!visitedi)visitedi=l;printf(m%cn ,lg-> vertices i data);enqueue(&qi);while(!queueempty(&q)u=dequeue(&q);/ 出隊for(w=ladjvex(lg,u);w>=0;w=ladjvex(lg,u) if(!visitedw)/ 沒被訪問過visitedw=l; printf(n%c,lg->verticesw.data); enq

23、ueue(&q,w); / 入隊/vl#kl#klkl/ *|*|* 卜 *|* 卜 * 卜 *|* 卜 * .卜 *|* 卜 rj 卜 r| 卜 rj 卜 rj 卜 r| 卜 rj r| rjr| rj rj* rj* rj* rj* rj* rj* rj rj* rj*rj*r| rj r| rj r| rj rjw rj r|* rj rjw*函數(shù)：mbfs*功能：鄰接矩陣表示的圖的廣度優(yōu)先遍歷*說明：/ 初始化 visited/初始化隊列/沒被訪問過/顯示/入隊/出隊void mbfs(mgraph *mg)int i,w,u;for(i=0;i<mg->vexnu

24、m;i+) visitedi=o;initqueue(); for(i=0;i<mg->vexnum;+i) if(!visitedi)visitedi=l; printf("%c",mg->vexsi); enqueue(&q,i);wh ile(! queueempty(&q) u=dequeue(&q);for(w=adjves(mg,u);w>=0;w=adjves(mg,u)if(!visitedw)/ 沒被訪問過visitedw=l;printf(m%cn,mg->vexsw);/ s/jsenqueue(&q,w);/ 入隊/<1> 11 * . « "an .1 2# / rj* rj* rj* rj* rj* 卜 卜 卜 卜 卜 卜 rj* 卜 rp 卜 rj 卜 rp 卜 rj 卜 rj rj* rp rj* rj* ryw