6.1 图的基本概念
主要掌握==深度优先==搜索与==广度优先==搜索。掌握图的基本概念及基本性质、图的存储结构（邻接矩阵、邻接表、邻接多重表和十字链表）及其特性、存储结构之间的转化。基于存储结构上的遍历操作和各种应用（拓扑排序、最小生成树、最短路径和关键路径）等。图的相关算法较多通常只要求掌握其基本思想和实现步骤，而算法的具体实现不是重点。
6.1.1 图的定义
图G由顶点集V和边集E组成，记为G=(V,E) 其中V(G)表示图G中顶点的==有限非空集==；E(G)表示图G中顶点之间的关系（边）集合。
线性表可以是空表，树可以是空树，但图==不可以是空图==。图的顶点集V一定非空，但边集召可以为空，此时只有顶点而没有边。
稠密图与稀疏图
有向图
无向图
简单图、多重图
不存在重复的边与和自己连接的环。一般数据结构中仅仅讨论简单图。
完全图（简单完全图）
各个点之间都有边
子图、生成子图
G的一部分边与点构成的图。并非V和E的任何子集都能构成G的子图，因为这样的子集可能不是图。 若==V(G)=V(G')==，子图G‘是G的生成子图
路径、路径长度与回路
路径指包括首尾的由边连着的链状的==点集==。 路径长度是==边的个数==。 回路指==首尾相连==。
简单路径与简单回路
==没有重复==的顶点，当然不包括首尾。
距离
==最短的路径长度==。
网与权
带权路径长度：一条路径所有边的权的和。
连通、连通图与连通分量（针对无向图）
对于n个顶点的G图： 是连通图，至少有n-1条边 非连通图，最多有以n-2为底的C^2 
强连通图与强连通分量（针对有向图）
有向图强连通情况下边最少的情况：至少需要n条边，构成一个环路。
有向树
顶点的度、入度与出度
无向图：所有点度的和 = 2 * 边的数量 有向图：入度和 = 出度和 = 边的数量
6.2 图的存储形式与基本操作
6.2.1 邻接矩阵
将邻接的关系保存在二维数组中。
特点
- 无向图的邻接矩阵是==对称矩阵==，对规模特大的邻接矩阵可采用==压缩存储==。
- 邻接矩阵表示法的空间复杂度为 O(|V|)
- 对于无向图，邻接矩阵的第i行(或第i列)非零元素(或非∞元素)的个数正好是顶点 i 的度 TD(v)。
- 用邻接矩阵存储图，很容易确定图中两个顶点之间是否有边相连。但是，要确定图中有多少条边、则必须按行、按列对每个元素进行检测，花费的时间代价很大。
- ==稠密图==适合使用邻接矩阵的存储表示。
6.2.2 邻接表
一个图为稀疏图时，使用邻接矩阵法要浪费大量空间。图的邻接表法结合了顺序存储和链式存储方法，大大减少浪费。
特点：
- 若 G为无向图，则所需的存储空间为 O(|V|+2|E|)，2是由于无向图中，每条边在邻接表中出现了两次。
- 若 G为有向图，则所需的存储空间为O(|V|+|E|)
- 对于稀疏图，采用邻接表表示将极大地节省存储空间。
- 在邻接表中，能很容易地找出一个顶点的所有邻边。在邻接矩阵中，相同的操作则需要扫描一行，花费的时间为 0(n)。
- 若要确定给定的两个顶点间是否存在边，则在邻接矩阵中可以立刻查到，而在邻接表中则需要在相应结点对应的边表中查找另一结点，效率较低。
- 图的邻接表表示并不唯一，它取决于建立邻接表的算法及边的输入次序。而邻接矩阵是唯一的。
- 在有向图的邻接表表示中，求一个给定顶点的出度只需计算其邻接表中的结点个数;但求其顶点的入度则需要遍历全部的邻接表。
6.2.3 十字链表（有向图）
图的十字链表表示是不唯一的，但一个十字链表表示确定一个图。 空间复杂度：O(|V|+|E|)
6.2.4 邻接多重表（无向图）
空间复杂度：O(|V|+|E|)
理解，邻接多重表与十字链表，其代码实现较复杂，不会考察代码。
6.2.5 图的基本操作
- Adjacent(G,x,y):判断图G是否存在边<x,y>或(x,y)。
6.3 图的遍历
6.3.1 广度优先搜索BFS
遍历图的过程是以v为起始点，由近至远依次访问和，有路径相通且路径长度为1,2,…的顶点。算法必须借助一个辅助队列，以记忆正在访问的顶点的下一层项点。、
性能分析
- 无论是邻接表还是邻接矩阵的存储方式，BFS 算法都需要借助一个辅助队列，在最坏的情况下，空间复杂度为 O(|V|)。
- 邻接表，每个顶点均需搜索一次(或入队一次)，故时间复杂度为 O(|V|)，在搜索任意一个顶点的邻接点时，每条边至少访问一次，故时间复杂度为 O(E)，算法总的时间复杂度为 O(|V|+|E|)。
- 邻接矩阵，査找每个顶点的邻接点所需的时间为 O(|V|)，故算法总的时间复杂度为 O(IV|^2)。
广度优先生成树与森林
广度遍历得到一棵遍历树，称为广度优先生成树：
- 邻接矩阵存储表示是唯一的，其广度优先生成树也是唯一的，
- 邻接表存储表示不唯一，广度优先生成树是不唯一的。 广度优先生成树组成的森林就是广度优先生成森林
6.3.2 深度优先搜索DFS
优先探索结点的孩子，直到叶子结点。之后再回溯，继续探索没有探索的孩子结点。
性能分析
- DFS 算法都需要借助栈，在最坏的情况下，空间复杂度为 O(|V|)，最好O(1)
- 邻接表时间复杂度O(|V|+|E|)
- 邻接矩阵时间复杂度O(IV|^2)
深度优先生成树与森林
同一个图的邻接矩阵表示方式唯一，深度优先遍历序列唯一，树也唯一 同一个图邻接表表示方式不唯一，深度优先遍历序列不唯一，树不唯一
图的遍历与连通性
无向图：DFS、BFS调用与连通分量数相同的次数 有向图：若起始点到其他的所有顶点都有路径，那么只调用一次。其余情况要具体分析。
6.4 图的应用
一般而言，这部分内容直接以算法设计题形式考查的可能性很小，而更多的是结合的实例来考查算法的具体手动操作过程。
6.4.1 最小生成树
各边权值之和最小的生成树
生成树
一个连通图的生成树包含图的所有顶点，并且只含尽可能少的边。对于生成树来说，若砍去它的一条边，则会使生成树变成非连通图;若给它增加一条边，则会形成图中的一条回路。
性质
- 最小生成树并不是唯一的。只有在图的各边的权值互不相同的时候才是唯一的。
- G本身是一棵树时，则G的最小生成树就是它本身。
- 最小生成树的边数为顶点数减1。
- 最小生成树的边的权值之和总是唯一的，而且是最小的，虽然树本身并不唯一。
- 假设 G=(V,E)是一个带权连通无向图，U是顶点集V的一个非空子集。若(u,v)是一条具有最小权值的边，其中u属于U，v属于V-U，则必存在一棵包含边(u,v)的最小生成树。
Prim算法
从开始的点，选择一条权值最小的边，加入U中。再在U中所有点的边中选择一条权值最小的边。重复，直到全部加入U中。
时间复杂度：O(|V^2|)。适合用于求解边稠密的图。
Kruskal算法
最开始将所有的点视为一个连通分量，在这些连通分量中寻找权值最短的边，被边连上的点，算为一个新的连通分量。重复，直到只剩一个连通分量。
时间复杂度：O(|E|log2|E|)。适合于边稀疏而顶点较多的图。
6.4.2 最短路径
最短路径：权值最少的路径
- 单源最短路径：从一个结点出发。
- BFS
- Dijkstra
- 每对顶点间的最短路径：将所有的结点之间的最短路径都求出来。
- Floyd
BFS求无权图的单源最短路径
将无权图视为权位1，实现的过程与BFS遍历很像。要添加辅助数组，记录距离与前驱 
Dijkstra算法求单源最短路径（贪心）
每轮选择距离最短的顶点固定，将这个点连接的所有边加上到他自己的距离的和如果小于对应顶点的距离，就更新。重复，直到将所有的点固定。固定的点不再参与比较。 在这个图中，顶点5在第一轮距离为5，值最小，就固定，它与2、4相连，2+5=7，3+5=8<10。都符合更新的条件。 边上带有负权值时，Dijkstra 算法并不适用。
Floyd算法求每对顶点间的最短路径（DP）
考试只会考阶数较少的，如3阶：
时间复杂度，O(|V^3|) 空间复杂度，O(IV^2|)
6.4.3 有向无环图表达式
若一个有向图中不存在环，则称为有向无环图，简称 DAG 图。 有向无环图是描述含有公共子式的表达式的有效工具。例如表达式 ( (a+b) * (b * (c+d))+(c+d) * e) * ((c+d) * e )
利用有向无环图，则可实现对相同子式的共享，从而节省存储空间 
表达式中的字母会作为树的==叶子结点==，同时==不会重复==。
6.4.4 拓扑排序
使用有向无环图来表示具有“前后顺序”的活动
时间复杂度：O(|V|+|E|)，若采用邻接矩阵则需O(|V|^2)
算法实现
- 从 AOV 网中选择一个没有前驱的顶点并输出。
- 从网中删除该顶点和所有以它为起点的有向边。
- 重复，直到没有点。
逆拓扑排序
逆着图来做
6.4.5 关键路径
在AOE网中，具有最大路径长度的路径称为关键路径，而把关键路径上的活动称为关键活动，就是整个工程想要完成的最短时间。特性：
- 关键活动耗时增加，整个工程时间增加。
- 关键活动耗时减少，整个工程时间减少。
- 关键活动耗时减少到一定程度，可能会变为非关键活动。
- 可能具有多条关键路径（耗时相同）。
AOE网
可以将顶点理解为一瞬间完成，而边需要一段时间。
相关定义
若果一个活动的时间余量为0，那么它就是关键活动，由关键活动组成的路径，就是关键路径。
算法
