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

福建师范大学物光院计算机教学辅导讲义1 实验题目图的基本操作2 实验目的1)掌握图的邻接矩阵、邻接表的表示方法。2)掌握建立图的邻接矩阵的算法。3)掌握建立图的邻接表的算法。4)加深对图的理解，逐步培养解决实际问题的编程能力3需求分析 (1)编写图基本操作函数。建立图的邻接表，邻接矩阵Create_Graph( LGraph lg. MGraph mg ) 邻接表表示的图的递归深度优先遍历LDFS( LGraph g, int i )邻接矩阵表示的图的递归深度优先遍历MDFS( MGraph g,int i, int vn )邻接表表示的图的广度优先遍历LBFS( LGraph g, int s, int n )邻接矩阵表示的图的广度优先遍历MBFS(MGraph g, int s, int n )(2)调用上述函数实现下列操作。建立一个图的邻接矩阵和图的邻接表。采用递归深度优先遍历输出图的邻接矩阵采用递归深度优先遍历输出图的邻接表。采用图的广度优先调历输出图的邻接表。采用图的广度优先遍历输出图的邻接矩阵4概要设计（1） ：/*图的基本操作*/- 邻接矩阵数据类型的定义-/ 最大顶点个数typedef structchar vexsMAX_VERTEX_NUM;/ 顶点向量 intacrsMAX_VERTEX_NUMMAX_VERTEX_NUM;/ 邻接矩阵 intvexnum,arcnum;/ 图当前顶点数和弧数MGraph ;/-邻接表数据类型的定义-typedef struct ArcNodeint adjvex;/ 该弧所指向的顶点的位置 struct ArcNode *nextarc;/ 指向下一条弧的指针 ArcNode;typedef struct VNodechar data;/ 顶点信息ArcNode *firstarc;/ 指向第一条依附该顶点的弧的指针VNode, AdjListMAX_VERTEX_NUM;typedef structAdjList vertices; int vexnum,arcnum;/ 图当前顶点数和弧数 LGraph;（2） 本程序主要包含6个函数： 主函数main() 建立图的邻接矩阵，邻接表 Create_Graph () 邻接表表示的图的递归深度优先遍历LDFS () 邻接矩阵表示的图的递归深度优先遍历MDFS () 邻接表表示的图的广度优先遍历LBFS () 邻接矩阵表示的图的广度优先遍历MBFS（）各函数间调用关系如下：mainCreate_Graph ()LDFS ()MDFS ()LBFS ()MBFS（）（3） 主函数的伪码main() 定义邻接矩阵和邻接表； 建立邻接矩阵和邻接表； 邻接矩阵MDFS深度优先遍历；邻接矩阵MBFS广度优先遍历；邻接表LDFS深度优先遍历；邻接表LBFS广度优先遍历5详细设计/*图的基本操作*/- 邻接矩阵数据类型的定义-/ 最大顶点个数typedef structchar vexsMAX_VERTEX_NUM;/ 顶点向量 intacrsMAX_VERTEX_NUMMAX_VERTEX_NUM;/ 邻接矩阵 intvexnum,arcnum;/ 图当前顶点数和弧数MGraph ;/-邻接表数据类型的定义-typedef struct ArcNodeint adjvex;/ 该弧所指向的顶点的位置 struct ArcNode *nextarc;/ 指向下一条弧的指针 ArcNode;typedef struct VNodechar data;/ 顶点信息ArcNode *firstarc;/ 指向第一条依附该顶点的弧的指针VNode, AdjListMAX_VERTEX_NUM;typedef structAdjList vertices; int vexnum,arcnum;/ 图当前顶点数和弧数 LGraph;int Create_Graph( MGraph *Mg , LGraph *Lg ) / 建立图的邻接矩阵，邻接表输入图的顶点个数（字符），构造顶点向量输入图的任意两个顶点的弧构造邻接矩阵构造邻接表void LDFS(LGraph *Lg,int i) 邻接表表示的图的递归深度优先遍历显示顶点向量，指针指向下一个顶点向量下一个顶点没有被访问，继续否则 退会上一个顶点向量的另一个边void MDFS(MGraph *Mg,int i) 邻接矩阵表示的图的递归深度优先遍历显示顶点向量，指针指向下一个顶点向量下一个顶点没有被访问，继续否则 退会上一个顶点向量的另一个边void LBFS( LGraph *Lg )邻接表表示的图的广度优先遍历 初始化 visited初始化 队列没被访问过显示顶点向量入队出队访问下一个顶点向量void MBFS(MGraph *Mg )邻接矩阵表示的图的广度优先遍历 初始化 visited初始化 队列没被访问过显示顶点向量入队出队访问下一个顶点向量/-主函数-main() 定义邻接矩阵和邻接表； 建立邻接矩阵和邻接表； 邻接矩阵MDFS深度优先遍历；邻接矩阵MBFS广度优先遍历；邻接表LDFS深度优先遍历；邻接表LBFS广度优先遍历6测试结果7. 参考文献数据结构8附录#include #include #include #include #define OK 1#define ERROR 0#define MAX_VERTEX_NUM20/*图的基本操作*/int visitedMAX_VERTEX_NUM;/ 访问标志数组/- 邻接矩阵数据类型的定义-/ 最大顶点个数typedef structchar vexsMAX_VERTEX_NUM;/ 顶点向量 intacrsMAX_VERTEX_NUMMAX_VERTEX_NUM;/ 邻接矩阵 intvexnum,arcnum;/ 图当前顶点数和弧数MGraph ;/-邻接表数据类型的定义-typedef struct ArcNodeint adjvex;/ 该弧所指向的顶点的位置 struct ArcNode *nextarc;/ 指向下一条弧的指针 ArcNode;typedef struct VNodechar data;/ 顶点信息ArcNode *firstarc;/ 指向第一条依附该顶点的弧的指针VNode, AdjListMAX_VERTEX_NUM;typedef structAdjList vertices; int vexnum,arcnum;/ 图当前顶点数和弧数 LGraph;/_队列函数_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;void EnQueue(Queue *Q,int w)/ 入队if(Q-rear+1)%MAX_VERTEX_NUM=Q-front)printf(Error!);elseQ-arryQ-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+1)%MAX_VERTEX_NUM;return u;/_队列函数end_/*函数：Create_Graph*功能：建立图的邻接矩阵，邻接表 *说明：该构建的为无向网 mg 为邻接矩阵 ，lg为邻接表 , 无权值 */int Locatevex(MGraph *Mg , char v)/ 确定 v 元素在Mg中的位置int i;for(i=0;Mg-vexsi!=v;i+);if(iMg-vexnum)/ 输入的元素不正确则显示 错误printf(ERROR );return i;/ 返回位置int Create_Graph( MGraph *Mg , LGraph *Lg ) / 建立图的邻接矩阵，邻接表 int i , j , k ;char v1 , v2 ;ArcNode *q,*p;printf(输入图的顶点数和弧数: ); scanf(%d %d,&Mg-vexnum,&Mg-arcnum);getchar();Lg-vexnum=Mg-vexnum;/ 邻接表的顶点数和弧数 Lg-arcnum=Mg-arcnum;for(i=0;ivexnum;i+)/ 构造顶点向量 printf(请输入一个图的顶点(字符):);scanf(%c , &Mg-vexsi);getchar();Lg-verticesi.data=Mg-vexsi; / 赋值Lg-verticesi.firstarc=NULL;/ 指向第一条依附该顶点的弧的指针 为空 for(i=0;ivexnum;i+)/ 初始化邻接矩阵for(j=0;jvexnum;j+)Mg-acrsij=0 ;for(k=0;karcnum;k+)/ 构造邻接矩阵和邻接表printf(请输入一条边连接的2个顶点：);scanf(%c %c,&v1,&v2);getchar();i=Locatevex(Mg,v1);/ 确定 v1 在Mg 中的位置j=Locatevex(Mg,v2);/ 确定 v2 在Mg 中的位置Mg-acrsji=Mg-acrsij=1;/ 置v1,v2的对称弧v2,v1p=(ArcNode *)malloc(sizeof(ArcNode); p-adjvex=i;/ 确认顶点位置p-nextarc=Lg-verticesj.firstarc;/ 指向下一条弧的指针Lg-verticesj.firstarc=p;/ 赋值q=(ArcNode *)malloc(sizeof(ArcNode); q-adjvex=j;/ 确认顶点位置 q-nextarc=Lg-verticesi.firstarc;/ 指向下一条弧的指针Lg-verticesi.firstarc=q;/ 赋值return OK ; /*函数：LDFS*功能：邻接表表示的图的递归深度优先遍历*说明：*/int LAdjVex(LGraph *Lg,int k)/ 位置 ArcNode *p;for(p=Lg-verticesk.firstarc;p!=NULL;p=p-nextarc)if(!visitedp-adjvex)return p-adjvex;return -1;void LDFS(LGraph *Lg,int i) int k;visitedi=OK;printf(%c,Lg-verticesi.data);for(k=LAdjVex(Lg,i);k=0;k=LAdjVex(Lg,k)if(!visitedk)LDFS(Lg,k);/*函数：MDFS*功能：邻接矩阵表示的图的递归深度优先遍历*说明：*/int AdjVes(MGraph *Mg,int k)/ 位置 int i;for(i=0;ivexnum;i+)if(Mg-acrski&(!visitedi)return i;return -1;void MDFS(MGraph *Mg,int i)/ 递归深度优先遍历int k;visitedi=1;/ 访问标志数组某位 置 1printf(%c,Mg-vexsi);/ 显示for(k=AdjVes(Mg,i);k=0;k=AdjVes(Mg,k)if(!visitedk)MDFS(Mg,k);/ 递归/*函数：LBFS*功能：邻接表表示的图的广度优先遍历 *说明：*/void LBFS( LGraph *Lg )int i,u,w;for(i=0;ivexnum;+i)/ 初始化 visitedvisitedi=0;InitQueue();/ 初始化 队列for(i=0;ivexnum;+i)if(!visitedi)/ 没被访问过visitedi=1;printf(%c,Lg-verticesi.data);EnQueue(&Q,i);/ 入队while(!QueueEmpty(&Q)u=DeQueue(&Q);/ 出队for(w=LAdjVex(Lg,u);w=0;w=LAdjVex(Lg,u)if(!visitedw)/ 没被访问过visitedw=1;printf(%c,Lg-verticesw.data);EnQueue(&Q,w);/ 入队/*函数：MBFS*功能：邻接矩阵表示的图的广度优先遍历*说明：*/void MBFS(MGraph *Mg )int i,w,u;for(i=0;ivexnum;i+)/ 初始化 visitedvisitedi=0; InitQueue();/ 初始化队列for(i=0;ivexnum;+i)if(!visitedi)/ 没被访问过visitedi=1;printf(%c,Mg-vexsi);/ 显示EnQueue(&Q,i);/ 入队while(!QueueEmpty(&Q)u=DeQueue(&Q);/ 出队for(w=AdjVes(Mg,u);w=0;w=AdjVes(Mg,u) if(!visitedw)/ 没被访问过visitedw=1;printf(%c,Mg-vexsw); / 显示EnQueue(&Q,w);/ 入队/*主函数*/void main()int i ;MGraph Mg;LGraph Lg;Create_Grap