图的基本概念：

对书上内容的一些补充：

子图简单来说就是一个充分非必要条件，子图顶点和边必然是图的子集合，反之不然

数据结构里面只讨论简单图，所以不会出特别古怪的题目

同样，最少的有环图也同样不会考虑，只会考一定有环的边数

极大连通子图就是其连通分量，极大强连通子图就是其强连通分量

如果其自身就是连通或者强连通图，那么其自身就是极大连通子图、极大强连通子图

后面也有对有向图进行连通性的讨论（有向图的连通意味着是可达但非双向可达

生成树一般都是对无向图讨论的，生成森林也是一样

极小连通子图并没有对顶点个数的要求，而极大连通子图包含了对顶点个数的要求

要点摘录，根据这些点去复习：

1.无向图：

连通最大边数、最小边数；不连通最大边数、最小边数；一定连通的边数

一定不连通的边数、一定有环的边数

2.有向图：

强连通最大边数、最小边数；不强连通最大边数、最小边数一定强连通的边数

一定不强连通的边数、一定有环的边数

习题补充：

3：每次深搜、广搜都是对图从该顶点向外拓展的可达的分量进行遍历的过程

4：图和树的区别在于定义，一个是一对多，一个是多对多

15：思想就是每次向里面加一条边就可以连接两个分量变为一个，总体分量数量减一

其实就是后面的最小生成树的思路，如果实在没思路都是可以举例破题的

关于统考题：

当时出这种题的时候王道里面大概率是没有这类知识点的，那么怎么办？

一眼看不懂或者想不透那么就举例，举例或者穷举是考场上经常需要使用的方法

其他就是改变下不等式的方向或者说样子，可能换个样子就比较容易理解了

关于顶点的度问题，这个比较简单也不太需要多说

PS：依旧是审题，需要注意下选择题里面说的到底是什么类型的图…

图的存储和基本操作：（以存储为主，因为不怎么考代码题所以基本操作了解即可

书上内容补充：

图的存储更多应该会结合具体的应用背景考察应用方式，单独考察的概率并不高

所以重心要放在这几个存储方式的操作实现上各自的区别、应用场景、优缺点这一些

唯一考察的算法题居然是邻接矩阵的遍历，只能说是过分简单了

矩阵压缩可以注意这样一点：对角线不需要存储，所以如果考察下标计算需要注意

除了邻接矩阵以外的存储方式都是不唯一的

邻接表、邻接多重表、十字链表的顶点表都可以是顺序存储的

图四种存储方式的总结需要依照下述操作自己走一遍，理解才会深刻：

对于四种存储方式：邻接矩阵、邻接表、十字链表、邻接多重表

分别写出对应的操作以及计算其时间复杂度：

求一个顶点的入度、出度，求相邻边及条数，与任意一个顶点的连接是否存在

求一共有多少条边、删除边、删除顶点、建立该数据结构

PS:具体的补充在文档内，由于篇幅较大所以没有写纸上

习题补充：

3：矩阵计算的时候对角元素必然是零，这一点或许可以做考察方向

8：这个结论基本不太可能再考察第二遍，统考里面遇到这种基本只能是没办法的

对于那道统考题最多只能做到矩阵的运算，确实很难联系出实际的含义

15：统考比较喜欢考察的一种方式：某某方式比某某方式更好（一般都是错的

往往都是在某些情况下这种方式好而另外一种情况下那种好，这个是片面的判断

PS：审题上面看清楚是哪种存储方式，哪种图，然后再决定做题

综合题四：

拓扑序列可以将一个图的顶点邻接矩阵排序为上三角矩阵，记住这个结论

同时邻接矩阵若是上三角矩阵，那么也可以说明一定存在拓扑序列，这算是个结论

但也可以基于理解去思索

图的遍历：

书上内容的补充和总结整理：

对于任何图，其访问位的设置是必要的，否则一方面成环图会死循环，一方面效率低

深度优先的遍历必然是类似先序的，肯定是把当前退回之前的全部访问完再向上退回去

关于图的连通性判断：

无向图每次广搜或者深搜的调用都可以遍历一个连通分量，调用次数就是连通分量数

同时也可以用于判断连通性，但对于有向图就复杂得多

一方面是有向图从不同顶点出发，其访问序列和访问次数、生成森林、生成树都会不同

可能从A顶点能一次性访问全部顶点，但从B顶点开始需要全部遍历一遍

对于有向图如果不考虑其逆图的状况只能求得从该点开始的“可达访问序列”

但深搜、广搜也同样可以用于判断有向图的强连通性或者求强连通分量

只需要正向求解一次后再转置该图即可反向验证该图的强连通性或者强连通分量

总之需要记住：

对于有向图而言，其一次访问是完全随机的，和其强连通性完全没什么关系

不管是访问的次数还是访问的序列，甚至是生成森林与否，生成树的顺序都是不确定的

拓展补充：

广度优先采用的是队列，深度优先采用的是递归栈，两者均可用于有向图和无向图

深度优先、广度优先都基于一个原理（这里是说无向图之下）

每次遍历一个连通分量或者说全部的可达点，在确认访问结束后找未访问节点再度遍历

这个图不论是连通的还是不连通的，最终都会被遍历一遍，即使图本身没有边

广度补充：

广度优先遍历的最短路径求解只适用于权值相同的图或者说是无权图

至于带环与否并不重要，因为每次记录的都是最短路径，一旦带环必然会更长一些

负权值这种本身就不是支持范围内了（当然如果权值都一样那么可以转换为权值相同

拓扑排序既可以基于队列也可以基于栈，但对有向无环图而言只有深度优先能判断

因为确实是无所谓的，本身每次只是需要入度、出度为零的被标记后面再度可以用即可

对于无向图而言，不论是广度优先还是深度优先都可以判断到是否具有环

二分图的检测是书上的拓展习题，可以用深搜和广搜实现（具体原理？

一般广搜用得更多的在于树的层序遍历上面，无向连通图当边为N-1时即为一棵树

深度优先补充：

深度优先可以用于判断图内是否存在环，不论是有向图还是无向图都可以判断有环否

在无向图里面因为各自顶点都是连通的，所以只要能够访问到已经访问过的结点就有环

在有向图里面有环其实就是属于其子孙重新找到自身（子孙与否由结束时间判

其实这种东西只需要跟着算法执行一遍就会有很多新的体会和感悟，能够理解很多

深度优先也可以用于判断强连通性、强连通性，具体的操作和广搜是一样的

一般用得较多就是在树的先序遍历或者递归工作栈上，递归工作栈本身就是深度优先的

描述一棵树的话，有两种方式：

无向连通图，具有N-1条边那么就是一棵树

有向图，N-1条边，且存在一个入度为零，其他N-1个结点入度均为1的情况就是一棵树

有环与否，深搜、广搜：

在无向图里面有环，不论深搜还是广搜都是能清楚的，因为肯定会找到已访问顶点

既然访问到已经访问的顶点了，你说是不是一定存在环？

对于无向图里面，广搜无法判定是否有环，因为访问到已访问结点的时候可能没有环

但深搜可以，其如果从其子孙找回了其已访问过的子孙结点那么必然就有环

本质一个是层序遍历，不含前驱和后继逻辑关系，而另外一者是先序，含前驱后继逻辑

更准确而言一者的遍历序列不能完全包含前驱后继逻辑关系，而另外一者必然能够

习题补充：

1：其实更有意义的是思索为什么广度优先不能实现带权图的最短路径计算

以及为什么广搜、深搜能够判断无环图中的环，而不能判断有环图中的环，这才有意义

因为实际考察必然是以这种类型来的，而不会是简单的判断定义

2：基于邻接矩阵的遍历序列是唯一的，基于邻接表的遍历都是不唯一的

但如果给定了一个邻接表，那么遍历序列也自然唯一了，因为先前的不唯一是链序不定

不设置访问位的话，基本是铁定会访问第二次的，因为每个顶点都会进行一次遍历

除非你是一个单独的没有和其他连接边的点，不然不设访问位必然导致两次以上访问

有时候如果有环的话，那么就…死循环

非强连通的有向图依旧可能可以一次即可实现全部调用

所以有时候可能就可以思考下这个有向图最少可以几次调用，最多需要几次调用

4：基于邻接矩阵、邻接表均是一样的，无非时间复杂度上面略微有些差别

基本还是应用场景上面，邻接矩阵适用于稠密图，邻接表适用于稀疏图，这两者的区别

10：这类题目才真正考察了代码的运行模拟，清楚一个思路：

对于每个顶点，其每次的遍历均是一个“可达分量”，这一些都是已经置访问位的

这一个顶点遍历结束后再去别的没有访问过的顶点进行再度的遍历，这个是核心思想

7、8、10、11、16、18：至于深搜、广搜的序列判断

一般只需要清楚广搜是一批批访问，而深搜是先访问到最深然后再逐渐退回就可以

其实容易错在深搜，最后一次的访问退回可能容易被忽略掉

综合题4、5：

第四题其实就是分别对两端调用一次深搜或者广搜即可，如果某次访问完对应被访问

那么就肯定存在这样一条路径，这里只进行判断是否存在，没有要求记录

第五题基于深搜可以实现（思路见草稿

图的应用（重难点）（分三段叙述）（上：

最小生成树：

最小生成树是对于无向图而言的，且也不用考虑权值正负，是求最小带权生成树

图到底有没有环也没有关系，其求的只是一棵最小权值的生成树而已！别什么都求不了

至于为什么后面的表内没有对Prim和Kruskal算法两者的邻接表、邻接矩阵说明：

其实更多原因是这两者不太适合用邻接矩阵或者邻接表存储罢了

Prim而言，将每次每个顶点的遍历数量从顶点数变为了其相连的顶点数

基本对整体算法效率的改善没太大帮助，因为决定查找次数的是顶点的数量而非边数

对Kruskal而言，其边不适合用邻接矩阵存储，而适合用结构体数组用堆存储

否则每次求最小的可行权值边都需要遍历一整个邻接矩阵，这是完全不能接受的

两者算法的思想基本一样：每次选最优解,构造整体最优解

具体的运行过程不太适合用言语阐述，适合用笔、纸去模拟运行

最短路径（中：

先说下一共有这样一些需要考虑的图类型：（这一些排列组合就成了一堆图）

按权值分：带权图（正权，负权、混合）、无权图

按结构分：带环、不带环

按类型分：有向、无向

BFS:

BFS仅适用于无权图（权值默认为一），至于带环或者有向与否没关系

因为如果带环，经过环的路径必然大于不经过环的路径，不可能影响最短路径

有向无向与否没关系，如果能由一个顶点到达另外一个顶点那么一定可以得到最短路径

无非对有向图可能需要调用两次罢了（顶点A到顶点B可以是单向也可以是双向的）

Dijkstra:

对于Dijkstra算法，从其算法过程就能理解为何其不能用于负权图

因为每次其集合内的路径是已经认为最短，不更新的，加入负值可能导致集合路径更短

因而自然就不再满足这个算法的基本判断：集合内的都是最短路径，自然无法求解

带环与否同样不重要，和广搜的思路是一样的，有向与否也同样不重要

因为每次更新的都是可达的顶点，管你到底是有向还是无向？根本不可能产生影响的

Floyd:

至于Floyd，也可以从其算法里面去思索，其是动态规划的思想

每次加入一个新结点，然后考虑能否从这个新结点得到到任何一个其他顶点更短的路径

光从这一点就可以看出来负权也是没关系的，算法会考虑这条更短的路径在内

至于为什么不能有负权环？

如果家到学校是-21km，学校到家是20km，那么家到学校最短路径是多少？

我特么从学校到家，再从家到学校，ok，变成负无穷了，本身就是没有解的一个情况！

不是弗洛伊德不能得到最短路径，是这个问题压根就没有解，多半就能理解些了吧

至于这图到底带环不带环、负权值与否、有向否都是没关系的，不会影响最终解的情况

毕竟无向可以视作是双向连通的有向图，带环肯定更长

利用多次Dijkstra得到每个结点的最短路径：

这个要求其实和Dijkstra是一样的，如果存在负权值那么就没办法得到正确的最短距离

拓扑排序、关键路径：

习题补充：

1：补充一些知识点，最小生成树的唯一性

当顶点数为N-1的无向连通图，即图本身就是一棵最小生成树时那么必然是唯一的

当顶点数大于N-1时，就分为图中各条边权值是否唯一的两种情况

权值若是均不重复的，那么最小生成树就一定是唯一的，而权值若有重复，则就不一定

但当权值有重复但各个环内没有权值重复的边时，那么最小生成树一样唯一

上面列举的情况基本已经覆盖了所有的充分条件，最小生成树并没形式上的必要条件

如果考试的时候出现一些较为例外的情况，最好的办法就是举反例，而不是正向去证明

比较简单的方式是列出一个思维导图看一遍就能清晰理解

2：两种算法得出的最小生成树是否唯一不仅取决于图，而且还取决于算法开始点

3：注意先前的讨论均是基于无向连通图之下的，如果不能保证连通自然没最小生成树

5、6：考察两个算法的执行流程和过程，依旧是一个需要加强的点，不够熟悉

7：虽然严格而言，图也包括了负权图，如果是含负权的图那么答案自然就不再成立

9：求最短路径，虽然可以依靠各类算法典型的可模拟的如Dijkstra模拟，但不太建议

如果考试中没有明确说明需要模拟过程或者指明需要用这个算法，那么最好暴力计算

对于最小生成树、最短路径、关键路径的计算基本都可以直接暴力求解，速度一般很快

对于选择题最好的办法就是直接穷举而不是套公式

10：这种是没办法，必须模拟，按照书上给出的例子模板去做，那个模板是很清晰的

11：有向图中广搜不能判断是否有环，如果正向证明比较难那么就去举反例

关键路径的计算最基本的就是求拓扑序列、逆拓扑序列，有了拓扑即可得到逆拓扑

同时需要注意的就是，关键路径正求即为拓扑，逆求即为逆拓扑，这一点没必要去多虑

提一个比较容易忽略的点，关键路径的代码流程，这个似乎时常会被忘记

个人的思路是每次都需要去搜索入度或者出度为零的点，这样就会导致时间复杂度极高

但实际上算法里面完全没必要这样，因为入度为零的情况只有可能在减的时候出现

所以其优化的结果就是ON+E，这也是某年统考题个人没有思路的原因所在点

13：拓扑序列的唯一性问题，其对应的还有一个存在性问题

如果在考场里面遇到新的一些概念问题，最佳的办法就是去逆向举例，看能否证伪

14：在有向图中，强连通分量、强连通图的判断均可以基于拓扑序列进行判断

如果存在顶点数大于一的强连通分量，那么这个图必然是无法拓扑排序的

同样也可以得到一个逆向结论：

如果一个有向图可以拓扑排序，那么其强连通分量数必然就是其顶点数

或者可以说：这个图里面的强连通分量顶点数必然小于二，即一个顶点一个强连通分量

16：最佳的办法就是全部都遍历写完一遍，太取巧的方法一般不太有

19：能够拓扑排序的有向图必然能够改变顶点转换为上三角的邻接矩阵，反之亦然

21：其实对于图论里面的内容，有一些涉及离散数学，很多都是统考考纲之外的内容

如果真的在统考里面遇到了，基本只有一种方法：举例，穷举举反例去证伪

24、25：关键路径的求法一般比较复杂和费事，如果考试里没有主动要求要写完整过程

那么最佳的办法就是直接穷举出关键路径而不是写一大堆，但最基本的训练还是需要

关键路径的属性在书上有介绍，后面还有一道习题会进行更多的补充，这里暂时不赘述

更多是要清楚关键路径的算法和其含义（能够手工模拟

关键路径本身用栈或者队列都能够实现（或者说拓扑排序用栈和队列都能实现

甚至依靠一个集合也能实现，因为本质只是维护一个入度为零的顶点集，一直读取而已

所以具体的算法实现也是非常多的

30：其实统考遇到这种题，一般也只能绞尽脑汁去穷举证伪，没有更佳思路

31：这边实际上书上讲的并不是足够完善，书上讲的其实漏了这道题的这一类情况

在同时改变多条路径的关键路径上活动速度的情况下，如果改变覆盖到了全部关键路径

那么整体的工程进度就是会提速的，书上是为了严谨性所以没有举这个例子

当时做题的时候其实也会稍微有些困惑，为什么没有修改共有的关键路径也能减少

34：其实现在想起来，有向图的有环和其强连通分量顶点数大于一是一个等价的命题

36：这就是算法不熟悉的原因，以为每次对度的查找均需要遍历整个表，实际不必

只在每次修改的时候顺带统计入度为零的点即可，除了一开始可能会遍历全部的顶点罢

求关键路径算法其实也可以称为是求拓扑序列，书上给出的就是非深搜的另一种方式

37：一般是反看，如果一两眼看不出来，那么就必须需要认真一个个对下去

38：目前看其实没有更好的办法，这类选择题就比较恶心，五分但基本没有简便办法的

42：给出另外一个补充命题：增加任一关键路径任一活动的时长会导致工程总体延长

44：相对来说比较容易考察模拟的是最小生成树和Dijkstra这三个算法，别的不太易考

所以这三者的代码运行就需要比较详细去把握，要清楚整个流程，不能有太多疑惑在

但个人依旧是不够熟练的

45：总体没有特别好的办法，虽然可以基于理解做，但面对的线路一旦多就容易做错

46：最小生成树算法得到的不一定是最短路径，最短路径得到的也不一定是最小生成树

综合：

1：统考里面不会出这种证明题，因为难度实在是太高，正向证明基本是不可能实现

一般如果真的出了，基本直接锁定是可以反向举例证伪的，正向证明都是离散数学内容

不可能考察，碰到比较超纲的数学问题直接考虑反向举例去破掉

2：对上面的补充，即是联系拓扑序列和强连通分量之间的关系

若一个图有向图能有拓扑序列，那么其强连通分量数量等于其顶点数量（没有环，等价

求一个图的强连通分量算法也可以基于拓扑排序，每次都如此去去掉这样一个分量

若去除到无法去除，那么剩下的就是一整个强连通分量，也可以用于统计强连通分量数

3：关键路径的训练只能是多加以训练，基本没有特别好的办法，还是考察的重难点

7：其实也思索过为何是以结束时间来判断子孙关系，而不是访问顺序来判断子孙关系

不过也很容易举出反例，递归返回向上访问就会导致子孙的编号大于其祖先

只有结束时间才能唯一断定子孙关系

8：典型的统考证明题，如果出现了基本锁定是不能的，因为统考没办法出这种题目

9：一个细节：存储图的邻接矩阵存储，不需要存储其对角线的内容

这道题也是统考题，但其没有说明一定需要依靠求关键路径的算法去求解

所以一般，直接穷举出最佳结果即可，没必要单独再去运行一遍

10：其实题目没看懂也没大事情，这里的表其实还是比较容易看懂，并不算难的

这里补充一个细节：计算机网络里面的图代价一般不相同，同路径方向不同代价不同

这道题好在图本身都是无向图并且代价也都是一样的，所以才能结合数据结构考察

关于统考中的一些细节：如果能写详细，一定要写越详细越好，而不要只是概括一个解

无向图也完全可以说出来到底是带权还是不带权、带环还是不带环，也会有分值的

11：MST不唯一，之前的概述就来自于这边

拓扑排序序列的唯一性问题：

拓扑排序的唯一充要条件即为对于一个图而言，其在任意求拓扑路径过程中

其入度为零的点均只有一个，这个条件是从算法开始到结束为止，均满足该条件才充要

同样可以推出其的特例：图入度为零和出度为零的点均只有一个（其拓扑子图也是

充分条件就比较多，各顶点为线性序列就能判定拓扑序列唯一

拓扑序列唯一性并不能判定一个图是否唯一

其实关于拓扑序列考试实际的考察细节并不是能够罗列完的，这些只是常见的考察点

如果统考中出现了新增的一些考点，更多还是要依靠举例去作判断

PS：拓扑排序虽然是基于AOV的，但其实际也应用在了AOE上，这一点要清楚

本节要点：（基本来源于书上和习题，内容较多且比较繁杂，今后复习可进一步拓展

1.最小生成树算法的模拟(Prim、Kruskal)

基于模拟运行的角度去做，课后经典习题对应：5、6，应该是很经典和考察细致的习题

后面多少还是有一些模拟题的（但可以酌情去做、看、模拟

2.最短路径算法的模拟(Dijkstra、BFS、Floyd)

首先看P245的表，全部都能回忆、运行模拟、理解那么再去考虑攻克习题

对应习题：10、44、综合7（核心放在Dijkstra的模拟上，另外两者不可能考察模拟

补充模拟：综合10、综合3

3.拓扑序列的算法模拟（DFS、Kahh)

首先看书上P248的DFS，以及综合7，剩下看P247的代码运行，然后去习题加深体会

36题去思索清楚，P251上面的表里面思索清楚时间复杂度即可，顺便思索逆拓扑序列

4.最小生成树的唯一性问题：

5.拓扑排序的存在性问题、唯一性问题：

6.最短路径的唯一性问题：

7.关键路径以及相应的计算

8.关键路径性质和结论：

9.书上两张表（时间复杂度、算法适用范围）的理解