20172307 2018-2019-1 《程序设计与数据结构》第9周学习总结
教材学习内容总结
- 无向图是一种边为无序结点对的图。
- 如果图中的两个顶点之间有一条连通边，则称这两个顶点是领接的。
- 如果无向图拥有最大数目的连通顶点的边，则认为这个无向图是完全的。
- 路径是图中的一系列边，每条边连通两个顶点。
- 环路是一种首顶点和末顶点相同的且没有重边的路径。
- 无向树是一种连通的无环无向图，其中一个元素被指定为树根。
- 有向图有时也称为双向图，它是一种边为有序顶点对的图。
- 有向图中的路径是图中连通两个顶点的有向序列。
教材学习中问题和解决过程
问题1：对图的深度遍历和广度遍历的区别不太理解。
- 问题1解决方案：
深度优先搜索（Depth_Fisrst Search）遍历类似于树的先根遍历，是树的先根遍历的推广。
假设初始状态是图中所有顶点未曾被访问，则深度优先搜索可从图中某个顶点发v 出发，访问此顶点，然后依次从v 的未被访问的邻接点出发深度优先遍历图，直至图中所有和v 有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。
以如下图的无向图G5为例，进行图的深度优先搜索：
搜索过程：
假设从顶点v1 出发进行搜索，在访问了顶点v1 之后，选择邻接点v2。因为v2 未曾访问，则从v2 出发进行搜索。依次类推，接着从v4 、v8 、v5 出发进行搜索。在访问了v5 之后，由于v5 的邻接点都已被访问，则搜索回到v8。由于同样的理由，搜索继续回到v4，v2 直至v1，此时由于v1 的另一个邻接点未被访问，则搜索又从v1 到v3，再继续进行下去由此，得到的顶点访问序列为：
显然，这是一个递归的过程。为了在遍历过程中便于区分顶点是否已被访问，需附设访问标志数组visited[0:n-1], ，其初值为FALSE ，一旦某个顶点被访问，则其相应的分量置为TRUE。
+广度优先搜索（Breadth_First Search） 遍历类似于树的按层次遍历的过程。
假设从图中某顶点v 出发，在访问了v 之后依次访问v 的各个未曾访问过和邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。换句话说，广度优先搜索遍历图的过程中以v 为起始点，由近至远，依次访问和v 有路径相通且路径长度为1,2,…的顶点。
对图如下图所示无向图G5 进行广度优先搜索遍历：
广度搜索过程：
首先访问v1 和v1 的邻接点v2 和v3，然后依次访问v2 的邻接点v4 和v5 及v3 的邻接点v6 和v7，最后访问v4 的邻接点v8。由于这些顶点的邻接点均已被访问，并且图中所有顶点都被访问，由些完成了图的遍历。得到的顶点访问序列为：
v1→v2 →v3 →v4→ v5→ v6→ v7 →v8
和深度优先搜索类似，在遍历的过程中也需要一个访问标志数组。并且，为了顺次访问路径长度为2、3、…的顶点，需附设队列以存储已被访问的路径长度为1、2、… 的顶点。
代码调试中的问题和解决过程
- 问题1：
- 问题1解决方案：
代码托管
上周考试错题总结
本周没有错题。
结对及互评
- 本周结对学习情况
- 20172311
- 对课本上的诸多疑问点进行了讨论，同时对代码实现过程中遇到的一些问题也通过讨论得以解决。
- 上周博客互评情况
- 20172311
学习进度条
| 代码行数（新增/累积） | 博客量（新增/累积） | 学习时间（新增/累积） | 重要成长 | |
|---|---|---|---|---|
| 目标 | 5000行 | 30篇 | 400小时 | |
| 第一周 | 0/0 | 1/1 | 6/6 | |
| 第二周 | 612/612 | 1/2 | 18/24 | |
| 第三周 | 516/1128 | 1/3 | 16/40 | |
| 第四周 | 702/1830 | 2/5 | 16/56 | |
| 第五周 | 1926/3756 | 1/6 | 18/74 | |
| 第六周 | 948/4304 | 1/7 | 18/92 | |
| 第七周 | 771/5075 | 1/8 | 20/112 | |
| 第八周 | 1204/6279 | 1/9 | 20/132 | |
| 第九周 | 3772/10051 | 1/10 | 20/152 |
参考资料
- 图的深度遍历和广度遍历
《Java程序设计与数据结构教程（第二版）》
《Java程序设计与数据结构教程（第二版）》学习指导