20172325 2018-2019-2 《Java程序设计》第九周学习总结

时间:2023-03-08 17:32:42

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)。有向图的入度定义为多少边指向该顶点,出度是该顶点出边的个数;
  • 根据边是否有方向,将图可以划分为:无向图和有向图。
  • 无向图:

    20172325 2018-2019-2 《Java程序设计》第九周学习总结
  • 有向图:

    20172325 2018-2019-2 《Java程序设计》第九周学习总结

网络

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

对于网络,我们将用一个三元组来表示每条边,这个三元组中包括起始顶点、终止顶点和权重。对于无向网络来说,起始顶点与终止顶点可以互换。

最小生成树

对于图的操作,还有一个最常用的就是找到最小生成树,最小生成树就是用最少的边连接所有顶点。对于给定的一组顶点,可能有很多种最小生成树,但是最小生成树的边的数量 E 总是比顶点 V 的数量小1,即:

  V = E + 1

这里不用关心边的长度,不是找最短的路径(会在带权图中讲解),而是找最少数量的边,可以基于深度优先搜索和广度优先搜索来实现。

比如基于深度优先搜索,我们记录走过的边,就可以创建一个最小生成树。因为DFS 访问所有顶点,但只访问一次,它绝对不会两次访问同一个顶点,但她看到某条边将到达一个已访问的顶点,它就不会走这条边,它从来不遍历那些不可能的边,因此,DFS 算法走过整个图的路径必定是最小生成树。

图的遍历

图的遍历包括深度优先和广度优先搜索

(关于遍历,参考到其他博客,点击此处查看原文)

深度优先搜索

思路:假设初始状态是图中所有顶点均未被访问,则从某个顶点v出发,首先访问该顶点,然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图,直至图中所有和v有路径相通的顶点都被访问到。 若此时尚有其他顶点未被访问到,则另选一个未被访问的顶点作起始点,重复上述过程,直至图中所有顶点都被访问到为止。显然,深度优先搜索是一个递归的过程。

无向图深度优先搜索图解:

20172325 2018-2019-2 《Java程序设计》第九周学习总结

有向图深度优先搜索图解:

20172325 2018-2019-2 《Java程序设计》第九周学习总结

广度优先搜索

   从图中某顶点v出发,在访问了v之后依次访问v的各个未曾访问过的邻接点,然后分别从这些邻接点出发依次访问它们的邻接点,并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问,直至图中所有已被访问的顶点的邻接点都被访问到。如果此时图中尚有顶点未被访问,则需要另选一个未曾被访问过的顶点作为新的起始点,重复上述过程,直至图中所有顶点都被访问到为止。换句话说,广度优先搜索遍历图的过程是以v为起点,由近至远。

无向图广度优先搜索图解:

20172325 2018-2019-2 《Java程序设计》第九周学习总结

有向图广度优先搜索图解:

20172325 2018-2019-2 《Java程序设计》第九周学习总结

图的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,邻接链表关系表示不如邻接矩阵清晰,数据结构相对复杂,但节省空间。

邻接表由数组+链表组成对于上面的无向图,邻接表表示为(由于有向和无向的差别不是太大,所以只是画出了无向的邻接表表示):

20172325 2018-2019-2 《Java程序设计》第九周学习总结

该图标是为,标号为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

参考资料