第六章学习小结_初识图

存储结构及搜索

第六章开始学习的图，是多对多的新的数据结构。

图本身不难理解，但是基于图有很多存储方式和操作，比较容易混淆。

对于存储方式，主要学习了邻接矩阵和邻接表。邻接矩阵在处理稀疏图的时候导致大量空间浪费，因此局限比较大，但如果是在PTA上解题，邻接矩阵是一个不错的方法，操作简单且容易理解。而邻接表显得更加高级（可能是因为它的结构比较复杂，搞得人比较头晕），由几个结构的嵌套组合而成一个邻接表。邻接矩阵所占空间大小主要由顶点个数决定，即固定顶点数不变的情况下边的增加不影响空间大小；而邻接表不同，它的边额外作为一个结构体，因此边的增加也使存储空间增加。

对于上述两种结构，我以深度优先搜索为例进行实例化。

不过需要注意的是，对于一张图，邻接矩阵是唯一的，但邻接表却不唯一，因为在邻接表中，每个顶点后的边的顺序可以改变。但有些时候，对义图的遍历输出会有特殊的要求，比如PTA的作业题，要求按编号递增的顺序访问邻接点。通常邻接表的顺序是通过输入的顺序构建的，输入不一定是递增顺序，输出也不一定是，这就要求我们对邻接再进行排序的处理或者将输出的数据进行排序，增加额外的工作量。（所以不如用邻接矩阵呢）

最小生成树

生成图的最小生成树自然需要两个算法：普里姆算法和克鲁斯卡尔算法

他们最大的差别是，普里姆算法从顶点入手，不用考虑图所有的边而仅考虑当前顶点的邻边。而克鲁斯卡尔算法则从边入手，着眼于图的所有边。

虽然着重点不同，但两者的基本思想相似，即将图的所有顶点分为两个集合，而最终目的是使两个集合的顶点全都整合到一个集合中。这个思想在之后求图的最短路径中也由运用

目标

关于目标的实现方面，好坏参半吧，首先对于书上的算法在代码方面有一个加强，实例化了深搜，但是后劲不足所以广搜并没有去打一边，希望之后能补上。

有去翻阅stl但是比较匆忙，没有去理解和深究，在之后的学习中也要加强，争取能自发地使用st。