数据结构与算法实验——图的基本操作

1、图的基本操作实验报告图的基本操作实验报告 实验名称图的基本操作实验目的1. 掌握图的各种存储结构，特别要熟练掌握邻接矩阵和邻接表的存储结构；2. 遍历是图各种应用的算法的基础，要熟练掌握图的深度优先遍历和广度优先遍历的算法，复习栈和队列的应用；3. 掌握以邻接矩阵作为存储结构的生成图的最小生成树的普利姆算法；实验内容编制一个演示图的邻接表的创建、深度遍历、广度遍历操作的程序。问题描述用数据结构相关知识，实现邻接表的定义和操作。该程序包括图的邻接表的结点类型定义以及对图操作的具体的函数定义（包括：建立图的邻接表、深度优先遍历图、广度优先遍历图）。问题分析该实验是基于C语言和数据结构知识基础的对图

2、的基本操作的检验，无需设计复杂的算法，程序语句也相对简单。因此，我直接按要求定义了对图操作的具体函数，并于主函数中实现对应的功能调用。 实验步骤1需求分析    本演示程序用VC+编写，完成图的邻接表的生成、遍历基本操作。  输入的形式和输入值的范围：在输入邻接表顶点信息前，必须先确定该信息能正确创建邻接表。   输出的形式：在所有三种操作中都显示操作是否正确以及操作后图的内容。   程序所能达到的功能：完成图的邻接表的生成、深度优先遍历、广度优先遍历基本操作。   测试数据：创建操作中依次输入

3、7,7作为顶点数和边数，以（0,1）（0,2）（1,3）（1,5）（3,4）（3,6）（4,5）作为各顶点信息生成一个邻接表。 2概要设计   1）为了实现上述程序功能，需要定义二叉树的抽象数据类型：   ADT Graph   数据对象：顶点的有穷非空集合和边的集合数据关系：结点具有相同的数据类型及层次结构 基本操作： Void InitGraph(ALGraph *G)    初始条件：无   

4、0;操作结果：初始化图  Void DFSTraverse(ALGraph *G)     初始条件：图Graph已存在    操作结果：按深度优先遍历图的邻接表Void BFSTraverse(ALGraph *G)     初始条件：图Graph已存在    操作结果：按广度优先遍历图的邻接表2）本程序包含7个函数：   主函数main()  

5、建立一个图的邻接表函数CreateGraphAL () 深度优先遍历图 DFS ()广度优先遍历 BFS() 函数说明#include <stdio.h>#include <stdlib.h>#define MaxVertexNum 100#define QueueSize 30 typedef enumFALSE,TRUEBoolean; Boolean visitedMaxVertexNum; typedef char VertexType;typedef int EdgeType;typedef struct node/边表结点int adjvex;/邻

6、接点域struct node *next;/域链/若是要表示边上的权,则应增加一个数据域EdgeNode;typedef struct vnode/顶点边结点VertexType vertex;/顶点域EdgeNode *firstedge;/边表头指针VertexNode;typedef VertexNode AdjListMaxVertexNum;/AdjList是邻接表类型typedef struct AdjList adjlist;/邻接表int n,e;/图中当前顶点数和边数ALGraph;void CreateGraphAL (ALGraph *G) int i,j,k; Edge

7、Node * s; printf("请输入顶点数和边数(输入格式为:顶点数,边数)：n"); scanf("%d,%d",&(G->n),&(G->e); / 读入顶点数和边数 printf("请输入顶点信息(输入格式为:顶点号<CR>)每个顶点以回车作为结束:n"); for (i=0;i<G->n;i+) / 立有n个顶点的顶点表 scanf("n%c",&(G->adjlisti.vertex); / 读入顶点信息 G->adjlisti

8、.firstedge=NULL; / 点的边表头指针设为空 printf("请输入边的信息(输入格式为:i,j)：n"); for (k=0;k<G->e;k+) / 建立边表 scanf("n%d,%d",&i,&j); / 读入边<Vi,Vj>的顶点对应序号 s=new EdgeNode; / 生成新边表结点s s->adjvex=j; / 邻接点序号为j s->next=G->adjlisti.firstedge; / 将新边表结点s插入到顶点Vi的边表头部 G->adjlisti.f

9、irstedge=s; s=new EdgeNode;s->adjvex=i;s->next=G->adjlistj.firstedge;G->adjlistj.firstedge=s; /*/* 深度优先遍历 */*/ void DFS(ALGraph *G,int i) /以vi为出发点对邻接表表示的图G进行深度优先搜索 EdgeNode *p;printf("visit vertex:%cn",G->adjlisti.vertex); / 访问顶点vivisitedi=TRUE; /标记vi已访问p=G->adjlisti.firs

10、tedge; /取vi边表的头指针while(p)/依次搜索vi的邻接点vj，这里j=p->adjvexif (!visitedp->adjvex)/若vi尚未被访问DFS(G,p->adjvex);/则以Vj为出发点向纵深搜索p=p->next; /找vi的下一邻接点void DFSTraverseM(ALGraph *G) int i; for(i=0;i<G->n;i+) visitedi=FALSE; for(i=0;i<G->n;i+) if(!visitedi) DFS(G,i); /*/* 广度优先遍历 */*/typedef st

11、ruct int front; int rear; int count; int dataQueueSize; CirQueue; void InitQueue(CirQueue *Q) Q->front=Q->rear=0; Q->count=0; int QueueEmpty(CirQueue *Q) return Q->front=Q->rear; int QueueFull(CirQueue *Q) return (Q->rear+1)%QueueSize=Q->front; void EnQueue(CirQueue *Q,int x) if

12、 (QueueFull(Q) printf("Queue overflow"); else Q->count+; Q->dataQ->rear=x; Q->rear=(Q->rear+1)%QueueSize; int DeQueue(CirQueue *Q) int temp; if(QueueEmpty(Q) printf("Queue underflow"); return false; else temp=Q->dataQ->front; Q->count-; Q->front=(Q->

13、front+1)%QueueSize; return temp; void BFS(ALGraph*G,int k)/ 以vk为源点对用邻接表表示的图G进行广度优先搜索 int i;CirQueue Q;/须将队列定义中DataType改为intEdgeNode *p;InitQueue(&Q);/队列初始化printf("visit vertex:%cn",G->adjlistk.vertex);/访问源点vkvisitedk=TRUE; EnQueue(&Q,k);/vk已访问，将其人队。（实际上是将其序号人队）while(!QueueEmpty(

14、&Q)/队非空则执行i=DeQueue(&Q);/相当于vi出队p=G->adjlisti.firstedge;/取vi的边表头指针while(p)/依次搜索vi的邻接点vj(令p->adjvex=j)if(!visitedp->adjvex)/若vj未访问过printf("visit vertex:%cn",G->adjlistp->adjvex.vertex);/访问vjvisitedp->adjvex=TRUE; EnQueue(&Q,p->adjvex);/访问过的vj人队p=p->next;/

15、找vi的下一邻接点void BFSTraverseM(ALGraph *G) int i; for (i=0;i<G->n;i+) visitedi=FALSE; for (i=0;i<G->n;i+) if (!visitedi) BFS(G,i); /*/* 主函数调用 */*/int main()int n; ALGraph G; CreateGraphAL(&G); printf("深度优先遍历：n");DFSTraverseM(&G); printf("广度优先遍历：n");BFSTraverseM(&a

16、mp;G);return 0;程序流程图开始访问V,置标志求V邻接点有邻接点w？求下一邻接点wV W访问过？返回NYNY深度优先遍历流程图开始结束初始化visitvV入队列对头元素出队，W= FirstAdjVex(G,u)初始化visitedv V入队列w=NextAdjVex(G,u,w)!IsEmptyQueue(Q)w!=-1YYNN广度优先遍历流程图调试报告发现问题：1. 在创建图的邻接表以后，得到的深度优先遍历和自己在草稿纸上演算得到的序列不符。2. 在创建图的邻接表以后，得到的广度优先遍历和自己在草稿纸上演算得到的序列不符。调试：1. 仔细检查程序后，发现是因为创建邻接表的方法是

17、头插法；2. 检查程序，发现依据队列的长度而判断队满和队空的条件不能实现。解决方案：1. 我重新在草稿纸上对用头插法建立的邻接表进行深度遍历；2. 将队满的条件修改为：(rear+1)%QueueSize=front;将队空的条件修改为：rear=front结果：结果运行正确！使用说明建立邻接表深度优先遍历广度优先遍历心得体会数据结构顾名思义讲求的是一种存储结构，一路走来先后学习了表、树，最后学习的是图，对于每种存储结构学习之初都会学习一些基本操作，而操作之中又以创建和遍历为最基本的操作，只有熟练掌握了以后才能对其他操作进行研究和学习。 图的存储结构相比表和树都要复杂，其操作过程也较难进行掌握。仅仅是创建图的存储结构便分为矩阵、临接链表、十字链表等，对于每一种存储结构又分为有向与无向之分。然而，深度优先和广度优先是两种算法，