2018-2019-20172329 《Java软件结构与数据结构》第九周学习总结

教材学习内容总结

《Java软件结构与数据结构》第十五章-图

一、图及无向图

• 1、图的相关概念：
  • （1）一个图（graph）G=（V，E）由顶点（vertex）的集V和边（edge）的集E组成。每一条边就是一幅点对（v，w）。
  • （2）如果点对是有序的，那么图就是有向的。
  • （3）假如点对是无序的，那么图就是无向的。
  • （4）如果图中的两个顶点之间有一条连通边，则称这两个顶点是衔接的。邻接顶点有时也称为邻居。连通一个顶点及其自身的边称为自循环或环。
  • （5）边的条数的计算：对于第一个顶点，需要（n-1）条边将其与其他顶点连通。而对于第2个顶点，只需要（n-2）条边，因为第二个顶点已经和第一个顶点连通了。第三个顶点需要（n-3）条边。继续向下，直到最后一个顶点，这个末顶点不需要额外的边，因为所有其他的顶点都已经和它连通了。1～n的求和是：求和（n+1）n/2。
  • （6）路径：路径是图中的一系列边，每条边连通两个顶点。
  • （7）路径的长度是该路径中边的条数（或者是顶点减去1）
• 2、无向图：
  • （1）如果无向图拥有最大数目的连通顶点的边，则认为这个无向图是完全的。
  • （2）如果无向图中的任意两个顶点之间都存在一条路径，则认为这个无向图是连通的。
  • （3）无向树是一种连通的无环无向图，其中一个元素被指定为树根。

二、有向图

• 1、有向图有时也称为双向图，它是一种边为有序顶点对的图。如下图：
• 2、有向图中的路径是图中连通两个顶点的有向边序列。
  • （1）连通：
    
    
  • （2）没连通：
    
    
• 3、拓扑序：
  • （1）拓扑排序是对有向无圈图的顶点的一种排序，使得存在一条从vi到vj的路径，那么在排序中vi的后面。
• 4、有向图的属性：
  • （1）不存在其他顶点到树根的连接。
  • （2）每个非树根元素恰好有一个连接。
  • （3）树根到每个其他顶点都有一条路径。

三、网络

• 1、网络：或称为加权图，是一种每条边都带有权重或代价的图。
  • 加权图中的路径权重是该路径中各条边权重的和。
  • 对于网络我们将用一个三元组来表示各条边。这三元组包括起始起点、终止顶点和权重。注：对于无向网络来说，起始顶点和终止顶点可以互换。但是在有向图来说，必须包含每个右相连接的三元组。

四、常用的图算法

• 1、遍历

（1）广度优先遍历：

• a、广度优先遍历类似于树的前序遍历；

• b、可以用一个队列和一个无序列表来构造出结果；

• c、步骤：

  • 1、起始顶点进入队列，同时标记该顶点为已访问的。
  • 2、然后开始循环，该循环一直持续到队列为空时停止，在这个循环中，从从队列中取出这个首顶点，并将它添加到列表的末端。
  • 3、接着让所有与当前顶点邻接且尚未被标记为已访问的各个顶点依次进入到队列，同时把他们逐个标记为已访问，然后重复上述循环。
  • 4、对每个已访问的结点都重复这一过程，直到队列为空时结束，这意味着我们无法再找到任何新的顶点。
  • 5、现在的链表即以广度优先遍历器。

• d、遍历实例：从顶点9开始进行广度优先遍历的步骤如下（连接如下图）

  • 1、往队列中添加9，并且把它标记为已访问；

  • 2、从队列中取出9；

  • 3、往链表中添加9；

  • 4、从队列中添加6、7、8，逐个标记为已访问；

  • 5、从队列中取出6；

  • 6、往链表中添加6；

  • 7、往队列中添加3、4，逐个标记为已访问。

  • 8、从队列中取出7，并将它添加到链表中；

  • 9、往队列中添加5，并且把它标记为已访问；

  • 10、从队列中取出8，并将它添加到链表中（这时不再往队列中添加任何新的结点了，因为顶点8再也没有尚未访问过的邻居了）

  • 11、从队列中取出3，并将它添加到链表中；

  • 12、往队列中添加1，并且把它标记为已访问；

  • 13、从队列中取出4，并加它添加到列表中；

  • 14、往队列中添加2，并且把它标记为已访问；

  • 15、从队列中取出5，并将它添加到列表中（由于再没有未访问过的邻居，因此不需再往队列中添加顶点）

  • 16、从队列中取出2，并将它添加到链表中；

  • 17、从队列中取出2，并将它添加到列表中。

  • 这样列表就以广度优先次序存放了从顶点9开始的如下顶点：9、6、7、8、3、4、5、1和2.

• 2、测试连通性
  • （1）定义：如果图中的任意两个顶点之间都存在一条路径，则认为这个图是连通的。
  • （2）该定义对无向图和有向图都是成立的。
  • （3）判定：在一个含n个顶点的图中，当且仅当对每个顶点v，从v开始的广度优先遍历的列表大小都是n，则该图就是连通的。
  • 举例：
    
    如下图：

起始顶点	广度优先遍历
A	A,B,C,D
B	B,A,D,C
C	C,B,A,D
D	D,B,A,C

• 3、最小生成树
• （1）生成树是一颗含有图中所有顶点和部分边（但有可能不是所有边）的树。由于树也是图，因此对于某些树而言，其本身就是一颗生成树，这是该图的唯一生成树包含所有边。
• 如图

起始顶点	广度优先遍历
A	A,B,C
B	B,A,C
C	C,B,A
D	D

• （2）生成树的一个有趣应用是找出加权图的最小生成树。最小生成树，其边的权重其边的权重总和小于或等于同一个图中的其他任何一颗生成树的权重总和。
• （3）算法介绍：Prim算法
  • 1、计算最小生成树的一种方法是使其连续地一步一步长成。在每一步，都要把一个结点当作根并往上加边。
  • 2、在算法的任意时刻，我们都可以看到一组已经添加到树上的顶点，而其余顶点尚未加到这棵树中。此时算法在每一阶段都可以通过选择边（u，v）使得（u，v）的值是所有u在树上但v不在树上的边的值中的最小者而找到一个新的顶点并把它添加到这课树中。
  • 3、如图：

• 4、判断最短路径
• （1）判断图中的最短路径有两种情况：
  • 1、判定起始顶点与目标顶点之间的字面意义上的最短路径，也就是两个顶点之间的最小边树。
  • 2、寻找加权图的最便宜路径。
• （2）第一种：从起始顶点到本顶点的路径长度，以以路径中作为本顶点前驱的那个顶点。接着要修改循环，使得当抵达目标顶点时循环将终止，最短路径的路径长度就是从起始顶点到目标顶点前驱顶点的路径长度再加1:如果要输出这条最短路径上的顶点，只需沿着前趋链回溯即可。
• （3）第三个：新的一个算法：Dijkstra算法，我会在代码问题中详细进行描述。

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

• 问题1：在教材308页中介绍有向图的时候有这样两句话：

有向图有时也称为双向图。

有向图中的路径并不是双向的。

就这两句话，我产生了疑问，为什么有向图不为双向，但叫做双向图，他所谓的双向是一样的吗？

• 问题1解决方案：
  
  （1）因为就有向图本身而言，为的确可以为双向的，我们可以在上述的教材内容总结中在网络一部分可以看到两张这样的图：

在第二张很显然就是一个双向的网络，网络同样也是图的一种，但是我很详细的看了一下有向图中的路径并不是双向的。这句话出现的地方，这句话后买呢还接着一句话：除非我们添加了额外的边连通他们俩，也就是这句话介绍是就假如A指向了B，但是在前提中就没有让B指向A，当我们有指向返回的那条边的时候才可以有双向，所以我觉得书本在这里写的会误导第一次学习有向图的同学。

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

• 问题1：pp15.7的具体以及我思考的整个过程？
• 问题1解决方案：
  
  （1）这一周假如算看完书开始做pp项目以来，引得我三天茶不思饭不想的一道题就是这个pp15.7，既然将它写进这个调试，我觉得需要好好记录一下这一周中三天是如何进行这道题的思考的。
  
  （2）其实这道题想想并不难，它只是要求我们求的最便宜路径的最便宜价格是多少，所以一开始我的第一个问题就是如何去保存这个我们输入的权重。因为一开始真的是没有什么思路，就一直在纸上画，写各种各样的伪代码。
  
  （3）然后就突然有了自己的第一版想法：
• 1、我在看到用邻接矩阵记录是否连通的这个数组有了契机，就觉得这个二维数组是个好东西，就觉得是它了。因为我就在添加边的方法中加了这样一句语句Weight[getIndex((T) vertex1)][getIndex((T) vertex2)]=weight;,用于对于权重添加到一个二位数组中，同时在无向图中是有与它对称的语句Weight[getIndex((T) vertex2)][getIndex((T) vertex1)]=weight;，这样就讲连起来的线给赋予一个权重。
• 2、然后我写了这样的一个表格进行明晰

• 3、然后我就想通过两个或三个循环进行找到T,然后用一个result记录下来，进行重复的找然后找到一条路走到尽头，将结果存进一个数组中，重复过程。我的第一版代码如下

Double[] temp = new Double[100];

        Double result=0.0;

        int a =0;

        int b =0;

        int c=0;

        for (int i =0;i<end+1;i++){

            start=c;

            result=0.0;

            for (int j =b;j<end;j++) {

                result=0.0;

                start=a;

                for(int r=b;r<end;r++){

                    result += Weight[start][r + 1];

                    start=r+1;

                    }

                temp[a]=result;

                a++;

                b=b+2;

            }

            a++;

            b++;

        }

//我通过一直讲这个二维数组的位置进行查找在相加再保存

• 4、然后将存进数组的元素找到最小的那个进行输出

          Double min = temp[0];

            for (int r =0;r<end;r++){

                if (temp[r+1]<min&&temp[r+1]>0){

                    min=temp[r+1];

                }

            }

        return min;

• 5、为什么我会毙掉第一版，因为存在着很大的问题，首先，假如我插入的元素够多，我的循环不够多，（我想过用递归实现，但是因为涉及二维数组的横向判断，所以我觉得递归也不行），然后就是因为涉及到横向的判断，举个例子，假如A和B连了，B和C连了，B和D也连了，这个时候我们就多了一路，因为二维数组移动的位置太不可控，所以位置的增加减少就存在很大的问题，所以就陷入了一直想用连续循环的这个弊病中，一时半会儿一直解决不了这个问题，就想着能不能用我们pp15.1需要实现的方式，也就是用链表的方式。

• 6、（1）首先我们先构建这样的一个图：

（2）然后我们需要构建类似链地址法绘制出一个如下图的图：

（3）我的新的一版思路是：当我们在保存头结点的数组中找到开始的结点，然后再需要写循环进行对于是否连接进行判断，在进行将权重相加，但是我依旧又是毙了这一版，因为在偶尔的一天晚上凌晨，翻到了算法导论图论的这一部分，看到了里面讲解的有一部分叫做**单源最短路径**，发现这一部分和这个题目存在着很大的关联，就仔细的看了看，有一个算法就是针对此类题型设计的，叫做Dijkstra算法，我很感谢我当时买了这本书，让我从痛苦中走了出来。
**（4）Dijkstra算法：**
- 1、这个算法被誉为贪婪算法最好的例子。贪婪算法一般分阶段求解一个问题，在每个阶段他都把出现的当做是最好的例子。贪婪算法主要的问题在于，该算法不是总能够成功的。
- 2、举个例子：

• （1）第一个选择的顶点是v1，路径长是为0；该顶点标记为known。既然v1是known的，那么某些表项就需要调整。邻接到v1的顶点是v2和v4。这两个项得到调整。
  
  

• （2）下一步，选取v4并且标记为known。顶点v3,v5,v6,v7是邻接的顶点，而它们实际上都需要调整。如图
  
  

• （3）接下来选择v2，v4是邻接的点，但已经是known的了，因此对它没有工作要做。v5是邻接的点但不做调整，因为经过v2的值2+10=12而长为3的路径已经是已知的。图
  
  

• （4）下一个被选择的顶点是v5，其值为3。v7是唯一的邻接顶点，但是它不用调整，因为3+6>5.然后选取v5，对v6的距离下调到3+5=8。如图：
  
  

• （5）再下一个选取的顶点是v7，v6下调到5+1=6，如图：
  
  

• （6）最后，我们选取的顶点是v6。最后的表在下图中显示，在如下的图形显示算法期间是如何标记为known的以及顶点是如何更新的。
  
  

上周考试错题总结

本周无测试。

结对及互评

• 本周结对学习情况
  • 20172316赵乾宸
• 博客中值得学习的或问题：
  • 内容详略得当；
  • 代码调试环节比较详细；
• 基于评分标准，我给本博客打分：5分。得分情况如下：

1. 正确使用Markdown语法（加1分）：

2. 模板中的要素齐全（加1分）

3. 教材学习中的问题和解决过程, 一个问题加1分

4. 代码调试中的问题和解决过程, 一个问题加1分

   • 20172316唐才铭

• 博客中值得学习的或问题：
  • 内容详略得当；
  • 代码调试环节比较详细；
• 基于评分标准，我给本博客打分：9分。得分情况如下：

1. 正确使用Markdown语法（加1分）：
2. 模板中的要素齐全（加1分）
3. 教材学习中的问题和解决过程, 一个问题加1分
4. 代码调试中的问题和解决过程, 一个问题加1分

感悟

第一次要好好写写感悟了：

• 1、我觉得现在班里写博客呈现出一种我觉得学习java或者学习编程很大的一个弊病，不仅仅是我们学生自己本身，还包括。。。你懂的。我觉得我们学习一门汇编语言应勤于练习，原理是需要了解，但是博客写的如此之多，难道就为了换个加分？？是这样么？现在很多人写博客20小时，敲代码10分钟，难道现在不常见么，码云上，看看，抄抄，多快，很多人自己连脑子都不会动一下，所以我希望不要把有心人的努力慢慢磨的没有了，我觉得我现在为了写一篇博客花了太多的时间去完善我的博客，没有问题，没有教材，我觉得那个只不过是因为很多人已经对于这样的形式趋于疲乏。我们大家的时间都很重要，教材总结，我们看了一遍，还得把教材的自己总结一下，我觉得那不如让我们别敲代码的了，就写博客，分不也很高。
• 2、我自己本身对于分数并不是很在意，只不过只是自己期末的分数高低而已，学没学到真本事谁也不知道，我可以举个例子，我的结对小伙伴赵乾宸本是一个编码能力超强，脑子非常聪明的人，很多人真的不知道他有多强，但是现在这种形式，我觉得博客从纪录分数变成如此的利益化，我觉得本身意义就很弱了，很多人肯定会给我说，那你写这么多干什么，因为我傻。

学习进度条

	代码行数（新增/累积）	博客量（新增/累积）	学习时间（新增/累积）
目标	5000行	30篇	400小时
第一周	0/0	1/1	6/6
第二周	1313/1313	1/2	20/26
第三周	901/2214	1/3	20/46
第四周	3635/5849	2/4	20/66
第五周	1525/7374	1/5	20/86
第六周	1542/8869	2/5	25/111
第七周	1391/10260	1/6	20/131
第八周	4379/14639	2/8	25/156
第九周	3155/17794	1/9	30/186

参考资料

蓝墨云班课

Java程序设计

算法导论：别点了，是本书

数据结构与算法分析：别点了，是本书

Dijkstra 最短路径算法 秒懂详解