第六章 图
一、图
1.定义：V是顶点集，E是边集；|V|表示顶点数，称为阶；|E|表示边数；有向图叫弧<>，无向叫边（） ；
- 有向图：有方向，<v,w>的v和w之间是有序的，v弧尾（不带箭头），w弧头（带箭头）；
- 无向图：无方向，<v,w>的v和w之间是无序的；
- 权：两顶点之间的距离；
- 路径：两顶点间经过的点边上的数目，若第一个顶点和最后一个顶点路径相同，叫做环；如果一个图有n个顶点，且有大于n-1条边，则该图一定有环。
- 简单路径：顶点不重复；
- 简单回路：除第一个顶点和最后个顶点外，其余顶点也不重复出现；
2.简单图：无重复边，不存在顶点到自身的边；有n个顶点的向完有全图有n(n-1)条边；
3.完全图：任意两顶点间都存在边；有n个顶点的无向完全图有n(n-1)/2条边；
- 完全无向图：存在两个不相同的点且两点间有一条无向边；
- 完全有向图：存在两个不相同的点且两点间有一条弧；
4.稀疏图和稠密图：很少边，很少弧，判断标准e<nlog₂n，反之为稠密图；
5.子图和生成子图：顶点和边都属于另一个图，则叫子图；顶点数与图相等，但边只属于该图，则叫生成子图；
6.连通：在无向图中，只要存在路径就是连通的；
- 连通图：任意两点中只要存在路径就是连通的，否则不是；
- 连通分量：无向图的极大（极大要求该连通子图包含其所有的边）连通子图称为该图的连通分量；任何连通图的连通分量只有一个，即是自身，非连通图的无向图有多个连通分量；如果一个图有n个顶点，且小于n-1条边，则此图必为连通图；
- 强连通图：在有向图中任意一对顶点都强连通的；
- 强连通分量：在有向图中的极大强连通子图称为有向图的强连通分量；
7.顶点的邻接(Adjacent)：对于无向图G=(V，E)，若边(v,w)EE，则称顶点v和w互为邻接点，即v和w相邻接。
顶点的度、入度、出度：对于无向图G=(V，E)，VvieV，图G中依附于的边的数目称为顶点的度(degree)，记为TD(vi)。
显然，在无向图中，所有顶点度的和是图中边的2倍。 即 ∑TD(vi)=2e ；i=1,2…n ，e为图的边数。(度和公式)。
8.对有向图G=(V，E)，若存在vi∈V ，图G中以vi作为起点的有向边(弧)的数目称为顶点vi的出度(Outdegree)，记为OD(vi);以vi作为终点的有向边(弧)的数目称为顶点的入度(Indegree)，记为ID(vi)。顶点的出度与入度之和称为的度，记为TD(vi)。即TD(vi)=OD(vi)+ID(vi)；
二、图的存储
1.存储结构：邻接矩阵、邻接链表、邻接多重表和边表；
2.邻接矩阵（无向图和有向图都各有无权图和有权图两类）
- 无向图的数组表示
- 特点： 对称方阵；顶点相邻的边数等于该点度数；图所有边数等于下或上三角的非0元素的个数；
- 无权图的邻接矩阵
- 带权图的邻接矩阵
- 有向图数组表示
- 特点： 某行的非0元素个数对应是出度，某列的非0元素个数对应入度；
- 无权图的邻接矩阵
- 带权图的邻接矩阵
3.邻接链表法：对图的每个顶点建立一个单链表，存储该顶点所有邻接顶点及其相关信息。每一个单链表设一个表头结点。
- 特点：对有向图可以建立正邻接表或逆邻接表；在有向图中，第i个链表中结点数是顶点的出或入度，求出或入度需要遍历整个邻接表；
- 无向图的邻接表
- 有向图的邻接表
三、图的遍历
1.图的遍历算法
- 深度优先搜索算法：类似树的先序遍历，是树的先序遍历的推广；借助栈实现，是递归算法，空间复杂度O(V)；以邻接矩阵表示时时间复杂度O(V²)，以邻接表表示时时间复杂度为O(e+V)；
- 广度优先搜索算法：类似于树的按层次遍历，借助队列实现，空间复杂度O(V)；以邻接矩阵表示时时间复杂度O(V²)，以邻接表表示时时间复杂度O(e+V)；
四、图的应用
1.最小生成树：如果连通图是一个带权图，则其生成树中的边也带权，生成树中所有边的权值之和称为生成树的代价。带权连通图中代价最小的生成树称为最小生成树；
- 基本原则是:
- 尽可能选取权值最小的边，但不能构成回路;
- 选择n-1条边构成最小生成树。
- 普里姆(Prim)算法：整个算法的时间复杂度是O(n²)，与边的数目无关，适用于求解稠密图最小生成树。
- 克鲁斯卡尔(Kruskal)算法：整个算法的时间复杂度是O(eloge)；适用于边稀疏而顶点较多的图。
2.最短路径：带权有向图的最短路径，也适用于无向图。将一个路径的起始顶点称为源点，最后一个顶点称为 终点。
- 单源点最短路径
- 迪杰斯特拉算法：一个顶点到每个顶点的最短路径；按路径长度递增次序；时间复杂度是O(n²)；
- 弗洛伊德算法：每一对顶点之间的最短路径，时间复杂度O(n³)；
3.AOV网：顶点表示活动，弧表示优先关系；
- 特点：弧表示活动间存在某种制约关系；不能出现回路；
- 拓扑排序：对一个有向图构造拓扑序列的过程；时间复杂度O(n+e)；使得AOV网中所有应有存在的前驱和后继关系都能得到满足；（简单来说就是找入度为0的点然后挨个去掉）；若AOV网中存在回路即写不出拓扑排序。
4.AOE网：求关键路径，基于有向图；边表示活动；AOE网中没有入边的顶点叫始点，没有出边的叫终点；
- 关键路径：始点到终点具有最大路径长度，该路径上的各个活动所持续的时间之和的路径称为关键路径（类似工程所需的最短工期）；
- ▲关键活动：关键路径上的活动称为关键活动；
- 事件的最早发生时间ve[k]；
- 事件的最迟发生时间vl[k]；
- 活动的最早开始时间e[i]；
- 活动的最晚开始时间l[i]；
- 关键活动：l[i]=e[i]的活动（红色部分是由关键活动组成的路径，叫关键路径）；