20172325 2018-2019-2 《Java程序设计》第九周学习总结
教材学习内容总结
图的定义
- 图是由顶点集（VertexSet）和边集（EdgeSet）组成，针对图G，顶点集和边集分别记为V(G)和E(G)。依据图的边集是否为有向，可把图分为有向图和无向图，根据图是否有权重，可以分为有权图和无权图。
- 图的基本术语：
1.邻接点----在一个无向图中，若存在一条边（Vi，Vj），则称Vi，Vj为此边的两个端点，并称它们互为邻接点；
2.出/入边 -----在一个有向图张，若存在一条边<Vi，Vj>，则称此边为顶点Vi的出边，顶点Vj的一条入边；
3.度/入度/出度----无向图中的度定义为以该顶点为一个端点的边的数目，记为D(V)。有向图的入度定义为多少边指向该顶点，出度是该顶点出边的个数； - 根据边是否有方向，将图可以划分为：无向图和有向图。
- 无向图：
- 有向图：
网络
网络或称为加权图，是一种每条边都带有权重或代价的图，加权图中的路径权重是该路径中各条边权重的和。
对于网络，我们将用一个三元组来表示每条边，这个三元组中包括起始顶点、终止顶点和权重。对于无向网络来说，起始顶点与终止顶点可以互换。
最小生成树
对于图的操作，还有一个最常用的就是找到最小生成树，最小生成树就是用最少的边连接所有顶点。对于给定的一组顶点，可能有很多种最小生成树，但是最小生成树的边的数量 E 总是比顶点 V 的数量小1，即：
V = E + 1
这里不用关心边的长度，不是找最短的路径（会在带权图中讲解），而是找最少数量的边，可以基于深度优先搜索和广度优先搜索来实现。
比如基于深度优先搜索，我们记录走过的边，就可以创建一个最小生成树。因为DFS 访问所有顶点，但只访问一次，它绝对不会两次访问同一个顶点，但她看到某条边将到达一个已访问的顶点，它就不会走这条边，它从来不遍历那些不可能的边，因此，DFS 算法走过整个图的路径必定是最小生成树。
图的遍历
图的遍历包括深度优先和广度优先搜索
（关于遍历，参考到其他博客，点击此处查看原文）
深度优先搜索
思路：假设初始状态是图中所有顶点均未被访问，则从某个顶点v出发，首先访问该顶点，然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和v有路径相通的顶点都被访问到。 若此时尚有其他顶点未被访问到，则另选一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。显然，深度优先搜索是一个递归的过程。
无向图深度优先搜索图解：
有向图深度优先搜索图解：
广度优先搜索
从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问，直至图中所有已被访问的顶点的邻接点都被访问到。如果此时图中尚有顶点未被访问，则需要另选一个未曾被访问过的顶点作为新的起始点，重复上述过程，直至图中所有顶点都被访问到为止。换句话说，广度优先搜索遍历图的过程是以v为起点，由近至远。
无向图广度优先搜索图解：
有向图广度优先搜索图解：
图的java实现
有两种：二维数组表示（邻接矩阵）；链表表示（邻接表）。
邻接矩阵，是表示图形中顶点之间相邻关系的矩阵，对于n个顶点的图而言，矩阵是的row和col表示的是1....n个点。对于无向图 如果顶点b1和b2是连接的，那么在二维矩阵中matrix[b1,b2]和matrix[b2,b1]位置的值置为1，如果是有向图b1指向b2，那么 matrix[b1,b2]=1,matrix[b2,b1]=0；下面用一个例子表示无向图和有向图的邻接矩阵；
邻接矩阵以矩阵的形式存储图所有顶点间的关系。邻接矩阵具有以下特点：
1，邻接矩阵是正矩阵，即横纵维数相等。
2，矩阵的每一行或一列代表一个顶点，行与列的交点对应这两个顶点的边。
3，矩阵的点代表边的属性，1代表有边，0代表无边，所以矩阵的对角线都是0，因为对角线上对应的横纵轴代表相同的顶点，边没有意义。
4，如果是无向图，那么矩阵是对称矩阵；如果是有向图则不一定。
5，如果是有权图，矩阵点数值可以是权值。
6，邻接矩阵表示图的关系非常清晰，但消耗空间较大。
邻接矩阵与邻接表相比，它会造成空间的一定损失，它需要为每个顶点都分配n个边的空间，其实有很多边都是不存在边，但是邻接表的实现就不一样，它只关心存在的边，不关心不存在的边。
邻接表是以一组链表来表示顶点间关系，有以下特点:
- 1，邻接表示一个有但链表组成的数组
- 2，图中的每一个顶点都有一个链，数组的大小等于图中顶点的个数。
- 3，无向图的链的第一个元素是本顶点，后继分别连接着和这个顶点相连的顶点；有向图的链第一个顶点是本顶点，后继是以本顶点为起点的边的终点。
- 4，如果是有权图，可以在节点元素中设置权值属性
- 5，邻接链表关系表示不如邻接矩阵清晰，数据结构相对复杂，但节省空间。
邻接表由数组+链表组成对于上面的无向图，邻接表表示为（由于有向和无向的差别不是太大，所以只是画出了无向的邻接表表示）：
该图标是为，标号为0的结点的相关联的结点为 1 2 3 4；标号为1的结点的相关联结点为0 4，标号为2的结点相关联的结点为 0 4 5......
教材学习中的问题和解决过程
教材学习有问题先去https://shimo.im/doc/1i1gldfsojIFH8Ip/看看，如果别人没有提出相同问题，可以编辑文档添加，然后把自己提出的问题复制到下面：
问题1：看完教材之后不太明白如何获取某顶点所有相连接的点。
问题1解决方案：顶点类里面 使用了一个私有的内部类实现了一个邻接点的迭代器，
/**Task: 遍历该顶点邻接点的迭代器--为 getNeighborInterator()方法 提供迭代器
* 由于顶点的邻接点以边的形式存储在java.util.List中,因此借助List的迭代器来实现
* 由于顶点的邻接点由Edge类封装起来了--见Edge.java的定义的第一个属性
* 因此，首先获得遍历Edge对象的迭代器,再根据获得的Edge对象解析出邻接点对象
*/
private class NeighborIterator implements Iterator<VertexInterface<T>>{
Iterator<Edge> edgesIterator;
private NeighborIterator() {
edgesIterator = edgeList.iterator();//获得遍历edgesList 的迭代器
}
这个迭代器的作用就是用来遍历当前顶点对象(this)的邻接点的。
你只需要获得这个迭代器，就可以遍历该顶点的邻接点了。
代码调试中的问题和解决过程
- 问题1：如何返回一个节点的所有邻居？
graph.addEdge("A", "D");
graph.addEdge("A", "C");
while(graph.getVertices().get("A").getNeighborInterator().hasNext())
{
System.out.println(graph.getVertices().get("A").getNeighborInterator().next().getLabel());
}
这里我添加了两条边<A,D>,<A,C>,利用迭代器将A的邻居节点的表示服打印出来是发现陷入死循环，一直打印第一个邻居D
- 问题1解决方案：需要在源代码里面添加一个方法获取所有的顶点(当然，不要忘了在它实现的接口中添加方法的声明)：
public Map<T, VertexInterface> getVertices()
{
return vertices;
}
然后就可以这样来访问某个顶点的邻接点了。
①创建图，添加顶点和边。②获取目标顶点。③获得目标顶点的迭代器。④拿着迭代器遍历该顶点的邻接点。
import java.util.Iterator;
import java.util.Map;
public class TestGraphBlog {
public static void main(String[] args) {
GraphInterface<String> graph = new DirectedGraph<>();
//添加顶点
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
graph.addVertex("D");
//添加边
graph.addEdge("A", "D");
graph.addEdge("A", "C");
Map<String, VertexInterface<String>> verttices = graph.getVertices();
VertexInterface<String> vertex_A = verttices.get("A");//获得顶点
Iterator<VertexInterface<String>> it = vertex_A.getNeighborInterator();
while(it.hasNext())
{
String vertex_Label = it.next().getLabel();
System.out.println(vertex_Label);
}
}
}
代码托管
（statistics.sh脚本的运行结果截图）
上周考试错题总结
暂无
结对及互评
- 本周结对学习情况
- 20172306
- 结对学习内容
- 学习了第十五章的内容
- 编译书中代码
- 编写课后的作业
学习进度条
| 代码行数（新增/累积） | 博客量（新增/累积） | 学习时间（新增/累积） | 重要成长 | |
|---|---|---|---|---|
| 目标 | 5000行 | 30篇 | 400小时 | |
| 第一周 | 200/200 | 2/2 | 20/20 | |
| 第二周 | 300/500 | 2/4 | 18/38 | |
| 第三周 | 500/1000 | 3/7 | 22/60 | |
| 第四周 | 300/1300 | 2/9 | 30/90 |