数据结构——图的基本操作

1、1. 实验题目图的基本操作2. 实验目的1) 掌握图的邻接矩阵、邻接表的表示方法。2) 掌握建立图的邻接矩阵的算法。3) 掌握建立图的邻接表的算法。4) 加深对图的理解，逐步培养解决实际问题的编程能力3. 需求分析(1)编写图基本操作函数。 建立图的邻接表，邻接矩阵create_graph( lgraph lg. mgraph mg ) 邻接表表示的图的递归深度优先遍历ldfs( lgraph g, inti) 邻接矩阵表示的图的递归深度优先遍历mdfs( mgraph g,int i, int vn ) 邻接表表示的图的广度优先遍历lbfs( lgraph g, int s, int n )

2、 邻接矩阵表示的图的广度优先遍历mbfs(mgraph g, int s, int n )(2)调用上述函数实现下列操作。 建立一个图的邻接矩阵和图的邻接表。 采用递归深度优先遍历输出图的邻接矩阵 采用递归深度优先遍历输出图的邻接表。 采用图的广度优先调历输出图的邻接表。 采用图的广度优先遍历输出图的邻接矩阵4.概要设计(1)/邻接矩阵数据类型的定义/最大顶点个数typedef structcharvexsfmax_vertex_num;/ 顶点向量int acrsmax_vertex_nummax_vertex_num; / 邻接矩阵int vexnum,arcnum;/图当前顶点数和弧数)

3、mgraph ;/邻接表数据类型的定义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;/顶点信息/指向第一条依附该顶点的弧的指针/图当前顶点数和弧数jlgraph;<2) 本程序主要包含6个函数: 主惭数m

4、ain() 建立图的邻接矩阵，邻接表 邻接表表示的图的递归深度优先遍历 邻接矩阵表示的图的递归深度优先遍历 邻接表表示的图的广度优先遍历 邻接矩阵表示的图的广度优先遍历create_graph ()ldfs ()mdfs ()lbfs ()mbfs ()各函数间调用关系如下:create_graph ()ldfs ()mdfs ()lbfs ()mbfs ()main()定义邻接矩阵和邻接表;建立邻接矩阵和邻接表；邻接矩阵mdfs深度优先遍历； 邻接矩阵mbfs广度优先遍历: 邻接表ldfs深度优先遍历； 邻接表lbfs广度优先遍历5详细设计/ 邻接矩阵数据类型的定义/最大顶点个数typede

5、f structchar vexsfmax.vertex.num;/ 顶点向量int acrsmax_vertex_nummax_vertex_num; / 邻接矩阵 int vexnum,arcnum;/图当前顶点数和弧数jmgraph ;/邻接表数据类型的定义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;/该弧所指向的顶点的位置/指向下一条弧的指针/顶点信息/指向第一条依附该顶点的弧的指针/图当前顶点数和弧数int create_graph( mgraph *mg , lgraph *lg ) / 建立图的邻接矩阵，邻接表 输入图的顶点个数(字符)，构造顶点向量输入图的任意两个顶点的弧构造邻接矩阵构造邻接表void ldfs(lgraph *lg,int i)邻接表表示的图的递归深度优先遍历 显示顶点向量，指针指向下一个顶点向量下一个顶点没有被访问，继续否则退会上一个顶点向量的另一个边void mdfs(mgraph *mg,in

7、t i)邻接矩阵表示的图的递归深度优先遍历显示顶点向量，指针指向下一个顶点向量下一个顶点没有被访问，继续否则退会上一个顶点向量的另一个边void lbfs( lgraph *lg )邻接表表示的图的广度优先遍历初始化visitedf初始化队列没被访问过显示顶点向量入队出队访问下一个顶点向量void mbfs(mgraph *mg )邻接矩阵表示的图的广度优先遍历 初始化visited初始化队列没被访问过显示顶点向量入队出队访问下一个顶点向量/主函数main()定义邻接矩阵和邻接表；建立邻接矩阵和邻接表；邻接矩阵mdfs深度优先遍历；邻接矩阵mbfs c度优先遍历:邻接表ldfs深度优先遍历；邻

8、接表lbfs广度优先遍历6测试结果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 点图图图图图边边边边fsfs探广ke mb盼fsy 旳二二二一二屢ldlban 圏人)a-)a-)a-)a-)a-)a-)a-)a-包包却埶 s 書请请请请请请请请邻邻

9、邻邻pr7. 参考文献数据结构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;/ 访问标志数组/邻接矩阵数据类型的定义/最大顶点个数typedef structchar vexsmax_vertex_num;顶点向量int acrslmax_vertex_nummax_vert

10、ex_numj; / 邻接矩阵 int vexnum,arcnum;/图当前顶点数和弧数jmgraph ;/邻接表数据类型的定义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、条依附该顶点的弧的指针/图当前顶点数和弧数/队列函数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;/队歹函数end/* * * * * * * 函数：create_graph*功能：建立图的邻接矩阵，邻接表*说明：该构建的为无向网mg为邻接矩阵，ig为邻接

13、表，无权值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”输入图的顶点数和弧数:“)；scanf(”d %d",&m

14、g->vexnum,&mg->arcnum); getchar();lg->vexnum=mg->vexnum;/邻接表的顶点数和弧数lg> arcnum=mg->arcnum;for(i=0;i<mg->vexnum;i+)/ 构造顶点向量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+)/构造邻接矩阵和邻接表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;确认顶点位置p->nextarc=lg->verticesj.firstarc;/ 指向下一条弧的指针 lg->vertices j . firstarc=p;/ 赋值q=(arcnode *)malloc(sizeof(arcnode);q->adjvex=j;确认顶点位置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*函数：ldfs *功能：邻接表表示的图的递归深度优先遍历*说明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*函数：mdfs*功能：邻接矩阵表示的图的递归深度优先遍历*说明：%£#%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)/递归深度优先遍历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);/访问标志数组某位 置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*函数：lbfs *功能：邻接表表示的图的广度优先遍历*说明/ 初始化 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*函数：mbfs*功能：邻接矩阵表示的图的广度优先遍历*说明：/ 初始化 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