实验五图的操作及应用

《实验五图的操作及应用》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验五：图的操作及应用实验学时：4实验类型：综合型一、实验目的1.理解图的逻辑结构和物理结构；2.掌握图的邻接矩阵和邻接表存储表示的实现方法;3.掌握图的深度优先和广度优先遍丿力算法的实现；4.掌握拓扑排序算法的实现方法。二、实验条件VisualC++6.0三、实验原理及相关知识1.图的邻接矩阵和邻接表存储结构的描述;2.图的邻接矩阵和邻接表存储表示的算法;3.图的深度优先和广度优先遍历算法；4.拓扑排序算法。四、实验步轴1.实现图的邻接矩阵的存储表示。2.实现图的邻接表存储表示。3.实现图的深度优先和广度优先遍历算法。4.实现拓扑排序

2、算法。5.调用以上函数实现以下操作：(1)建立图。(2)输；I〔基于邻接表存储的深度优先和广度优先遍丿力序列o(3)输出有向图的拓扑排序序列。参考代码：要求：补充完整以下代码使其能够运行通过。#includeHstdio.hH#includeHmalloc>hn#includenstring>hu#defineINFINITY10000//用整型最大值代替8#defineMAX_VERTEX_NUM20//最大顶点个数#defineOK1#defineERROR0#defineFALSE0#defineTRUE1#defineMAXQS

3、IZE100typedefintQElemType;typedeffloatVRType;typedeffloatInfoType;typedefcharVertexType;typedefcharVexType;〃==™====二二邻接矩阵的定义============typedefstruct{VRTypeadj;InfoTypeinfo;//该弧相关信息的指针（可无）}ArcCell?AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{VertexTypevexs[MAX

4、_VERTEX_NUM][100];//顶点向量AdjMatrixarcs;//邻接矩阵intvexnum,arcnum;//图的当前顶点数和弧数}MGraph;邻接表的定义===//表结点//该弧所指向的顶点的位置//指向下一条弧的指针//网的权值指针//头结点//顶点信息//第一个表结点的地址//=======================邻接矩阵的定义========typedefstructArcNode{intadjvex;structArcNode*nextarc;floatinfo;}ArcNode;typedefstr

5、uctfVertexTypedata[100];ArcNode*firstarc;}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct{AdjListvertices;intvexnum,arcnum;//图的当前顶点数和弧数}ALGraph;intvisited[MAX_VERTEX_NUM];7/=================^接表的定义=========================〃二=======队列定义和基本操作===============typedefstructQNodel{Q

6、ElemTypedata;structQNodel*next;}QNode，*QueuePtr;typedefstruct{〃链队列的定义QElemType*base;intfront;intrear;}SqQueue;typedefstructfQueuePtrfront;QueuePtrrear;}LinkQueue;LinkQueueInitQueue(LinkQueueQ){Q>front=Qerear=(QueuePtr)malloc(sizeof(QNode));if(!Q.front)exit(l);Q.front->ne

7、xt=NULL;returnQ;}intEnQueue(LinkQueue*Q,QElemTypee){QueuePtrp;if(!(p=(QueuePtr)malloc(sizeof(QNode))))returnERROR;p->data=e;p->next=NULL;Q・>rear->next=p;Q->rear=p;returnOK;}intDeQueue(LinkQueue*Q,QElemType*e){QueuePtrp;if(Q->front==Q->rear)returnERROR;p=Q->front->next;*e

8、=p->data;Q・>front->next=p->next;if(Q->rear==p)Q->rear=Q->front;free(p);returnOK;}intQueueEmpty(LinkQueu