实验五 图的基本操作
一、实验目的
1、使学生可以巩固所学的有关图的基本知识。
2、熟练掌握图的存储结构。
3、熟练掌握图的两种遍历算法。
二、实验内容
[问题描述]
对给定图,实现图的深度优先遍历和广度优先遍历。
[基本要求]
以邻接表为存储结构,实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点,分别输出每种遍历下的结点访问序列。
【测试数据】
由学生依据软件工程的测试技术自己确定。
三、实验前的准备工作
1、掌握图的相关概念。
2、掌握图的逻辑结构和存储结构。
3、掌握图的两种遍历算法的实现。
四、实验报告要求
1、实验报告要按照实验报告格式规范书写。
2、实验上要写出多批测试数据的运行结果。
3、结合运行结果,对程序进行分析。
编程思路:
深度优先算法:计算机程序的一种编制原理,就是在一个问题出现多种可以实现的方法和技术的时候,应该优先选择哪个更合适的,也是一种普遍的逻辑思想,此种思想在运算的过程中,用到计算机程序的一种递归的思想。
度优先搜索算法:又称广度优先搜索,是最简便的图的搜索算法之一,这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim 最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS,属于一种盲目搜寻法,目的是系统地展开并检查图中的所有节点,以找寻结果。换句话 说,它并不考虑结果的可能位址,彻底地搜索整张图,直到找到结果为止。
以临接链表作为存储结构,结合其存储特点和上面两种算法思想,给出两种遍历步骤:
(1)既然图中没有确定的开始顶点,那么可从图中任一顶点出发,不妨按编号的顺序,先从编号小的顶点开始。
(2)要遍历到图中所有顶点,只需多次调用 从某一顶点出发遍历图的算法。所以,下面只考虑从某一顶点出发遍历图的问题。
…… …… 余下全文