图的建立与遍历实验报告

《图的建立与遍历实验报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、西安邮电大学（计算机学院）数据结构课内实验报告实验名称：图的建立与遍历专业名称：网络工程班级：网络1502学生姓名：李轩学号（8位）：04152044指导教师：王春梅实验日期：2016年12月13日一.实验目的及实验环境1、理解并掌握图的逻辑结构和物理结构——邻接矩阵、邻接表2、掌握图的构造方法3、掌握图的邻接矩阵、邻接表存储方式下基本操作的实现算法4、掌握图的深度优先遍历和广度优先原理5.实验环境：MicrosoftVisualC++6.0二.实验内容以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历以指定的结点为起点，分别输出每种遍历下的结

2、点访问序列：1、输入顶点数、边数、每个顶点的值以及每一条边的信息，构造一个无向图G，并用邻接矩阵存储改图。2、输入顶点数、边数、每个顶点的值以及每一条边的信息，构造一个无向图G，并用邻接表存储该图3、深度优先遍历第一步中构造的图G，输出得到的节点序列4、广度优先遍历第一步中构造的图G，输出得到的节点序列三．方案设计深度优先算法：计算机程序的一种编制原理，就是在一个问题出现多种可以实现的方法和技术的时候，应该优先选择哪个更合适的，也是一种普遍的逻辑思想，此种思想在运算的过程中，用到计算机程序的一种递归的思想。度优先搜索算法：又称广度优先搜索，是最简便的图

3、的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位址，彻底地搜索整张图，直到找到结果为止。以临接链表作为存储结构，结合其存储特点和上面两种算法思想，给出两种遍历步骤：（1）既然图中没有确定的开始顶点，那么可从图中任一顶点出发，不妨按编号的顺序，先从编号小的顶点开始。（2）要遍历到图中所有顶点，只需多次调用从某一顶点出发遍历图的算法。所以，下面

4、只考虑从某一顶点出发遍历图的问题。（3）为了在遍历过程中便于区分顶点是否已经被访问，设置一个访问标志数组visited[n]，n为图中顶点的个数，其初值为0，当被访问过后，其值被置为1。（4）这就是遍历次序的问题，图的遍历通常有深度优先遍历和广度优先遍历两种方式，这两种遍历次序对无向图和有向图都适用。1、深度优先遍历从图中某顶点v出发进行深度优先遍历的基本思想是：（1）访问顶点v；（2）从v的未被访问的邻接点中选取一个顶点w，从w出发进行深度优先遍历；（3）重复上述两步，直至图中所有和v有路径相通的顶点都被访问到。2、广度优先遍历从图中某顶点v出发进行

5、广度优先遍历的基本思想是：（1）访问顶点v；（2）依次访问v的各个未被访问的邻接点v1，v2，……vk；（3）分别从v1，v2，……vk出发依次访问它们未被访问的邻接点，并使“先被访问顶点的邻接点”先于“后被访问顶点的邻接点”被访问，直至图中所有与顶点v有路径的顶点都被访问到。广度优先遍历图是以顶点v为起始点，由近至远，依次访问和v有路径相通而且路径长度为1，2，……的顶点。为了使“先被访问顶点的邻接点”先于“后被访问顶点的邻接点”被访问，需设置队列存储访问的顶点。主要代码：voidDepthFirstSearch(AdjList*adjlist){i

6、nti;int*visited;visited=(int*)malloc(sizeof(int)*adjlist->vexnum);for(i=0;ivexnum;i++)visited[i]=0;printf("深度优先搜索:");for(i=0;ivexnum;i++){if(visited[i]==1)continue;VisitNext(adjlist,i,visited);}printf("");}voidBreadthFirstSearch(AdjList*adjlist){ArcNode

7、*temp=NULL;intnth;VexQueue*vexqueue=NULL;inti;int*visited=NULL;visited=(int*)malloc(sizeof(int)*adjlist->vexnum);for(i=0;ivexnum;i++)visited[i]=0;printf("广度优先搜索:");for(i=0;ivexnum;i++){if(visited[i]==1)continue;vexqueue=CreateQueue();Push(vexqueue,i);whil

8、e(!IsEmpty(vexqueue)){Pop(vexqueue,&nth);if(vis