20172320 2018-2019-1 《Java程序设计》第八周学习总结
教材学习内容总结
无向图
- 无向图是一种边为无序结点的图。（A,B）意味着A与B之间有一条从两个方向都可以游历的链接
- 图中的两个顶点之间有一条连通边，则称为这两个顶点是邻接的，如上图（1,2）；联通一个顶点及其自身的边称为自循环，如（1,1）
- 如果一个无向图含有最多条边，那么它为完全图。对于有n个顶点的无向图，第x个顶点，需要（n-x）条边将其与其他顶点联通，有n(n-1)/2条边
- 路径是图中的一系列边，路径的长度是该路径中边的条数（或顶点数减1），无向图的路径是双向的。两个顶点之间都存在一条路径，则认为这个无向图是连通的
-
环路是一种首顶点和末顶点相同且没有重边的路径，如上图（1,3,5,1）
有向图
- 有向图是一种边为顶点对的图，（1,2）与（2,1）是不同边
- 有向图中的路径是图中连通两个顶点的有向边序列
- 拓扑序：有向图中没有环路，且有一条从A到B的边，则可以吧顶点A安排在顶点B之前，这种排列得到的顶点次序
-
有向树是一个有向图，其中指定一个元素为根，则具有下列特性：
1、不存在其他顶点到树根的连接。
2、每个非树根元素恰好有一个连接。
3、树根到每个其他顶点都有一条路径。网络
- 网络（加权图）是一种每条边都带有权重或代价的图，网络可以是有向的，也可以是无向的，用三元组来表示网络的每条边，如（Boston,New York,120）
-
对无向网络来说，起始顶点与终止顶点可以互换
常用图算法
- 深度优先遍历：首先从图中某个顶点v0出发，访问此顶点，然后依次从v相邻的顶点出发深度优先遍历，直至图中所有与v路径相通的顶点都被访问了；若此时尚有顶点未被访问，则从中选一个顶点作为起始点，重复上述过程，直到所有的顶点都被访问。在访问某一个顶点时：将它标为已访问，递归的访问它的所有未被标记过的邻接点
- 广度优先遍历：首先，从图的某个顶点v0出发，访问了v0之后，依次访问与v0相邻的未被访问的顶点，然后分别从这些顶点出发，广度优先遍历，直至所有的顶点都被访问完。
- 深度优先遍历使用栈来实现，而广度优先遍历使用队列
- 测试连通性：当且仅当广度优先遍历中的顶点数目等于图中的顶点数目时，图为连通的
- 最小生成树：其边的权重总和小于或等于同一个图中其他任何一棵生成树的权重总和
Prim算法：每次将权值最小的横切边加入生成树中
从顶点0开始，首先将顶点0加入到树中（标记），顶点0和其它点的横切边（这里即为顶点0的邻接边）加入优先队列，将权值最小的横切边出队，加入生成树中。此时相当于也向树中添加了一个顶点2，接着将集合（顶点1，2组成）和另一个集合（除1,2的顶点组成）间的横切边加入到优先队列中，如此这般，直到队列为空。 -
判定最小路径：1、两个顶点之间的最小边数 2、寻找加权图的最便宜路径
图的实现策略
邻接列表：指的是对于图中给定的任意结点，它与其他结点连接的边列表，对于网络，列表中的每项还包含边的权重或代价
邻接矩阵：一种二维数组，其中每个单元都表示图中两个顶点的交接情况。对于无向图，数组中的每个单元是一个布尔值。
无向图由于边不区分方向，所以其邻接矩阵是一个对称矩阵
教材中遇到的问题和解决过程‘
- 问题1：网络定义中的权重和代价是什么？
- 解决方案：权：在实际应用中图的边往往需要表示成为某种数值，这个数值便是该边的权。无向图中加权值，则称为无向带权图。有向图中加权值，则称为有向带权图。
托管代码
上周考试错题总结
无测试
结对及互评
点评过的同学博客和代码
- 本周结对学习情况
20172327 - 结对学习内容
•阅读第15章节，运行教材上的代码
•完成程序设计项目PP15.1、PP15.7
•完成课后自测题，并参考答案学习
学习进度条
| 代码行数（新增/累积） | 博客量（新增/累积） | 学习时间（新增/累积） | 重要成长 | |
|---|---|---|---|---|
| 目标 | 5000行 | 30篇 | 400小时 | |
| 第一周 | 0/0 | 1/4 | 20/20 | |
| 第二周 | 328/328 | 1/5 | 20/40 | |
| 第三周 | 1597/ 1925 | 1/4 | 20/60 | |
| 第四周 | 1153/3850 | 1/5 | 20/80 | |
| 第五周 | 1583/5433 | 1/6 | 20/100 | |
| 第六周 | 1515/6948 | 1/7 | 20/120 | |
| 第七周 | 1145/8093 | 1/8 | 20/140 | |
| 第八周 | 1665/9758 | 1/9 | 20/160 | |
| 第九周 | 1739/11497 | 1/10 | 20/180 |