实验四 图的遍历算法设计与实现
一、实验名称：图的遍历算法设计与实现
二、实验目的：
1.掌握图的深度优先遍历的算法。
2.掌握图的广度优先遍历的算法。
3.实验章节：算法设计与分析 第四章
三、实验内容。实验问题和程序运行结果
第一部分 广度优先遍历算法
1. 分析Graph类，画出Graph类初始化以后的Graph对象的数据结构图。
2. 分析BFS函数，画出流程图。
3. 上述程序 int data[7][7]={{ 1,-1,-1,-1,-1,-1,-1},
{ 6, 3, 2,-1,-1,-1,-1},
{ 0,-1,-1,-1,-1,-1,-1},
{ 2, 0,-1,-1,-1,-1,-1},
{ 6, 5,-1,-1,-1,-1,-1},
{ 1,-1,-1,-1,-1,-1,-1},
{ 5, 3,-1,-1,-1,-1,-1}};
是对课本图4-1的输入，从0开始的广度优先的顺序是：
4. 若上图从节点4开始遍历的话，广度优先的顺序应该是什么。
5. 分析当Graph类对象，在输入以下图1的时候，从0开始的广度优先顺序是什么。自己设计data[][]数据进行输入，并给出该种输入情况下的遍历顺序。
6. 改写程序，输出parent数组值，并根据parent画出图1的广度优先深林。
第二部分 深度优先遍历算法
- 分析DFS程序，给出DFS的流程图：
- 对图4-1的DFS遍历顺序是：
- 当对图1进行DFS遍历的时候，遍历顺序是什么，根据parent值，推断深度优先深林是什么。
- 自己设计一个图，并通过程序计算深度遍历和广度遍历顺序。
四、实验小结和心得：
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
