1.图的定义
2.简单图的定义
3.度的定义
其中度和边的关系有
无向图：因为一条边会共享两个度，所以存在
图的度数=2×边的数量
无向图：一条边会贡献一个入度和一个出度，所以存在
图的入度=图的出度=边
4.顶点与顶点的关系
其中两点强联通指的是顶点与顶点之间存在往返的路径，则称之为强连通
点到点的距离指的是路径上边的数量
常见考点
其中非连通图为什么是c(n-1,2)?
排除一个点，使其不与其他顶点相连
然后在令剩下的顶点两两都有顶点相连即剩余n-1个顶点任取两个相连
也可以是等差数列进行计算，即公差为1以1开始到n-2的等差数列
5.子图和生成子图
取原图中任意边和点即为子图
但注意，一个边不能没有两个顶点相连
但一个子图顶点可以没有边
若一个子图的顶点是包含了原图中的所有顶点，则称之为生成子图
6.连通分量
将一个非连通的无向图G分割成几个联通的子图
对于无向图
所有子图都是联通的
7.强连通分量
将一个非强连通的有向图G分割成及格强连通的子图
对于有向图
每个子图都是强连通的
每一个强连通的子图都被称作强连通分量
如图所示的FG单独作为强连通图诞生
8.生成树
生成树n-1条边
9.生成森林
将原本的图分割成为及格连通子图然后再对每个子图求他们的生成树
10.权值
11.完全图
无向图即为等差数列求和
有向图即为求和后×2，因为有向图有往返
12.特殊的图
13.邻接矩阵
无向图：有联系就是1无就是0（因为是对称矩阵，所以可以压缩存储）
有向图：指向哪个点，哪个点就是1
通过矩阵求度数
存储带权图
邻接矩阵性能分析
邻接矩阵的性质
14.邻接表
顺序+链式存储
空间复杂度分析
因为无向图会有冗余，一条边会重复存储两次
邻接表求度数
有向图的出度很好求
但是入度容易不好求
无向图入度出度都很好求
邻接表的性质
一个图转化为邻接表不唯一
15.十字链表
这一方法有两个结构体如图所示
一个是弧节点，一个是顶点节点
顶点节点被放置于数组中
弧节点被顶点节点指向
其中由图片可以看出，顶点节点由两个指针，一个是弧头指针（即有向图中箭头部分），一个是弧尾指针（有向图中箭头没有尖尖的那部分）
寻找出度：从顶点弧尾指针顺着向下查找，个数就是出度
寻找入度：从顶点的弧头指针向下寻找，个数就是入度
16.邻接多重表
注意，只能存储无向图
如图所示，即不会对比邻接表存储冗余信息，而且对于删除操作也很方便
查找和A相连的顶点，只需要顺着ilink的指针，即橙色的指针向下搜索即可，并且删除也只需要使得原本指向被删除节点的指针，指向被删除节点所指向的下一个节点即可
17.图的存储总结
18.图的基本操作
判断是否有一条边链接两个顶点
有向图也是同理
查找与某点相连的所有顶点
如下是无向图
采用邻接矩阵的时候直接访问一行或者一列
邻接表直接顺着链表往下找
对于有向图
邻接矩阵:查找出度直接遍历一行，入度遍历一列
邻接表，出度顺着链表向下，入度需要遍历所有边进行查找
插入顶点
无向图有向图同理
都是o1的时间复杂度，因为不需要链接边只是插入点
删除顶点
无向图
邻接矩阵：只需要逻辑删除，如果物理删除那需要移动大量的空间很不划算
对于有向图
邻接矩阵：同无向图
邻接表：出边沿着链表遍历
入边：遍历所有边
插入一条边
无向图有向图同理
邻接矩阵：只需要对链接的两个顶点置为1即可
邻接表：采用头插法插入后续所指向的顶点即可，也是o1时间复杂度
寻找与顶点相连第一个点
无向图
邻接矩阵：直接顺着一行或者一列查找
邻接表：往后找一个即可
有向图
如图所示的操作
分为查找入边和出边所指向的第一个顶点
寻找顶点的第二个邻接点
设置权值
与寻找与该邻接点的边类似
最短路径问题
BFS算法（广度优先遍历）（无权图，也可看作路径权值都为1的图）
其中粉色的数组中有这样的结构体
一个部分存储的是起始点到他的路径长度
另一个部分存储他的直接前驱
其中对于非联通图的广度优先遍历可以对visit数组进行循环遍历，判断是否存在非联通图以防止没有被遍历到
时空复杂度
可以将这个问题简化为，访问所有的顶点和所有的边去进行时间复杂度的计算
时间开销主要为访问各个顶点和找各条边
所有顶点都和初始顶点链接，所有顶点一次性全部入队
最小生成树，森林
常见考点
有向图的bfs不同的点出发需要i盗用多次visit函数
为什么路径一定是最短的？
因为如果还有别的顶点更早到达该点，那么其visit[]里的值一定是被访问过的
也就是说如果有更短的路径那么一定会先访问，所以，若visit没被访问过，那么最先访问的一定就是最短的路径
深度优先遍历(DFS)
遍历过程是递归调用的
如下所示
从二开始调用
其中每一个for循环都是为了循环遍历一个顶点所连接的所有顶点
时空复杂度
深度优先生成树和森林
常见考点
最小生成树
普利姆算法
以点找边
模拟步骤：
1.我们挑选p城进行出事的顶点进行构建，发现和p城相连的边中最短的边是1
所以我们选择1和与1与p相连的点学校
2.接着，我们在这两个顶点相连的所有的边中找到一个不构成回路的最小的边，是4，矿场这个顶点也加入其中
3.接着，我们在所有的边中再次找到一个最小的边，2以及将渔村加入其中
4.接着在加入5这条边，农场也加入其中
5.然后将最小的边3加入其中，并加加入电站这个点，构成了最小生成树
kruskal算法
以边找点
1.第一轮找到最小的权值边为1，将学校和p城放入点集中
2.找到最小的边为2，将矿场和渔村放入点集中
3.找到最小的边3，将农场和电站放入点集
4.找到最小的边4，加入边集，因为点集中存在矿场和渔村所以不加入点集
5.找最小的边，但是发现此时最小的边4加入会构成回路，所以舍弃转而寻找第二小的边
6.找到5这条边链接农场和p城加入边集
时间复杂度
dijkstra算法（找有向图到某点的最短路径）
初始为下图所示
每次经历一轮更新dist数组后
在dist数组中找到最小的那个距离，视为下一个访问的顶点，并在final中将该顶点改成true，代表着最短路径已经被找到
其中前驱节点能够反映所经过的所有路径
能一步步逆向搜索最短路径的路径
常见考点
弗洛伊德算法
初始设立两个矩阵
一个矩阵记录各边到另一边的最短路径长度，初始状态就是个边之间相连的状态
一个矩阵记录中转点
初始时即不允许中转时矩阵如图所示
当允许中转时，我们首先用v0进行中转
其中代码如下，对于矩阵中每一个元素都需要进行如下的检查
以v2顶点距离
1.初始时检查a[2][0]>a[2][0]+A[0][0]=5不符合条件，所以不进行最短路径长度的修正
2.检查到v1时即检查A[2][1]时，如图代码所示
更新长度和path显示中转点
对矩阵所有的点进行一次遍历
0号中转
如左边算法说是，每下一阶段的路径修改和判定都需要和上一阶段的修改和判断进行对比，取得最优解，运用到了动态规划的思想
一号阶段：
以1作为中转点
n轮递推之后可以得到如下图所示的新信息
有向无环图
将一个算术表达式化简成为有向无环图方法
较为复杂，这类题目建议看网课复习
AOV网（拓扑排序）
他一定是一个有向无环图
入度为0就入栈
时空复杂度
逆拓扑排序
AOE网（关键路径）
常见考点
错题
1.生成树的边数一定只有n-1条边
例题：解析
因为树的性质是一定是顶点数-1为边数
我们假设有x个树
对于任意一棵树都有其顶点数ni-1=边数
所以所有树的边加起来为
n-x=e
即总顶点数-树的数量=边数
因为森林是由树组成的
我的答案：A
忽略任何情况下都是联通的，选择A只有在顶点拍成一串的情况下才是联通的
所以我们需要找最极限的情况即排除一个顶点，其他顶点构成无向完全图这时候我们在加上一条边即可构成最少边的情况下构成无论如何都是联通的情况
还有一个结论
即对任意一个n顶点无向完全图，如果边数大于 (n-1)(n-2)/2必定联通
该题主要对c选项进行解析
拓扑排序存在的充要条件是不存在环路
故如图所示，c选项等价于问的是，若下对角线元素为0则图中肯定不存在环
我们知道有向图的性质可知
下半矩阵中i>j
对于一行的元素来说，若a[i][j]≠0则说明存在i指向j元素的指针
而下半矩阵全部为零则说明不存在后面的元素指向前边的元素
也即所有节点都是向前指向
故i指向的元素一定大于i下标，所以不会存在环路所以c正确
答案选择：A
概念记忆和理解
dfs常用于解决拓扑排序
本题答案选择A
知识点：深度优先遍历可以判断是否存在环
如图所示代码就是用于判断是否存在环路
采用列举法将所有序列举例说明
我的答案:D
因为不知道简单路径定义所以选错
简单路径即路径中的点不重复，即不存在环和回路，即最短路径
但注意最短路径的考虑不应该存在负权环
其中本题还包括各个最短路径求解算法的总结表格
我的答案：A
正确答案：C
什么叫做单源最短路径？
即求解某一个点到其余点的最短路径，这叫做单源，所以迪杰斯特拉算法求解每一对顶点的最短路径的说法是错误的，即Ⅱ是错误的，若想通过dijkstra求解所有顶点则需要所有顶点都走一遍，所以时间复杂度是o(n³)
什么叫做含有负权的回路？
下方图所示的不是含有负权回路，只有当一个环路所有的权值加起来为负数才叫做含有负权的回路
我的答案：C
正确答案：D
Ⅲ是错误的，其中图中就有反例可以举例出来
Ⅳ是正确的，因为拓扑排序的选择就是选择入度为0的点开始，假设一开始有多个入度为0的点，那么从选择上就不知道选择哪一个作为开始
同理出度为0的点作为终止点的时候，当其他所有的点都被输出了，只剩下两个点，那么同样也不知道选择哪一个点
我的答案：D
正确答案：C
其中Ⅲ为什么是错的再图中有解答
我的答案：C
正确答案：D
以后遇到这种求多种排序的用图中解法
答案选择：C
将a1活动改成5也不会影响关键路径的产生如图
其中Ⅲ可以通过a7修改为7证明错误
其中Ⅳ是正确的，所有和共有就是能缩短
答案选择：C
对于这种题目将所有的关键路径找出
如图三种颜色三条关键路径
只有缩短所有关键路径的时间才能够缩短总时间
a选项，c和e只缩短了红蓝色的关键路径时间，黑色没变，所以工期仍然没变
b选项之缩短了蓝色的工期
c选项，d活动的减少即缩短了红蓝的弓起，f的缩短也缩短了黑色的工期，所以正确
正确答案选择：B
如图所示是重要解题思想
对于A选项来说，c的起始活动是2，它的开始顶点的最早开始时间2，c的结束顶点最迟开始时间是5
所以c活动的时间余量是5-2-1=2
对于b选项，活动g，它的开始顶点是3，结束顶点是6，所以6的最晚开始时间-3的最早开始时间-g本身持续时间=12-5-1=6
以此类推计算
