实验五 图的存储与遍历

数据结构实验五---图的遍历及其应用实现实验五图的遍历及其应用实现一、实验目的1．熟悉图常用的存储结构。

2．掌握在图的邻接矩阵和邻接表两种结构上实现图的两种遍历方法实现。

3．会用图的遍历解决简单的实际问题。

二、实验内容[题目] ：从键盘上输入图的顶点和边的信息,建立图的邻接表存储结构,然后以深度优先搜索和广度优先搜索遍历该图,并输出起对应的遍历序列. 试设计程序实现上述图的类型定义和基本操作,完成上述功能。

该程序包括图类型以及每一种操作的具体的函数定义和主函数。

三、实验步骤（一）、数据结构与核心算法的设计描述：本实验主要在于图的基本操作，关键是图的两种遍历，仔细分析图的遍历的特点，不难发现，其符合递归的特点，因此可以采用递归的方法遍历。

本实验图的存储结构主要采用邻接表，总共分为四个模块：图的创建、位置的查找、深度优先遍历、广度优先遍历。

以下是头文件中数据结构的设计和相关函数的声明：#include#include#include#nclude#define OVERFLOW -2#define MAX_VERTEX_NUM 50 //最大顶点数#define MAXQSIZE 100# define OK 1typedef int VRType;typedef int InfoType;typedef int QElemType;typedef enum{DG,DN,UDG,UDN}GraphKind;typedef struct ArcNode // 弧结点{int adjvex; //邻接点域，存放与Vi邻接的点在表头数组中的位置struct ArcNode *nextarc; //链域指向vi的下一条边或弧的结点，InfoType *info; //定义与弧相关的权值，无权则为0 }ArcNode;typedef struct VNode //表头结点{char vexdata; //存放顶点信息struct ArcNode *firstarc; //指示第一个邻接点}VNode,AdjList[MAX_VERTEX_NUM];typedef struct{ //图的结构定义AdjList vertices; //顶点向量int vexnum, arcnum; //vexnum为顶点数arcnum为弧或边的个数GraphKind kind; // 图的种类标志}MGraph;typedef struct Queue //构建循环队列{QElemType *base;int front;int rear;}Queue;void CreateGraph(MGraph &G); //图的创建void DFSTraverse(MGraph &G) ; //深度优先遍历void BFSTraverse(MGraph &G); //广度优先遍历int LocateVex(MGraph &G, char &v);//查找顶点v的位置（二）、函数调用及主函数设计void main(){int x;MGraph G;CreateGraph(G);cout<<"创建图成功!"<<endl;< p="">cout<<"1 深度优先搜索"<<endl<<"2 p="" 广度优先搜索"<<endl;<="">cin>>x;if(x==1){DFSTraverse(G);cout<<"深度优先搜索结束!"<<endl;< p="">}else if(x==2){BFSTraverse(G);cout<<"广度优先搜索结束!"<<endl;< p="">}elsecout<<"输入有误!"<<endl<<"再见!"<<endl;< p="">}（三）、实验总结由于图的基本操作在图这一章节中起着很主要的作用，所以在实验前就对实验做了充分的准备，实验的成功核心在于两种遍历的实现，因此只有充分理解遍历算法的精髓，才能更好的做好实验。

数据结构实验报告图的遍历讲解一、引言在数据结构实验中，图的遍历是一个重要的主题。

图是由顶点集合和边集合组成的一种数据结构，常用于描述网络、社交关系等复杂关系。

图的遍历是指按照一定的规则，挨次访问图中的所有顶点，以及与之相关联的边的过程。

本文将详细讲解图的遍历算法及其应用。

二、图的遍历算法1. 深度优先搜索（DFS）深度优先搜索是一种常用的图遍历算法，其基本思想是从一个顶点出发，沿着一条路径向来向下访问，直到无法继续为止，然后回溯到前一个顶点，再选择此外一条路径继续访问。

具体步骤如下：（1）选择一个起始顶点v，将其标记为已访问。

（2）从v出发，选择一个未被访问的邻接顶点w，将w标记为已访问，并将w入栈。

（3）如果不存在未被访问的邻接顶点，则出栈一个顶点，继续访问其它未被访问的邻接顶点。

（4）重复步骤（2）和（3），直到栈为空。

2. 广度优先搜索（BFS）广度优先搜索是另一种常用的图遍历算法，其基本思想是从一个顶点出发，挨次访问其所有邻接顶点，然后再挨次访问邻接顶点的邻接顶点，以此类推，直到访问完所有顶点。

具体步骤如下：（1）选择一个起始顶点v，将其标记为已访问，并将v入队。

（2）从队首取出一个顶点w，访问w的所有未被访问的邻接顶点，并将这些顶点标记为已访问，并将它们入队。

（3）重复步骤（2），直到队列为空。

三、图的遍历应用图的遍历算法在实际应用中有广泛的应用，下面介绍两个典型的应用场景。

1. 连通分量连通分量是指图中的一个子图，其中的任意两个顶点都是连通的，即存在一条路径可以从一个顶点到达另一个顶点。

图的遍历算法可以用来求解连通分量的个数及其具体的顶点集合。

具体步骤如下：（1）对图中的每一个顶点进行遍历，如果该顶点未被访问，则从该顶点开始进行深度优先搜索或者广度优先搜索，将访问到的顶点标记为已访问。

（2）重复步骤（1），直到所有顶点都被访问。

2. 最短路径最短路径是指图中两个顶点之间的最短路径，可以用图的遍历算法来求解。

数据结构课程设计报告样本（图的存储与遍历）这是最后提交的文档资料格式，必须包含几个部分，如果是四到五个人完成要求文档不少于70页，3-4个人完成要求不少于50页。

《数据结构》课程设计题目图的存储与遍历学生姓名指导教师学院专业班级完成时间目录（要求自动生成）第一章课程设计目的 (2)第二章课程设计内容和要求 (2)第三章课程设计分析 (3)第四章算法描述 (4)第五章源代码 (8)第六章运行结果分析 (13)第七章结束语 (15)第八章参考文献 (15)第一章课程设计目的本学期我们对《数据结构》这门课程进行了学习。

这门课程是一门实践性非常强的课程，为了让大家更好地理解与运用所学知识，提高动手能力，我们进行了此次课程设计实习。

这次课程设计不但要求实习者掌握《数据结构》中的各方面知识，还要求实习者具备一定的C语言基础和编程能力。

具体说来，这次课程设计主要有两大方面目的。

一是让实习者通过实习掌握《数据结构》中的知识。

对于《图的存储与遍历》这一课题来说，所要求掌握的数据结构知识主要有：图的邻接表存贮结构、队列的基本运算实现、邻接表的算法实现、图的广度优先搜索周游算法实现、图的深度优先搜索周游算法实现。

二是通过实习巩固并提高实习者的C语言知识，并初步了解Visual C++的知识，提高其编程能力与专业水平。

第二章课程设计内容和要求2.1课程设计内容组成员名称和分工（谁负责了哪个部分）该课题要求以邻接表的方式存储图，输出邻接表，并要求实现图的深度、广度两种遍历。

2.1.1图的邻接表的建立与输出对任意给定的图（顶点数和边数自定），并且对有向图与无向图都应进行讨论，根据邻接表的存储结构建立图的邻接表并输出之。

尽量用图形化的方式输出邻接表。

2.1.2 图的遍历的实现图的遍历包括图的广度优先遍历与深度优先遍历。

对于广度优先遍历应利用队列的五种基本运算（置空队列、进队、出队、取队头元素、判队空）来实现。

首先建立一空队列，从初始点出发进行访问，当被访问时入队，访问完出队。

实验报告June 11 2015姓名：陈斌学号：E11314079 专业：13计算机科学与技术数据结构第七次实验学号E11314079专业计算机科学与技术姓名陈斌实验日期2015.06.11教师签字成绩实验报告【实验名称】图的存储结构与遍历【实验目的】(1)掌握图的相关概念；(2)掌握图的存储结构；(3)掌握图的遍历算法并编程实现。

【实验内容】编写一个程序，实现图的相关运算，并在此基础上设计一个主程序，完成如下功能：(1)建立如教材图7.9所示的有向图G的邻接矩阵，并分别输出顶点表和邻接矩阵。

(2)由有向图G的邻接矩阵产生邻接表，并依次输出每一顶点和其邻接表。

(3)再由（2）的邻接表产生对应的邻接矩阵，并输出该矩阵。

(4)在图G的邻接矩阵存储表示基础上，输出从顶点V1开始的深度优先遍历序列（递归算法）。

(5)在图G的邻接表存储表示基础上，输出从顶点V1开始的广度优先遍历序列。

(6)利用非递归算法重解任务（4）（选做）。

源代码：head.h:#include<string.h>#include<ctype.h>#include<malloc.h> //malloc( )#include<limits.h> // INT ,MAX#include<stdio.h> //EOF,NULL#include<stdlib.h> //atoi( )#include<io.h> //eof( )#include<math.h> //floor( ),ceil( ),abs( )#include<process.h> //exit( )#include<iostream.h> //cout,cin//函数结果状态代码#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1//OVERFLOW 在math.h中已定义为3typedefint Status;typedefint Boolean; // 布尔类型main.cpp:#include"head.h"#define MAX_NAME 5 /* 顶点字符串的最大长度+1 */#define MAX_INFO 20 /* 相关信息字符串的最大长度+1 */typedefintVRType;typedefintInfoType;typedef char VertexType[MAX_NAME];#define INFINITY INT_MAX /* 用整型最大值代替∞*/#define MAX_VERTEX_NUM 20 /* 最大顶点个数*/typedefenum{DG,DN,AG,AN}GraphKind; /* {有向图,有向网,无向图,无向网} *//*图的数组(邻接矩阵)存储表示*/typedefstruct{VRTypeadj; /* 顶点关系类型。

实验题目:图的遍历实验描述:以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。

以用户指定的结点为起点，分别输出每种遍历下的结点访问序列和相应生成树的边集。

程序设计:#include"stdio.h"#include"stdlib.h"#define MaxVertexNum 30 /*定义最大顶点数*/typedef struct node{ /*边表结点*/int adjvex; /*邻接点域*/struct node *next; /*链域*/}EdgeNode;typedef struct vnode{ /*顶点表结点*/char vertex; /*顶点域*/EdgeNode *firstedge; /*边表头指针*/}VertexNode;typedef VertexNode AdjList[MaxVertexNum]; /*AdjList是邻接表类型*/typedef struct {AdjList adjlist; /*邻接表*/int n,e; /*图中当前顶点数和边数*/} ALGraph; /*图类型*//* 建立图的邻接表*/void CreatALGraph(ALGraph *G){int i,j,k;char a;EdgeNode *s; /*定义边表结点*/printf("请输入顶点数和边数: ");scanf("%d,%d",&G->n,&G->e); /*读入顶点数和边数*/scanf("%c",&a);printf("请输入顶点:");for(i=0;i<G->n;i++) /*建立边表*/{scanf("%c",&a);G->adjlist[i].vertex=a; /*读入顶点信息*/G->adjlist[i].firstedge=NULL; /*边表置为空表*/}printf("请输入边（Vi，Vj）的顶点对序号\n");for(k=0;k<G->e;k++) { /*建立边表*/scanf("%d%d",&i,&j); /*读入边（Vi，Vj）的顶点对序号*/s=(EdgeNode *)malloc(sizeof(EdgeNode)); /*/生成边表结点*/s->adjvex=j; /*邻接点序号为j*/s->next=G->adjlist[i].firstedge;G->adjlist[i].firstedge=s; /*将新结点*S插入顶点Vi的边表头部*/s=(EdgeNode *)malloc(sizeof(EdgeNode));s->adjvex=i; /*邻接点序号为i*/s->next=G->adjlist[j].firstedge;G->adjlist[j].firstedge=s; /*将新结点*S插入顶点Vj的边表头部*/}}/* 定义标志向量，为全局变量*/typedef enum{FALSE,TRUE} Boolean;Boolean visited[MaxVertexNum];/* DFS：深度优先遍历*/void DFSM(ALGraph *G,int i){ /*以Vi为出发点对邻接链表表示的图G进行DFS搜索*/ EdgeNode *p;printf("%c ",G->adjlist[i].vertex); /*访问顶点Vi*/visited[i]=TRUE; /*标记Vi已访问*/p=G->adjlist[i].firstedge; /*取Vi边表的头指针*/while(p) { /*依次搜索Vi的邻接点Vj，这里j=p->adjvex*/if(! visited[p->adjvex]) /*若Vj尚未被访问*/DFSM(G,p->adjvex); /*则以Vj为出发点向纵深搜索*/ p=p->next; /*找Vi的下一个邻接点*/}}void DFS(ALGraph *G){int i;for(i=0;i<G->n;i++)visited[i]=FALSE; /*标志向量初始化*/for(i=0;i<G->n;i++)if(!visited[i]) /*Vi未访问过*/DFSM(G,i); /*以Vi为源点开始DFS搜索*/}/* BFS：广度优先遍历*/void BFS(ALGraph *G,int k){ /*以Vk为源点对用邻接链表表示的图G进行广度优先搜索*/int i,f=0,r=0;EdgeNode *p;int cq[MaxVertexNum]; /*定义FIFO队列*/for(i=0;i<G->n;i++)visited[i]=FALSE; /*标志向量初始化*/for(i=0;i<=G->n;i++)cq[i]=-1; /*初始化标志向量*/printf("%c ",G->adjlist[k].vertex); /*访问源点Vk*/visited[k]=TRUE;cq[r]=k;while(cq[f]!=-1) { // 队列非空则执行i=cq[f]; f=f+1; /*Vi出队*/p=G->adjlist[i].firstedge; /*取Vi的边表头指针*/while(p) { /*依次搜索Vi的邻接点Vj（令p->adjvex=j）*/ if(!visited[p->adjvex]) { /*若Vj未访问过*/printf("%c ",G->adjlist[p->adjvex].vertex); /*访问Vj*/visited[p->adjvex]=TRUE;r=r+1; cq[r]=p->adjvex; /*访问过的Vj入队*/}p=p->next; /*找Vi的下一个邻接点*/}} /*endwhile*/}/* 主函数*/void main(){int i;ALGraph *G;G=(ALGraph *)malloc(sizeof(ALGraph));CreatALGraph(G);printf("DFS：深度优先遍历: ");DFS(G);printf("\n");printf("BFS：广度优先遍历: ");BFS(G,3);printf("\n");}测试数据:1.顶点: 4边数: 3顶点:bdac边（Vi，Vj）的顶点对序号(0,1) (0,2) (1,3)2. 顶点:1 边数:0顶点:k。

图的遍历的实验报告图的遍历的实验报告一、引言图是一种常见的数据结构，它由一组节点和连接这些节点的边组成。

图的遍历是指从图中的某个节点出发，按照一定的规则依次访问图中的所有节点。

图的遍历在许多实际问题中都有广泛的应用，例如社交网络分析、路线规划等。

本实验旨在通过实际操作，深入理解图的遍历算法的原理和应用。

二、实验目的1. 掌握图的遍历算法的基本原理；2. 实现图的深度优先搜索（DFS）和广度优先搜索（BFS）算法；3. 比较并分析DFS和BFS算法的时间复杂度和空间复杂度。

三、实验过程1. 实验环境本实验使用Python编程语言进行实验，使用了networkx库来构建和操作图。

2. 实验步骤（1）首先，我们使用networkx库创建一个包含10个节点的无向图，并添加边以建立节点之间的连接关系。

（2）接下来，我们实现深度优先搜索算法。

深度优先搜索从起始节点开始，依次访问与当前节点相邻的未访问过的节点，直到遍历完所有节点或无法继续访问为止。

（3）然后，我们实现广度优先搜索算法。

广度优先搜索从起始节点开始，先访问与当前节点相邻的所有未访问过的节点，然后再访问这些节点的相邻节点，依此类推，直到遍历完所有节点或无法继续访问为止。

（4）最后，我们比较并分析DFS和BFS算法的时间复杂度和空间复杂度。

四、实验结果经过实验，我们得到了如下结果：（1）DFS算法的时间复杂度为O(V+E)，空间复杂度为O(V)。

（2）BFS算法的时间复杂度为O(V+E)，空间复杂度为O(V)。

其中，V表示图中的节点数，E表示图中的边数。

五、实验分析通过对DFS和BFS算法的实验结果进行分析，我们可以得出以下结论：（1）DFS算法和BFS算法的时间复杂度都是线性的，与图中的节点数和边数呈正比关系。

（2）DFS算法和BFS算法的空间复杂度也都是线性的，与图中的节点数呈正比关系。

但是，DFS算法的空间复杂度比BFS算法小，因为DFS算法只需要保存当前路径上的节点，而BFS算法需要保存所有已访问过的节点。

数据结构实验总结及心得体会引言数据结构作为计算机科学的基础课程，是理解和应用计算机编程的重要部分。

通过实验的形式，我们可以更加深入地理解不同数据结构的特点和应用场景。

本文将总结我在数据结构实验中的学习经验和心得体会。

实验一：线性表在线性表实验中，我学习了顺序表和链表两种基本的线性表结构。

顺序表使用数组来存储数据，具有随机访问的特点；链表使用指针来连接数据元素，具有插入和删除操作方便的特点。

通过这个实验，我深刻认识了线性表的存储结构和操作方法。

我遇到的难点是链表的插入和删除操作，因为涉及到指针的重新指向。

通过调试和分析代码，我逐渐理解了指针指向的含义和变化规律。

在实验结束后，我还进一步学习了循环链表和双向链表的特点和应用。

实验二：栈和队列栈和队列是两种常用的数据结构，可以用来解决很多实际问题。

在这个实验中，我学习了顺序栈、链式栈、顺序队列和链式队列四种基本实现方式。

实验中我遇到的最大困难是队列的循环队列实现，因为需要处理队列尾指针的位置变化。

我通过画图和调试发现了队列尾指针的变化规律，并在实验中成功实现了循环队列。

熟练掌握了栈和队列的操作方法后，我进一步学习了栈的应用场景，如表达式求值和括号匹配等。

队列的应用场景还有优先级队列和循环队列等。

实验三：串串是由零个或多个字符组成的有限序列，是实际应用中十分常见的数据类型。

在这个实验中，我学习了串的存储结构和常规操作。

实验中最具挑战性的部分是串的模式匹配。

模式匹配是在一个主串中查找一个子串的过程，可以使用暴力匹配、KMP 算法和BM算法等不同的匹配算法。

在实验中，我实现了KMP算法，并在实际应用中进行了测试。

从实验中我学到了使用前缀表和后缀表来提高模式匹配的效率。

同时，在应用中也了解到了串的搜索和替换等常见操作。

实验四：树和二叉树树是一种重要的非线性数据结构，应用广泛。

在这个实验中，我学习了树的基本概念、存储结构和遍历方式。

实验中最困难的部分是二叉树的遍历。

图的遍历实验报告图的遍历实验报告一、引言图是一种常见的数据结构，广泛应用于计算机科学和其他领域。

图的遍历是指按照一定规则访问图中的所有节点。

本实验通过实际操作，探索了图的遍历算法的原理和应用。

二、实验目的1. 理解图的遍历算法的原理；2. 掌握深度优先搜索（DFS）和广度优先搜索（BFS）两种常用的图遍历算法；3. 通过实验验证图的遍历算法的正确性和效率。

三、实验过程1. 实验环境准备：在计算机上安装好图的遍历算法的实现环境，如Python编程环境；2. 实验数据准备：选择合适的图数据进行实验，包括图的节点和边的信息；3. 实验步骤：a. 根据实验数据，构建图的数据结构；b. 实现深度优先搜索算法；c. 实现广度优先搜索算法；d. 分别运行深度优先搜索和广度优先搜索算法，并记录遍历的结果；e. 比较两种算法的结果，分析其异同点；f. 对比算法的时间复杂度和空间复杂度，评估其性能。

四、实验结果与分析1. 实验结果：根据实验数据和算法实现，得到了深度优先搜索和广度优先搜索的遍历结果；2. 分析结果：a. 深度优先搜索：从起始节点出发，一直沿着深度方向遍历，直到无法继续深入为止。

该算法在遍历过程中可能产生较长的路径，但可以更快地找到目标节点，适用于解决一些路径搜索问题。

b. 广度优先搜索：从起始节点出发，按照层次顺序逐层遍历，直到遍历完所有节点。

该算法可以保证找到最短路径，但在遍历大规模图时可能需要较大的时间和空间开销。

五、实验总结1. 通过本次实验，我们深入理解了图的遍历算法的原理和应用；2. 掌握了深度优先搜索和广度优先搜索两种常用的图遍历算法；3. 通过实验验证了算法的正确性和效率；4. 在实际应用中，我们需要根据具体问题的需求选择合适的遍历算法，权衡时间复杂度和空间复杂度；5. 进一步研究和优化图的遍历算法，可以提高算法的性能和应用范围。

六、参考文献[1] Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.[2] Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.). Addison-Wesley Professional.。

武汉东湖学院
实验报告
学院：计算机科学学院专业计算机科学与技术2016年11月18日
姓名付磊学号42
班级计科一班指导老师吴佳芬
课程名称数据结构成
绩
实验名称图的存储结构和遍历
1．实验目的
（1）了解邻接矩阵存储法和邻接表存储法的实现过程。

（2）了解图的深度优先遍历和广度优先遍历的实现过程。

2．实验内容
1. 采用图的邻接矩阵存储方法，实现下图的邻接矩阵存储，并输出该矩阵.
2. 设计一个将第1小题中的邻接矩阵转换为邻接表的算法，并设计一个在屏幕上显示邻接表的算法
3. 实现基于第2小题中邻接表的深度优先遍历算法，并输出遍历序列
4. 实现基于第2小题中邻接表的广度优先遍历算法，并输出遍历序列
3．实验环境
Visual C++ 6.0
4．实验方法和步骤（含设计）
我们通过二维数组中的值来表示图中节点与节点的关系。

通过上图可知，其邻接矩阵示意图为如下：
V0 v1 v2 v3 v4 v5
V0 0 1 0 1 0 1
V1 1 0 1 1 1 0
V2 0 1 0 0 1 0
V3 1 1 0 0 1 1
V4 0 1 1 1 0 0
V5 1 0 0 1 0 0
此时的“1”表示这两个节点有关系，“0”表示这两个节点无关系。

我们通过邻接表来在计算机中存储图时，其邻接表存储图如下：
}。

实验7图的两种存储和遍历一、实验内容：（1）键盘输入数据，分别建立一个有向图和一个无向图的邻接表。

（2）输出该邻接表。

（3）在有向图的邻接表的基础上计算各顶点的度，并输出。

（4）采用邻接表存储实现无向图的深度优先遍历。

（5）采用邻接表存储实现无向图的广度优先遍历。

（6）在主函数中设计一个简单的菜单，分别调试上述算法。

二、源代码：#include<stdio.h>#include<stdlib.h>#include<conio.h>#define MAX_VERTEX_NUM 20#define OK 1#define ERROR 0#define OVERFLOW 0int visited[MAX_VERTEX_NUM];//表结点typedef struct ArcNode{int adjvex;struct ArcNode *nextarc;char *info;}ArcNode;//头结点typedef struct VNode{char data;ArcNode *firstarc;}VNode,AdjList[MAX_VERTEX_NUM];//图结构typedef struct{AdjList vertices;int vexnum,arcnum;}ALGraph;//用于BFS遍历的附设链队列结点结构typedef struct QNode{int data;struct QNode *next;}QNode,*QueuePtr;//链队列typedef struct{QueuePtr front;QueuePtr rear;}LinkQueue;//初始化链队int InitQueue(LinkQueue &Q){Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)); if(!Q.front) exit(OVERFLOW);Q.front->next=NULL;return OK;}//元素e入队int EnQueue(LinkQueue &Q,int e){QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode));if(!p) exit(OVERFLOW);p->next=NULL;p->data=e;Q.rear->next=p;Q.rear=p;return OK;}//队首元素出队,由e返回其值int DeQueue(LinkQueue &Q,int &e){QueuePtr p;if(Q.front==Q.rear) exit(OVERFLOW);p=Q.front->next;e=p->data;Q.front->next=p->next;if(Q.rear==p)Q.rear=Q.front;free(p);return OK;}//判断队列Q是否为空int EmptyQueue(LinkQueue Q){if(Q.front==Q.rear)return 1;return 0;}//查找值为v的顶点在顶点向量G.vexs[]中的位置int LocateVex(ALGraph G,char v){int i;for(i=0;i<G.vexnum;i++)if(v==G.vertices[i].data)return i;return -1;}//返回v的第一个邻接顶点的序号int FirstAdjVex(ALGraph G,char v){int i;ArcNode *p;i=LocateVex(G,v);if(i==-1)return -1;p=G.vertices[i].firstarc;if(p)return p->adjvex;elsereturn -1;}//返回v的(相对于w)的下一个邻接顶点的序号int NextAdjVex(ALGraph G,char v,char w){int i,j;ArcNode *p,*q; i=LocateVex(G,v);j=LocateVex(G,w);if(i==-1||j==-1||i==j)return -1;p=G.vertices[i].firstarc;while(p->nextarc&&p->adjvex!=j)p=p->nextarc;if(p->nextarc){q=p->nextarc;return q->adjvex;}elsereturn -1;}//采用邻接表表示，构造有向图Gint CreateDG(ALGraph &G){int v,e,i,j,t;ArcNode *p,*q;char tail,head;printf("输入顶点个数:");scanf("%d",&v);if(v<0)return ERROR;G.vexnum=v;printf("输入弧的条数:");scanf("%d",&e);if(e<0)return ERROR;G.arcnum=e;printf("建立DG:\n");//建立头结点顺序表for(t=0;t<G.vexnum;t++){fflush(stdin);printf("输入%d的信息:",t+1);scanf("%c",&G.vertices[t].data);G.vertices[t].firstarc=NULL;}//建立表结点链表(每个顶点的邻接顶点链表) for(t=0;t<G.arcnum;t++){fflush(stdin);printf("输入弧的信息(弧尾-弧头)");scanf("%c%*c%c",&tail,&head);i=LocateVex(G,tail);j=LocateVex(G,head);if(i==-1||j==-1||i==j)return ERROR;p=(ArcNode *)malloc(sizeof(ArcNode));p->adjvex=j;p->info=NULL;p->nextarc=NULL;if(!G.vertices[i].firstarc)G.vertices[i].firstarc=p;else{for(q=G.vertices[i].firstarc;q->nextarc;q=q->nextarc);q->nextarc=p;}}}//从第v个顶点出发，递归的深度优先遍历有向图Gint DFS(ALGraph G,int v){int w;visited[v]=-1;printf("%c ",G.vertices[v].data);w=FirstAdjVex(G,G.vertices[v].data);for(;w>=0;w=NextAdjVex(G,G.vertices[v].data,G.vertices[w].data)) if(!visited[w])DFS(G,w);return OK;}//深度优先搜索遍历图Gint DFSTraverse(ALGraph G){int i;for(i=0;i<G.vexnum;i++)visited[i]=0;for(i=0;i<G.vexnum;i++)if(!visited[i])DFS(G,i);return OK;}//广度优先搜索遍历图Gint Visit(char v){printf("%c ",v);return OK;}//从第v个顶点出发，递归的广度优先遍历有向图Gint BFSTraverse(ALGraph G,int(*visit)(char v)) {LinkQueue Q;int v,w,u;for(v=0;v<G.vexnum;v++)visited[v]=0;InitQueue(Q);for(v=0;v<G.vexnum;v++){if(!visited[v]){visited[v]=1;Visit(G.vertices[v].data);}EnQueue(Q,v);while(!EmptyQueue(Q)){DeQueue(Q,u);for(w=FirstAdjVex(G,G.vertices[u].data);w>0;w=NextAdjVex (G,G.vertices[u].data,G.vertices[w].data))if(!visited[w]){visited[w]=1;Visit(G.vertices[w].data);EnQueue(Q,w);}}}return OK;}//主函数void main() {ALGraph G;printf("建立有向图G\n");if(CreateDG(G)){printf("深度优先搜索的顺序:");DFSTraverse(G);printf("\n");printf("广度优先搜索的顺序:");BFSTraverse(G,Visit);}printf("\n");}三、运行结果：。

数据结构图的遍历实验报告篇一：【数据结构】图的存储和遍历实验报告《数据结构B》实验报告系计算机与电子专业级班姓名学号XX年1 0月 9日1. 上机题目：图的存储和遍历2. 详细设计#include#define GRAPHMAX 10#define FALSE 0#define TRUE 1#define error printf#define QueueSize 30typedef struct{char vexs[GRAPHMAX];int edges[GRAPHMAX][GRAPHMAX];int n,e;}MGraph;int visited[10];typedef struct{int front,rear,count;int data[QueueSize];}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))error("Queue overflow");else{ Q->count++;Q->data[Q->rear]=x;Q->rear=(Q->rear+1)%QueueSize;}}int DeQueue(CirQueue *Q){int temp;if(QueueEmpty(Q)){ error("Queue underflow");return NULL;}else{ temp=Q->data[Q->front]; Q->count--; Q->front=(Q->front+1)%QueueSize; return temp;}}void CreateMGraph(MGraph *G){int i,j,k;char ch1,ch2;printf("\n\t\t请输入定点数，边数并按回车（格式如：3，4）：");scanf("%d,%d",&(G->n),&(G->e));for(i=0;in;i++){ getchar();printf("\n\t\t请输入第%d个定点数并按回车：",i+1);scanf("%c",&(G->vexs[i]));}for(i=0;in;i++)for(j=0;jn;j++)G->edges[i][j]=0;for(k=0;ke;k++){ getchar();printf("\n\t\t请输入第%d条边的顶点序号（格式如：i,j）：",k+1);scanf("%c,%c",&ch1,&ch2);for(i=0;ch1!=G->vexs[i];i++);for(j=0;ch2!=G->vexs[j];j++);G->edges[i][j]=1;}}void DFSM(MGraph *G,int i){int j;printf("\n\t\t深度优先遍历序列： %c\n",G->vexs[i]);visited[i]=TRUE;for(j=0;jn;j++)if(G->edges[i][j]==1 && visited[j]!=1) ////////////////DFSM(G,j);}void BFSM(MGraph *G,int k){ int i,j;CirQueue Q;InitQueue(&Q);printf("\n\t\t广度优先遍历序列：%c\n",G->vexs[k]);visited[k]=TRUE;EnQueue(&Q,k);while(!QueueEmpty(&Q)){ i=DeQueue(&Q);for(j=0;jn;j++)if(G->edges[i][j]==1 && visited[j]!=1) { visited[j]=TRUE;EnQueue(&Q,j);}}}void DFSTraverseM(MGraph *G){int i;for(i=0;in;i++)visited[i]=FALSE;for(i=0;in;i++)if(!visited[i]) DFSM(G,i);}void BFSTraverseM(MGraph *G){int i;for(i=0;in;i++)visited[i]=FALSE;for(i=0;in;i++)if(!visited[i]) BFSM(G,i);}void main(){MGraph *G,a;char ch1;int i,j,ch2;G=&a;printf("\n\t\t建立一个有向图的邻接矩阵表示\n");CreateMGraph(G);printf("\n\t\t已建立一个有向图的邻接矩阵存储\n");for(i=0;in;i++){ printf("\n\t\t");for(j=0;jn;j++)printf("%5d",G->edges[i][j]);}getchar();ch1='y';while(ch1=='y'||ch1=='Y'){ printf("\n");printf("\n\t\t图的存储与遍历 ");printf("\n\t\t********************************");printf("\n\t\t*1-----更新邻接矩阵*");printf("\n\t\t*2-----深度优先遍历*");printf("\n\t\t*3-----广度优先遍历*");printf("\n\t\t*0-----退出*");printf("\n\t\t********************************");}} printf("\n\t\t请选择菜单号（0----3）"); scanf("%d",&ch2); getchar(); switch(ch2) { case 1:CreateMGraph(G); printf("\n\t\t图的邻接矩阵存储建立完成\n");break; case 2:DFSTraverseM(G);break; case 3:BFSTraverseM(G);break; case 0:ch1='n';break; default:printf("\n\t\t输出错误！清重新输入！"); }3. 调试分析（1）调试过程中主要遇到哪些问题？是如何解决的？由于实习之初对邻接表的存储结构了解不是很清楚，所以在运行出了一个小错误，即在输出邻接表时，每个结点都少了一个邻接点。

【关键字】结构中南大学《数据结构》课程设计题目图的保存和遍历学生姓名指导教师学院信息科学与工程专业班级完成时间第一章课程设计目的1.1掌握图的邻接表存贮结构。

1.2掌握队列的基本运算实现。

1.3掌握图的邻接表的算法实现。

1.4掌握图的广度优先搜索周游算法实现。

1.5掌握图的深度优先搜索周游算法实现第二章设计内容和要求对任意给定的图（顶点数和边数自定），建立它的邻接表并输出，然后利用队列的五种基本运算（置空队列、进队、出队、取队头元素、判队空）实现图的广度、深度优先搜索周游。

第三章运行环境Turber c/c++集成实验与学习环境第四章课程设计分析我的设计思路是,先通过给定的顶点和边的信息构造出图，用邻接表保存该图，然后用DFS或BFS进行遍历.下面是我设计过程的结构图:图4.1 设计过程的结构图通过自己对图的保存与遍历的算法了解和实践，进一步加深了图的邻接表保存，其特点有：1.保存表示，不惟一，各边表结点的链接次序取决于建立邻接表的算法和边的输入次序；空间复杂度S(n，e) ，S(n，e)=O(n+e)。

稀疏图用邻接表表示比用邻接矩阵表示节省保存空间；2.求顶点的度，无向图：顶点vi的度则是第i个边表中的结点个数；3.判定(Vi，Vj)或<Vi，Vj>是否是图的一条边；在邻接表表示中，需扫描第i个边表最坏情况下要耗费O(n)时间；4.求边的数目，与e的大小无关只要对每个边表的结点个数计数即可求得e，所耗费的时间，是O(e+n)。

当e≤n2时，采用邻接表表示更节省空间。

至于两种遍历，在计算机科学中，经常会遇到图的遍历问题。

解决这一问题的经典算法就是所谓深度优先搜索和广度优先搜索，理论证明两套算法的性能是等效的。

遍历图的过程实质是通过边或弧找邻接点的过程，因此广度优先搜索遍历图的时间复杂度和深度优先搜索遍历相同，两者不同之处在于对顶点访问的顺序不同而已.第五章算法（数据结构）描述实现图的保存和遍历其思路总体分二个大步骤：1.1图的保存采用邻接表对图进行保存，并输出保存结果，为实现邻接表的建立附设连个指向图相关边的指针*p,*q.再用for(k=1;k<=e;k++)同时*p，*q移动，给每条边分配内存，再利用函数print(g,n)将建立好的邻接表输出。

武汉东湖学院
实验报告
学院：计算机科学学院专业计算机科学与技术2016年11月18日
姓名付磊学号2015040131042
班级计科一班指导老师吴佳芬
课程名称数据结构成
绩
实验名称图的存储结构和遍历
1．实验目的
（1）了解邻接矩阵存储法和邻接表存储法的实现过程。

（2）了解图的深度优先遍历和广度优先遍历的实现过程。

2．实验内容
1. 采用图的邻接矩阵存储方法，实现下图的邻接矩阵存储，并输出该矩阵.
2. 设计一个将第1小题中的邻接矩阵转换为邻接表的算法，并设计一个在屏幕上显示邻接表的算法
3. 实现基于第2小题中邻接表的深度优先遍历算法，并输出遍历序列
4. 实现基于第2小题中邻接表的广度优先遍历算法，并输出遍历序列
3．实验环境
Visual C++ 6.0
4．实验方法和步骤（含设计）
我们通过二维数组中的值来表示图中节点与节点的关系。

通过上图可知，其邻接矩阵示意图为如下：
V0 v1 v2 v3 v4 v5
V0 0 1 0 1 0 1
V1 1 0 1 1 1 0
V2 0 1 0 0 1 0
V3 1 1 0 0 1 1
V4 0 1 1 1 0 0
V5 1 0 0 1 0 0
此时的“1”表示这两个节点有关系，“0”表示这两个节点无关系。

我们通过邻接表来在计算机中存储图时，其邻接表存储图如下：
}。

图的建立与遍历实验报告------------图的建立与遍历姓名:曹庆松班级:1104学号:1111611512实验日期:2012.10.15报告撰写日期:2012.10.16一、实验目的:1、熟悉图的概念、存储结构和遍历方法。

2、以邻接表为存储结构，掌握无向图的基本操作和实现方法。

3、以邻接表为存储结构，掌握无向图的深度优先遍历的算法实现。

二、实验内容:以邻接表为存储结构，编写程序实现。

1、要求通过键盘输入图的顶点，以及每一条边的两个顶点从而建立无向。

为了简化实验，顶点用数字表示。

2、在以上实验的基础上，实现无向图的深度优先遍历算法。

要求以用户给定的顶点为起始点，显示深度优先遍历的次序。

三、程序代码及结果展示:#include "stdafx.h"#include<stdio.h>#include<stdlib.h>#include <malloc.h>#define MAX_VERTER_NUM 20typedef struct ArcNode{ //表节点int adjvex; //邻接点struct ArcNode *nextarc; //指向下一条弧的指针}ArcNode;typedef struct VNode{ //头结点int data; //定点信息ArcNode * firstarc; //指向第一个依附该顶点的弧的指针}VNode,AdjList[MAX_VERTER_NUM];typedef struct{ //图AdjList vertices; //顶int vexnum,arcnum;//图的顶点数和弧数int Kind;// 图的种类标志}ALGraph;// 对图 G 作深度优先遍历int LocateVex(ALGraph * G,int v) //寻找节点V的位置 { int k,n;for(k=0;k<G->vexnum;k++){ if(G->vertices[k].data==v){n=k;break;}}return n;}int n=1;int visited[MAX_VERTER_NUM]; void DFS(ALGraph *G,int v)//递归调用{ArcNode *p;>vertices[v].firstarc; p=G-if(n<G->vexnum+1){printf(" V%d ",G->vertices[v].data);n++;}visited[v]=1;while(p){if(!visited[p->adjvex])DFS(G,p->adjvex);p=p->nextarc;}}void DFSVisited(ALGraph * G)//深度遍历{int v;int n;printf("请输入遍历的起始的顶点:");scanf("%d",&n);n"); printf("递归深度优先遍历点顺序: \DFS(G,n-1);for(v=0;v<G->vexnum;v++)visited[v]=0;for(v=0;v<G->vexnum;v++)if(!visited[v])DFS(G,v);}void Insertadj(ALGraph * G,int i,int j) //插入邻接点的下标 { ArcNode *a1,*a2;a1=(ArcNode *)malloc(sizeof(ArcNode));a1->adjvex=j;a1->nextarc=NULL;if(G->vertices[i].firstarc==NULL){G->vertices[i].firstarc=a1;}else{a2=G->vertices[i].firstarc;while(a2->nextarc){a2=a2->nextarc;}a2->nextarc=a1;}}void Init_ALGraph(ALGraph * G) //初始化图并建图 { int v,v1,v2,i,j,q,p;int m=0;printf("请输入顶点数:");scanf("%d",&G->vexnum);printf("请输入边数:");scanf("%d",&G->arcnum);for(v=0;v<G->vexnum;v++){printf("顶点 V%d:",(v+1));scanf("%d",&(G->vertices[v].data));>vertices[v].firstarc=NULL; G-}for(v=0;v<G->arcnum;v++) {printf("请输入点点: ");scanf("%d%d",&v1,&v2);i=LocateVex(G,v1); //v1的位置j=LocateVex(G,v2); //v2的位置Insertadj(G,i,j);Insertadj(G,j,i);}}int main(int argc,char **argv) {ALGraph G;Init_ALGraph(&G);//初始化图并建图DFSVisited(&G);//深度优先遍历printf("\n");return 0;}四、实验总结:通过本实验，我对图的存储结构、图的遍历等有了比较深的理解与运用，图的遍历和树的遍历很类似，但是却比树的遍历复杂很多。

实验四图的存储、遍历与应用1、实验目的1）熟悉图的邻接矩阵和邻接表的两种常用存储结构2）掌握两种常用存储方式下深度优先遍历（dfs）和广度优先遍历（BFS操作的实现及其应用。

3）进一步掌握递归算法的设计方法。

2、实验内容1）图的两种存储结构实现：（1）邻接矩阵存储：用一个一维数组来存储顶点信息，用一个二维数组存储用于表示顶点间相邻的关系（边）（2）邻接表存储：用一个一维数组来存储顶点信息，用一个链表表示与顶点相连的边。

表示法类似于树的孩子链表表示法。

2）图的遍历（1）对以邻接矩阵为存储结构的图进行DFS和BFS遍历：建立一个图的邻接矩阵表示，输出以某顶点为起始点的DFS和BFS序列。

实现提示：图的DFS遍历可通过递归调用或用栈来实现。

其思想是：只要当前结点未访问过，就访问该结点，沿着其一条分支深入下去，每深入一个未访问过的结点，就访问这个结点，然后从这个结点继续进行DFS遍历。

在这一过程中，若深入时遇到一个已访问过的结点，则查找是否有与这个结点相邻的下一个未访问过的结点。

若有则继续深人，否则将退回到这个结点的前一个结点，再找下一个相邻的本访问过的结点，,,如此进行下去，直到所有的结点都被访问过。

BFS 遍历可利用队列来帮助实现，也可以用栈。

实现方法与二叉树的层次遍历类似。

（2）对以邻接表为存储结构的图进行DFS和BFS遍历：以邻接表为存储结构，实现图的DFS和BFS遍历，输出以某顶点为起始点的DFS和BFS序列。

实现提示：以邻接表为存储结构的图的DFS和BFS算法的实现思想与以邻接矩阵为存储结构的实现是一样的。

只是由于图的存储形式不同。

而具体到取第一个邻接点和下一个邻接点的语句表示上有所差别而已。

（3）测试数据：自己设计测试用的图，给出其邻接矩阵存储表示。

也可以用如下图作为测试数据。

邻按第陰民字的IB试敕播JLk ainJL fcC 虫- 3| |E 审打jC" jj*J*3^J^yLr* ~|~ g4,19 邻播我的隸试數据图3) 图的应用(1)修改图的遍历程序，实现AOV网的拓朴排序。

实验五图的遍历（深/广度）实验内容图的深度优先搜索（DFS）和广度优先搜索（BFS）。

图的最小生成树和最短路径(选作)。

目的与要求掌握DFS和BFS原理，并用DFS和BFS打印图的顶点信息。

掌握图的最小生成树算法和最短路径算法。

程序中用户选择图的有向或无向，除对图作深，广度遍历之外，还对有向图作最短路径，对无向图作最小生成树。

#include <stdio.h>#include <stdlib.h>#define Infinity 1000#define MAX 20typedef struct{int vexnum; //顶点数目int arcnum; //弧数目char vexs[MAX]; //顶点向量int arcs[MAX][MAX]; //邻接矩阵char kind; //图的种类：有向图D，无向图U}MGraph;//图的建立MGraph Creat_MGraph(){MGraph G;int i,j,k,w;char v1,v2;printf("请输入图的种类（有向图（D）,无向图（U）！\n");scanf("%c",&G.kind);printf("请输入顶点数目和弧数目!\n");scanf("%d%d",&G.vexnum,&G.arcnum);getchar();printf("请输入各个顶点（abc）!\n");for(i=0;i<G.vexnum;i++)scanf("%c",&G.vexs[i]);getchar();for(i=0;i<G.vexnum;i++){for(j=0;j<G.vexnum;j++)G.arcs[i][j]=Infinity;}for(i=0;i<G.arcnum;i++){printf("请输入第(%d) 条弧的起始点和它的权重（ccd）!\n",i+1);scanf("%c%c%d",&v1,&v2,&w);getchar();j=k=0;while(G.vexs[j]!=v1) j++; //起点while(G.vexs[k]!=v2) k++; //终点G.arcs[j][k]=w;if(G.kind=='U')G.arcs[k][j]=w;}return G;}int visited[MAX]; //标志数组，显示是否遍历//递归深度遍历调用函数void DFS(MGraph G,int i){int j;visited[i]=1;printf(" %c ",G.vexs[i]);for(j=0;j<G.vexnum;j++)if(!visited[j]&&G.arcs[i][j]<Infinity)DFS(G,j);}//深度遍历函数void M_DFSTraverse(MGraph G){int i;printf("深度遍历图结果如下：\n");for(i=0;i<G.vexnum;i++)visited[i]=0;for(i=0;i<G.vexnum;i++)if(!visited[i])DFS(G,i);printf("\n");}//广度遍历函数void M_BFSTraverse(MGraph G){int i,j,k,Q[MAX],w;j=k=0;printf("广度遍历图结果如下：\n");for(i=0;i<G.vexnum;i++)visited[i]=0;for(i=0;i<G.vexnum;i++)if(!visited[i]){visited[i]=1;printf(" %c ",G.vexs[i]);Q[k++]=i;while(j!=k){j++;for(w=0;w<G.vexnum;w++)if(!visited[w] && G.arcs[j][w]<Infinity){visited[w]=1;printf(" %c ",G.vexs[w]);Q[k++]=w;}}}printf("\n");}//最小生成树函数，对无向图适用void MiniSpanTree_PRIM(MGraph G,char u){char adjvex[MAX];int lowcost[MAX];int i,j,k=0,min;printf("图的最小生成树为：\n");while(G.vexs[k]!=u) k++;for(i=0;i<G.vexnum;i++)if(i!=k){adjvex[i]=u;lowcost[i]=G.arcs[k][i];}lowcost[k]=0;for(i=0;i<G.vexnum-1;i++){min=Infinity;for(j=0;j<G.arcnum;j++)if(lowcost[j] && lowcost[j]<min){min=lowcost[j];k=j;}printf("%c--(%d)--%c\n",adjvex[k],lowcost[k],G.vexs[k]);lowcost[k]=0;for(j=0;j<G.vexnum;j++)if(G.arcs[k][j]<lowcost[j]){adjvex[j]=G.vexs[k];lowcost[j]=G.arcs[k][j];}}}//求最短路径的函数，对有向图适用void ShortestPath_DIJ(MGraph G,char u){int P[MAX][MAX], //二维数组，标志最短路径上的点D[MAX], //记录最短路径的长度final[MAX], //标志是否求的它的最短路径i,j,v,w,v0,min;v0=0;while(G.vexs[v0]!=u) v0++;for(v=0;v<G.vexnum;++v){ //初始化D[v]=G.arcs[v0][v];final[v]=0;for(w=0;w<G.vexnum;w++)P[v][w]=0;if(D[v]<Infinity){P[v][v0]=1; P[v][v]=1;}}D[v0]=0;final[v0]=1;for(i=1;i<G.vexnum;i++){ //循环求出各个最短路径min=Infinity;for(w=0;w<G.vexnum;++w)if(!final[w])if(D[w]<min){v=w; min=D[w];}final[v]=1;for(w=0;w<G.vexnum;w++)if(!final[w] && (min+G.arcs[v][w]<D[w])){ //修改最短路径D[w]=min+G.arcs[v][w];for(j=0;j<G.vexnum;j++)P[w][j]=P[v][j];P[w][w]=1;}}printf("从已知点到其他各点的最短路径为：\n");for(v=0;v<G.vexnum;v++)if(final[v]){printf("%c--%c 的最短路径长度为%d ，路径为：",u,G.vexs[v],D[v]);for(w=0;w<G.vexnum;w++)if(P[v][w])printf(" %c ",G.vexs[w]);printf("\n");}}void main(){MGraph G;G=Creat_MGraph();M_DFSTraverse(G);M_BFSTraverse(G);if(G.kind=='U')MiniSpanTree_PRIM(G,'a'); //无向图就求它的最小生成树elseShortestPath_DIJ(G,'a'); //有向图就求它的最短路径}程序运行如下：（有向图）请输入图的种类（有向图（D）,无向图（U）！D请输入顶点数目和弧数目!44请输入各个顶点（abc）!abcd请输入第(1) 条弧的起始点和它的权重（ccd）!ab4请输入第(2) 条弧的起始点和它的权重（ccd）!bc6请输入第(3) 条弧的起始点和它的权重（ccd）!cd5请输入第(4) 条弧的起始点和它的权重（ccd）!da8深度遍历图结果如下：a b c d广度遍历图结果如下：a c d b从已知点到其他各点的最短路径为：a--a 的最短路径长度为0 ，路径为：a--b 的最短路径长度为4 ，路径为： a ba--c 的最短路径长度为10 ，路径为： a b ca--d 的最短路径长度为15 ，路径为： a b c d Press any key to continue（无向图）请输入图的种类（有向图（D）,无向图（U）！U请输入顶点数目和弧数目!44请输入各个顶点（abc）!abcd请输入第(1) 条弧的起始点和它的权重（ccd）!ab4请输入第(2) 条弧的起始点和它的权重（ccd）!bc6请输入第(3) 条弧的起始点和它的权重（ccd）!cd5请输入第(4) 条弧的起始点和它的权重（ccd）!da8深度遍历图结果如下：a b c d广度遍历图结果如下：a cb d图的最小生成树为：a--(4)--bb--(6)--cc--(5)--dPress any key to continue。

实验五：图的操作及应用实验学时：4实验类型：综合型一、实验目的1.理解图的逻辑结构和物理结构；2.掌握图的邻接矩阵和邻接表存储表示的实现方法;3.掌握图的深度优先和广度优先遍历算法的实现;4.掌握拓扑排序算法的实现方法。

二、实验条件Visual C++ 6.0三、实验原理及相关知识1.图的邻接矩阵和邻接表存储结构的描述；2.图的邻接矩阵和邻接表存储表示的算法；3.图的深度优先和广度优先遍历算法；4.拓扑排序算法。

四、实验步骤1. 实现图的邻接矩阵的存储表示。

2. 实现图的邻接表存储表示。

3. 实现图的深度优先和广度优先遍历算法。

4. 实现拓扑排序算法。

5. 调用以上函数实现以下操作：(1) 建立图。

(2) 输出基于邻接表存储的深度优先和广度优先遍历序列。

(3) 输出有向图的拓扑排序序列。

参考代码：要求：补充完整以下代码使其能够运行通过。

#include "stdio.h"#include "malloc.h"#include "string.h"#define INFINITY 10000// 用整型最大值代替∞#define MAX_VERTEX_NUM 20 // 最大顶点个数#define OK 1#define ERROR 0#define FALSE 0#define TRUE 1#define MAXQSIZE100typedef int QElemType;typedef float VRType;typedef float InfoType;typedef char VertexType;typedef char VexType;//============邻接矩阵的定义============typedef struct {VRType adj;InfoType info; // 该弧相关信息的指针(可无)}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedef struct {VertexType vexs[MAX_VERTEX_NUM][100]; // 顶点向量AdjMatrix arcs; // 邻接矩阵int vexnum,arcnum; // 图的当前顶点数和弧数} MGraph ;//=======================邻接矩阵的定义========//=================================邻接表的定义========= typedef struct ArcNode{ // 表结点int adjvex; // 该弧所指向的顶点的位置struct ArcNode *nextarc; // 指向下一条弧的指针float info; // 网的权值指针} ArcNode;typedef struct{ // 头结点VertexType data[100]; // 顶点信息ArcNode *firstarc; // 第一个表结点的地址} VNode, AdjList[MAX_VERTEX_NUM];typedef struct {AdjList vertices;int vexnum,arcnum; // 图的当前顶点数和弧数}ALGraph;int visited[MAX_VERTEX_NUM];//=================邻接表的定义=========================//=========队列定义和基本操作=============== typedef struct QNode1{QElemType data;struct QNode1 *next;}QNode, *QueuePtr;typedef struct { //链队列的定义QElemType *base;int front;int rear;} SqQueue;typedef struct{QueuePtr front;QueuePtr rear;}LinkQueue;LinkQueue InitQueue(LinkQueue Q){Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));if(!Q.front)exit(1);Q.front->next=NULL;return Q;}int EnQueue(LinkQueue* Q, QElemType e){QueuePtr p;if( !(p=(QueuePtr)malloc(sizeof(QNode))) )return ERROR;p->data = e;p->next = NULL;Q->rear->next = p;Q->rear = p;return OK;}int DeQueue(LinkQueue *Q, QElemType *e) {QueuePtr p;if( Q->front == Q->rear )return ERROR;p = Q->front->next;*e = p->data;Q->front->next = p->next;if(Q->rear == p) Q->rear = Q->front;free(p);return OK;}int QueueEmpty(LinkQueue *Q) {if(Q->front ==Q->rear) return 1;else return 0;}int DestroyQueue( LinkQueue *Q ){while(Q->front) {Q->rear=Q->front->next;free(Q->front);Q->front=Q->rear;}return OK;}//===================队列定义和基本操作===============int LocateVex(MGraph G,char *vert){ int i;for(i=0; i<G.vexnum; i++)if(strcmp(G.vexs[i],vert)==0)return i;return -1;}int LocateVex1(ALGraph G,char *vert){ int i;for(i=0; i<G.vexnum; i++)if(strcmp(G.vertices[i].data,vert)==0)return i;return -1;}MGraph CreateGraph_UDN( MGraph G ){//建立无向网G的邻接矩阵int i, j,k;float w;VexType v1[100], v2[100];printf("输入顶点数,数边数：");scanf("%d %d", &G.vexnum, &G.arcnum);for(i=0; i<G.vexnum; i++) // 读入所有的顶点{ printf("输入第%d个顶点的信息：",i+1);scanf("%s", &G.vexs[i]);}for(i=0; i <G.vexnum; i++) //初始化邻接矩阵for(j=0; j<G.vexnum; j++)G.arcs[i][j].adj=INFINITY;for(k=0; k<G.arcnum; k++) { // 输入所有的边printf("输入第%d条边依附的两个顶点和边上的权值:",k+1);scanf("%s %s %f", &v1, &v2, &w);// 查询两个顶点在图中存储的位置i = LocateVex(G, v1);j = LocateVex(G, v2);if (i==-1 || j==-1){printf("输入的边不正确\n"); return;}G.arcs[i][j].adj = w;G.arcs[j][i].adj = G.arcs[i][j].adj;}return G;}ALGraph CreateALGraph_UDN(ALGraph G )//建立无向网G的邻接表{int i,j,k;float w;ArcNode * p;VexType v1[100], v2[100];printf("输入顶点数,数边数：");scanf("%d %d",&(G.vexnum),&(G.arcnum)); /* 读入顶点数和边数*/for(i=0;i<G.vexnum;i++) /* 建立有n个顶点的顶点表*/{printf("输入第%d个顶点的信息：",i+1);scanf("%s",&(G.vertices[i].data)) ; /* 读入顶点信息*/G.vertices[i].firstarc=NULL; /* 顶点的边表头指针设为空*/}for(k=0;k<G.arcnum;k++ ) /* 建立边表*/{printf("输入一条边依附的两个顶点和边上的权值:");scanf("%s %s %f",&v1,&v2,&w) ; /* 读入边<Vi，Vj>的顶点对应序号*/i = LocateVex1(G, v1);j = LocateVex1(G, v2);if (i==-1 || j==-1){printf("输入的边不正确\n"); return;}p=(ArcNode*)malloc(sizeof(ArcNode) ); /* 生成新边表结点p */p->adjvex=j; /* 邻接点序号为j */p->info =w;p->nextarc=G.vertices[i].firstarc; /* 将新边表结点p插入到顶点Vi的链表头部*/G.vertices[i].firstarc=p;p=(ArcNode*)malloc(sizeof(ArcNode) ); /* 生成新边表结点p */p->adjvex=i; /* 邻接点序号为i */p->info =w;p->nextarc=G.vertices[j].firstarc; /* 将新边表结点p插入到顶点Vj的链表头部*/G.vertices[j].firstarc=p;}return G;} /*CreateALGraph*/VisitFunc(char *ch)//输出顶点的信息{printf("%s ",ch);}void DFS(ALGraph G, int v ) {int j;ArcNode *p;VisitFunc(G.vertices[v].data); // 访问第v个顶点visited[v]=TRUE; // 设置访问标志为TRUE(已访问)for(p=G.vertices[v].firstarc; p;p=p->nextarc){j=p->adjvex;if( !visited[j] ) DFS(G, j);}}void DFSTraverse( ALGraph G){//图的深度优先遍历算法int v;for(v=0; v<G.vexnum; v++)visited[v]=FALSE; // 访问标志数组初始化(未被访问) for(v=0;v<G.vexnum;v++)if(!visited[v])DFS(G,v); // 对尚未访问的顶点调用DFS }void BFSTraverse(ALGraph G) //图的广度优先遍历算法{int v,j,u ;ArcNode *p;LinkQueue Q;Q=InitQueue(Q); // 置空的辅助队列Qfor(v=0; v<G.vexnum; v++)visited[v]=FALSE; // 置初值for(v=0; v<G.vexnum; v++)if(!visited[v]){visited[v]=TRUE; // 设置访问标志为TRUE(已访问)VisitFunc(G.vertices[v].data);EnQueue( &Q, v ); // v入队列while(!QueueEmpty(&Q)){DeQueue(&Q,&u); // 队头元素出队并置为ufor(p=G.vertices[u].firstarc; p;p=p->nextarc){j=p->adjvex;if( !visited[j] ){visited[j]=TRUE;VisitFunc(G.vertices[j].data);EnQueue(&Q, j);}}}}DestroyQueue( &Q );}//实现建立有向网的邻接矩阵和邻接表的函数MGraph CreateGraph_DN( MGraph G ){//建立有向网G的邻接矩阵{}ALGraph CreateALGraph_DN(ALGraph G )//建立有向网G的邻接表{}Print_MGraph(MGraph G)//输出图的邻接矩阵表示{int i,j;for(i=0;i<G.vexnum;i++){ for(j=0;j<G.vexnum;j++)printf("%f ",G.arcs[i][j].adj ); /*邻接矩阵*/printf("\n");}}Print_ALGraph(ALGraph G) //输出图的邻接表表示{int i,j;ArcNode *p;for(i=0;i<G.vexnum;i++){printf("%s",G.vertices[i].data ); /* 顶点信息*/p=G.vertices[i].firstarc ;while(p!=NULL) /* 表节点信息*/{printf("->%s",G.vertices[p->adjvex ].data);p=p->nextarc ;} /* 顶点的边表头指针设为空*/printf("\n");}}void FindInDegree(ALGraph G, int *indegree){int i,k;ArcNode *p;for (i=0; i<G.vexnum; ++i){for (p=G.vertices[i].firstarc; p; p=p->nextarc) {{k = p->adjvex;indegree[k]++; }}}}//===================拓扑排序==============================int TopologicalSort(ALGraph G) {// 有向图G采用邻接表存储结构。