数据结构习题三

数据结构习题三请分别写出从顶点0出发进行深度优先搜索（DFS）和广度优先搜索（BFS）的顶点访问序列（假设顶点编号小的优先访问）。问题分析：图的遍历是图操作的基础，DFS和BFS是两种最基本的遍历方法。DFS如同深度探索，尽可能深地沿着一条路径走，直到无法前进再回溯；BFS则如同逐层扩散，先访问完当前层的所有顶点，再访问下一层。解题思路：*DFS(深度优先搜索)：1.访问起始顶点0，并标记为已访问。2.从0的未访问邻接点中选择编号最小的（1），递归进行DFS。3.访问1，并标记。从1的未访问邻接点中选择编号最小的（3）。4.访问3，并标记。3无未访问邻接点，回溯到1。5.从1的剩余未访问邻接点中选择编号最小的（4）。6.访问4，并标记。从4的未访问邻接点中选择编号最小的（5）。7.访问5，并标记。从5的未访问邻接点中选择编号最小的（2）。8.访问2，并标记。2无未访问邻接点，回溯到5，再回溯到4，再回溯到1，再回溯到0。0的另一个邻接点2已访问。遍历结束。*BFS(广度优先搜索)：1.创建一个队列，将起始顶点0入队，并标记为已访问。2.队首元素0出队，访问0。将0的所有未访问邻接点（1,2）按编号顺序入队，并标记。3.队首元素1出队，访问1。将1的所有未访问邻接点（3,4）按编号顺序入队，并标记。4.队首元素2出队，访问2。2的邻接点0已访问，5未访问，将5入队并标记。5.队首元素3出队，访问3。3的邻接点1已访问，无新节点入队。6.队首元素4出队，访问4。4的邻接点1已访问，5已访问，无新节点入队。7.队首元素5出队，访问5。5的邻接点2和4均已访问。队列为空，遍历结束。参考答案与解析：*DFS访问序列：0,1,3,4,5,2*BFS访问序列：0,1,2,3,4,5上述序列是在“顶点编号小的优先访问”原则下得到的。DFS体现了“一条道走到黑”的特点，而BFS则体现了“逐层铺开”的特点。习题4：单源最短路径题目描述：考虑如下带权有向图，顶点为0,1,2,3,4。各边及其权值如下：0->1:100->4:51->2:11->4:22->3:43->0:73->2:64->1:34->2:94->3:2请使用Dijkstra算法求从顶点0到其他各顶点的最短路径及其长度。问题分析：Dijkstra算法是求解单源最短路径问题的经典算法，适用于边权为非负的图。其基本思想是贪心策略，通过逐步选择当前距离源点最近的未确定节点，并以该节点为中介松弛其邻接节点的距离。解题思路：1.初始化：设置一个距离数组`dist`，`dist[i]`表示从源点0到顶点i的最短距离。初始时，`dist[0]=0`，其余`dist[i]=infinity`。设置一个已访问节点集合`visited`，初始为空。2.选择与松弛：*第一轮：从`visited`外的节点中选择`dist`最小的节点u（初始为0）。将u加入`visited`。对u的每个邻接节点v，如果`dist[v]>dist[u]+weight(u->v)`，则更新`dist[v]`。*u=0，`dist[0]=0`。*邻接节点1：`dist[1]=min(inf,0+10)=10`*邻接节点4：`dist[4]=min(inf,0+5)=5`*`dist`现在为：[0,10,inf,inf,5]*第二轮：选择`visited`外`dist`最小的节点u=4（`dist[4]=5`）。加入`visited`。*邻接节点1：`dist[1]=min(10,5+3)=8`(更新)*邻接节点2：`dist[2]=min(inf,5+9)=14`*邻接节点3：`dist[3]=min(inf,5+2)=7`*`dist`现在为：[0,8,14,7,5]*第三轮：选择`visited`外`dist`最小的节点u=3（`dist[3]=7`）。加入`visited`。*邻接节点0：已在`visited`。*邻接节点2：`dist[2]=min(14,7+6)=13`(更新)*`dist`现在为：[0,8,13,7,5]*第四轮：选择`visited`外`dist`最小的节点u=1（`dist[1]=8`）。加入`visited`。*邻接节点2：`dist[2]=min(13,8+1)=9`(更新)*邻接节点4：已在`visited`。*`dist`现在为：[0,8,9,7,5]*第五轮：仅剩节点2未在`visited`，`dist[2]=9`。加入`visited`。其邻接节点3已在`visited`。3.结束：所有节点均已访问，`dist`数组即为最短距离。通过回溯可以记录具体路径（通常需要一个前驱数组辅助）。参考答案与解析：从顶点0到其他各顶点的最短路径及长度：*0->0：长度0(路径：0)*0->4->1：长度5+3=8*0->4->1->2：长度5+3+1=9*0->4->3：长度5+2=7*0->4：长度5Dijkstra算法通过不断“松弛”操作，逐步逼近并最终得到源点到所有其他顶点的最短路径。算法的关键在于每次选择当前距离最小的节点进行处理，保证了一旦节点被加入`visited`集合，其最短距离就已确定。总结与思考本次习题围绕树与图的核心应用展开。二叉树的构造加深了我们对不同遍历序列内在联系的理解；哈夫曼树的构造则展示了贪心算法在优化问题中的应用。图的两种遍历方式（DFS与BFS）是许多图算法的基础，而Dijkstra算法则为我们提供了求解单源最短路径的有效工具。在解决这些问题的过程中，我们不仅需要掌握算法的基本步骤，更要理解其背后的思想和适用场景。例如，哈夫曼编码为何能保证最优？Dijkstra算法为何要求边权非负？这些问题的思考将有助于我们更深入地理解数据结构的本质。实践是