11带BFS和DFS的图的实现.doc

图以及DFS和BFS的实现 前提，目标和结果 前提: 完成本次作业，学生需要掌握如下知识 图的存储- 有关图的存储的数据结构 图的便利-有关深度优先搜索和广度优先搜索的知识 目标： 本次作业在于寻猎学生对于计算机中图的存储结构的理解。以及两种基本的便利方法的深度优先搜索(DFS)和广度优先搜索(BFS)的理解。 结果: 学生独立完成本次作业应该有如下收获 理解图的存储结构 理解图的遍历，以及这些算法的实现 背景 基本上有两种不同的存储图的方法，邻接矩阵和邻接表。对这两种数据结构不熟悉的学生可以参考老师的课件，这里不再提供更多的资料。 关于BFS和DFS的一个可能的实现如下所示。 BREADTH FIRST SEARCH (G, S) Input: 一个图G和一个节点S Output: 在一个连通子图边被标记为发现过的和边缘的两种 Create a Queue Q. ENQUEUE (Q, S) // 将S插入到Q中 While Q is not empty do for each vertex v in Q do for all edges e incident on v do if edge e is unexplored then let w be the other endpoint of e. if vertex w is unexpected then - mark e as a discovery edge - insert w into Q else mark e as a cross edge DEPTH FIRST SEARCH (G, v) Input: 一个图G和一个节点v Output:在一个连通子图中边被标记为发现的和边缘边(back edge)两种 For all edges e incident on v do If edge e is unexplored then w ← opposite (v, e) // 返回和v在同一条边e上的两一个节点 If vertex w is unexplained then - mark e as a discovery edge - Recursively call DSF (G, w) else - mark e as a back edge 任务 本次作业和接下来的作业密切相关，所以你的程序应该被争取的实现，以备接下来的作业使用。你可以任何一种你喜欢的数据结构去实现一个图，然后根据你选择的数据结构去实现BFS和DFS两个算法。 你的程序应该完成对Fig 1的测试，其中s是开始节点。 Fig 1. A simple graph