20182328 2019-2020-1 《数据结构与面向对象程序设计》第十周学习总结

教材学习内容总结

图的概念

• 图由顶点和边组成。
• 邻接的(adjacent)：图中的两个顶点之间有一条连通边。
• 邻居：邻接顶点。
• 自循环（环）：连通一个顶点及其自身的边。
• 路径：由一个顶点到达另一个顶点。
• 路径长度：路径边的条数（顶点数 - 1）。
• 环路：一种首顶点和末顶点相同且没有重边的路径。没有环路则是无环的(acyclic)。
  

图的种类

• 无向图：是一种边为无序结点对的图。
• 完全的：无向图拥有最大数目的连通顶点的边。对于n个顶点的无向图，要是完全的，要有n(n-1)/2条边，假设没有边是自循环的。

• 连通的：无向图中任意两个顶点之间都存在一条路径。
  

• 无向树：一种连通的无环无向图，其中一个元素被指定为树根。

• 有向图：也称双向图，一种边为有序顶点对的图。

• 有向图的路径不是双向的，反方向路径不成立。
  

• 有向树：指定一个元素作为树根。
• 不存在其他顶点到树根的连接。
• 每个非树根元素恰好有一个连接。

• 树根到每个其他顶点都有一条路径。

• 网络：一种每条边都带有权重或代价的图。路径权重是该路径中各条边权重的和。

图的算法

• 遍历
• 广度优先遍历：类似树中的层次遍历。把图的每一邻接的横向依次遍历。
• 深度优先遍历：顾名思义，把图的每一邻接的纵向遍历，类似树的前序遍历。

• 深度优先遍历和广度优先遍历的唯一不同是使用的是栈而不是队列来管理。

• 测试连通性：
  从任意结点开始的广度优先遍历中得到的顶点数等于图中所含顶点数，则是连通的。

• 最小生成树（minimum spanning tree）:边的权值之和小于或等于其他任意一棵生成树的边的权值之和。

• 图的实现策略：用邻接列表或者邻接矩阵等。有向图和无向图是不同的。

教材学习中的问题和解决过程

• 问题1：课本上给了广度优先遍历和深度优先遍历的差异，那么深度优先遍历的步骤具体是怎样的呢？
  

• 问题1解决方案：图的深度优先遍历和广度优先遍历的主要差异是它使用的是栈而不是队列来管理遍历的，所以步骤为从顶点9-->顶点6-->顶点3-->顶点1，到顶点1之后，再从顶点9的相邻顶点开始重新遍历。
• 问题2：有向图和无向图的邻接矩阵有什么区别?

• 问题2解决方案：
  一、对称区别：
  1、无向图的邻接矩阵是对称的。
  2、有向图的邻接矩阵不一定对称。
  二、元素区别：
  1、对于无向图，顶点V1的度是邻接矩阵中第i行（或第i列）的非零元素的个数。
  2、对于有向图，顶点V1的度是邻接矩阵中第i行和第i列的非零元素的个数之和。

代码调试中的问题和解决过程

• 问题1：错误提示类Graph找不到符号
  

• 问题1解决方案：把文件名和类名调成一致即可

上周考试错题总结

• 无错题

结对及互评

评分标准

• 基于评分标准，我给本博客打分：14分。得分情况如下：

1. 正确使用Markdown语法（加1分）：
2. 模板中的要素齐全（加1分）
3. 教材学习中的问题和解决过程, 加2分
4. 代码调试中的问题和解决过程, 加1分
5. 本周有效代码超过300分行的（加2分）
6. 其他加分：加7分
7. 扣分：0分

点评模板：

• 博客中值得学习的或问题：
  • 内容详实且精简
  • 问题充分且已解决
• 代码中值得学习的或问题：
  • 正确且简练
  • 方法多样很值得学习
• 参考示例

点评过的同学博客和代码

• 本周结对学习情况
  • 20182322
  • 结对学习内容
    • 图的基本概念和相关延伸
    • 图的算法

其他（感悟、思考等，可选）

本周虽然只学了一章，但图在数据结构中应用范围是较为广泛的，实现的方法也是多种多样。要想全部理解吸收还是很有难度的，但是努力的敲课本上的代码，再加上从网上搜资料还是能够解决问题的。

学习进度条

尝试一下记录「计划学习时间」和「实际学习时间」，到期末看看能不能改进自己的计划能力。这个工作学习中很重要，也很有用。
耗时估计的公式：Y=X+X/N ，Y=X-X/N，训练次数多了，X、Y就接近了。

参考：软件工程软件的估计为什么这么难，软件工程 估计方法

• 计划学习时间:XX小时

• 实际学习时间:XX小时

• 改进情况：

(有空多看看现代软件工程 课件
软件工程师能力自我评价表)

参考资料

• 《Java程序设计与数据结构教程（第二版）》

• 《Java程序设计与数据结构教程（第二版）》学习指导

• ...