数据结构上机实验报告学号：20111004258姓名：刘龙3.4 图 1、实验目的 （1）熟悉图的数组表示法和邻接表存储结构。 （2）掌握构造有向图、无向图的算法。 （3）在掌握以上知识的基础上，熟悉图的深度优先遍历算法和广度优先遍历算法，并实现 之。 2、实验要求 （1）图的数组表示法（邻接矩阵）定义及基本操作的实现。 （2）图的邻接表表示法及基本操作的实现。 （3）写出函数实现图的深度优先遍历（分别在两种结构上） 。 （4）在邻接表上实现关键路径的球阀，在邻接矩阵上实现最短路径、最小生成树的求法。 3、实验内容 实验 图的邻接表表示法和遍历算法 （1）以邻接表作为存储结构，定义图结点 vertexnode； （2）实现图的下列运算：a 以邻接表作为存储结构建立图 b 按照深度遍历算法遍历图 c 按照广度遍历算法遍历图。 #include #define MaxVertexNum 100 #define QueueSize 30 typedef enumFALSE,TRUEBoolean; Boolean visitedMaxVertexNum; typedef char VertexType; typedef int EdgeType; typedef struct node /边表结点 int adjvex; /邻接点域 struct node *next; /域链 /若是要表示边上的权,则应增加一个数据域 EdgeNode; typedef struct vnode /顶点边结点 VertexType vertex; / 顶点域 EdgeNode *firstedge;/ 边表头指针 VertexNode; typedef VertexNode AdjListMaxVertexNum; /AdjList 是邻接表类型 typedef struct AdjList adjlist; /邻接表 int n,e; /图中当前顶点数和边数 ALGraph; /对于简单的应用，无须定义此类型，可直接使用 AdjList 类 型 /*/ /* 建立无向图的邻接表算法 */ /*/ void CreateGraphAL (ALGraph *G) int i,j,k; EdgeNode * s; printf(“请输入顶点数和边数(输入格式为: 顶点数,边数) ：/n“); scanf(“%d,%d“, / 读入顶点数和边数 printf(“请输入顶点信息(输入格式为: 顶点号) 每个顶点以回车作为结束:/n“); for (i=0;in;i+) / 立有 n 个顶点的顶点表 scanf(“/n%c“, / 读入顶点信息 G-adjlisti.firstedge=NULL; / 点的边表头指针设为空 printf(“请输入边的信息(输入格式为:i,j)：/n“); for (k=0;ke;k+) / 建立边表 scanf(“/n%d,%d“, / 读入边 的顶点对应序号 s=new EdgeNode; / 生成新边表结点 s s-adjvex=j; / 邻接点序号为 j s-next=G-adjlisti.firstedge; / 将新边表结点 s 插入到顶点 Vi 的边表头部 G-adjlisti.firstedge=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:%c/n“,G-adjlisti.vertex); / 访问顶点 vi visitedi=TRUE; / 标记 vi 已访问 p=G-adjlisti.firstedge; / 取 vi 边表的头指针 while(p) /依次搜索 vi 的邻接点 vj，这里 j=p-adjvex if (!visitedp-adjvex) /若 vi 尚未被访问 DFS(G,p-adjvex); /则以 Vj 为出发点向纵深搜索 p=p-next; /找 vi 的下一邻接点 void DFSTraverseM(ALGraph *G) int i; for(i=0;in;i+) visitedi=FALSE; for(i=0;in;i+) if(!visitedi) DFS(G,i); /*/ /* 广度优先遍历 */ /*/ typedef struct 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-count=QueueSize; int QueueFull(CirQueue *Q) return Q-count=QueueSize; void EnQueue(CirQueue *Q,int x) if (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 NULL; else temp=Q-dataQ-front; Q-count-; Q-front=(Q-front+1)%QueueSize; return temp; void BFS(ALGraph*G,int k) / 以 vk 为源点对用邻接表表示的图 G 进行广度优先搜索 int i; CirQueue Q; /须将队列定义中 DataType 改为 int EdgeNode *p; InitQueue( /队列初始化 printf(“visit vertex:%c/n“,G-adjlistk.vertex); /访问源点 vk visitedk=TRUE; EnQueue( /vk 已访问，将其人队。 （实际上是将其序号人队） while(!QueueEmpty( / 相当于 vi 出队 p=G-adjlisti.firstedge; / 取 vi 的边表头指针 while(p) /依次搜索 vi 的邻接点 vj(令 p-adjvex=j) if(!visitedp-adjvex) /若 vj 未访问过 printf(“visit vertex:%c“,G-adjlistp-adjvex.vertex); / 访问 vj visitedp-adjvex=TRUE; EnQueue( / 访问过的 vj 人队 p=p-next; /找 vi 的下一邻接点 void BFSTraverseM(ALGraph *G)