数据结构-第六章-图
6.1 图的基本概念
图G由顶点集V和边集E组成，记为G = (V, E)
树可以是空树，图不可以为空图
##1. 有向图
2. 无向图
3. 简单图，多重图
满足：
- 不存在重复边
- 不存在顶点到自身的边
满足上述两点则为简单图
图6.1中G1，G2均为简单图
如果图G中某两个顶点之间的边数大于1条，又允许顶点通过一条边和自身关联，则为多重图
4. 完全图（简单完全图）
对于无向图，有n(n - 1)/2条边的无向图称为完全图
对于有向图，有n(n - 1)条弧的有向图称为有向完全图
5. 子图
设两个图G = (V, E)和G' = (v', E')，若V'是V的子集，且E'是E的子集，则称G'是G的子图
若有满足V(G') = V(G)的子图G'，则称其为G的生成子图
G3为G1的生成子图
6. 连通，连通图和连通分量
无向图中的极大连通子图称为连通分量
假设一个图有n个顶点，如果边数小与n-1，那么此图必是非连通图
7. 强连通图，强连通分量
在有向图中
如果有一对顶点v和w，从v到w和从w到v之间都有路径，则称这两个顶点是强连通的。若图中任何一对顶点都是强连通的，则称此图为强连通图
在有向图中的极大强连通子图称为有向图的强连通分量
在无向图中讨论连通性，在有向图中讨论强连通性
8. 生成树，生成森林
连通图的生成树是包含图中全部顶点的一个极小连通子图
对生成树，若砍去它的一条边，则会变成非连通图，若加上一条边，则会形成一个回路
在非连通图中，连通分量的生成树构成了非连通图的生成森林
区分极大连通子图和极小连通子图
极大连通子图是无向图的连通分量，极大即要求该要求该连通子图包含其所有的边，极小连通子图是既要保持连通又要使得边数最少的子图
9. 顶点的度，入度和出度
无向图的全部顶点的度的和等于边数的2倍
度：TD(v)
入度: ID(v)
出度: OD(v)
10. 路径，路径长度和回路
路径指顶点a到b的顶点序列
路径上边的数目为路径长度
第一个顶点和最后一个顶点相同的路径称为回路或环
若一个图有n个顶点，并且有大于n-1条边，则此图一定有环
11. 简单路径，简单回路
在路径序列中，顶点不重复出现的路径称为简单路径
除第一个顶点和最后一个顶点外，其他顶点不重复出现的回路称为简单回路
12. 距离
从顶点u出发到顶点v的最短路径若存在，则此路径的长度成称为从u到v的距离
13. 有向树
一个顶点的入度为0，其余顶点的入度均为1的有向图，称为有向树
总结
有向完全图一定是强连通有向图
一个有28条边的非连通无向图至少有（）个顶点
先假设28条边构成一个完全无向图，则 n(n-1)/2 = 28，n = 8
则再增加一个顶点，就为非连通， 8 + 1 = 9
对于一个有n个顶点的图，若是连通无向图，其边数至少为
n-1，若是强连通有向图，其边的个数至少为n无向图的全部顶点的度的和等于边数的2倍
6.2 图的存储及基本操作
6.2.1 邻接矩阵法
特点：
- 无向图的邻接矩阵一定是一个对称矩阵，因此，在实际存储邻接矩阵时只需存储上（或下）三角矩阵的元素
- 对于无向图，邻接矩阵的第
i行（或i列）非零元素（或非∞元素）的个数正好是顶点i的度\(TD(v_i)\) - 对于有向图，邻接矩阵的第
i行非零元素的个数正好是顶点i的出度OD，第i列非零元素的个数正好是顶点i的入度ID - 用邻接矩阵存储图，很容易确定图中任意两个顶点之间是否有边相连，但是，要确定图中有多少条边，则必须按行，按列对每个元素进行检测，所花费的时间代价很大
- 稠密图适合使用邻接矩阵的存储表示
- 设图G的邻接矩阵为A，A''的元素
A''[i][j],等于由顶点i到顶点j的长度为n的路径的数目
6.2.2 邻接表法
当一个图为稀疏图时，使用邻接矩阵显然要浪费大量的存储空间，而图的邻接表法结合了顺序存储和链式存储，大大减少了折中不必要的浪费
特点：
- 若图G为无向图，则所需的存储空间为
O(|v| + 2|E|)，若G为有向图，则所需的存储空间为O(|V| + |E|) - 对于稀疏图，采用邻接表可以极大地节省存储空间
- 在邻接表中，给定一顶点，能很容易地找出它的所有邻边，在邻接矩阵中，相同的操作则需要扫描一行，花费的时间为
O(n)。但是，要确定给定的两个顶点间是否存在边，则在邻接矩阵中可以立刻查到，而在邻接表中则需要在相应结点对应的边表中查找另一结点，效率较低 - 在有向图的邻接表中，求一个给定顶点的出度只需计算其邻接表中的结点个数，但求其顶点的入度则需要遍历全部邻接表
- 图的邻接表表示并不唯一
6.2.3 十字链表
十字链表是有向图的一种链式存储结构
图的十字链表表示是不唯一的，但一个十字链表表示确定一个图
6.2.4 邻接多重表
邻接多重表是无向图的另一种链式存储结构
总结
- 图的邻接矩阵表示唯一，邻接表表示不唯一
- 若邻接表中有奇数个边表结点，则图为有向图
- 在有向图的邻接表存储结构中，顶点V在边表中出现的次数是顶点V的入度
顶点1的出度为顶点1的边表个数 入度为在全部边表中出现的个数
- n个顶点的无向图的邻接表最多有
n(n - 1)个边表结点，因为n个顶点的无向图最多有n(n-1)/2条边
6.3 图的遍历
6.3.1 广度优先搜索（BFS）
相当于树的层次遍历
需借助一个辅助队列
性能分析：
空间复杂度为：O(|V|)
时间复杂度：
邻接表：O(|V| + |E|)
邻接矩阵：\(O(|V|^2)\)
BFS算法求解单源最短路径问题
邻接矩阵的广度优先生成树是唯一的，邻接表的不唯一
6.3.2 深度优先搜索（DFS）
类似与树的先序遍历
空间复杂度：O(|V|)
时间复杂度：
邻接表：O(|V| + |E|)
邻接矩阵：\(O(|V|^2)\)
6.3.3 图的遍历与图的连通性
图的遍历算法可以用来判断图的连通性
总结
- 判断有向图中是否存在回路，除了可以用拓扑排序外，还可以利用深度优先遍历算法
6.4 图的应用（重点）
6.4.1 最小生成树
一个连通图的生成树包含图中的所有顶点，并且尽可能少的边
- 最小生成树不是唯一的
- 最小生成树的边的权值之和总是唯一的，而且是最小的
- 最小生成树的边数为顶点数减1
最小生成树算法：Prim算法和Kruskal算法
Prim算法（顶点）
每次选择顶点集合距离最近的顶点
时间复杂度：\(O(|V|^2)\)
不依赖与|E|，因此它适用于求解边稠密度图的最小生成树
Kruskal算法（权值）
时间复杂度：O(|E|log|E|)
适用于边稀疏而顶点较多的图
6.4.2 最短路径
带权路径长度最短的路径----最短路径
- 单源最短路径-->
Dilkstra(迪杰斯特拉) - 每个顶点间的最短路径-->
Floyd(佛洛伊德)
1. Dijkstra算法求解单源最短路径问题
时间复杂度：
邻接表：\(O(|V|^2)\)
邻接矩阵：\(O(|V|^2)\)
Dijkstra不适用于权值为负的
2. Floyd算法求解各顶点之间最短路径长度
时间复杂度：\(O(|V|^3)\)
6.4.3 有向无环图
DAG图：有向无环图（有向图不存在环）
6.4.4 拓扑排序
AOV网：若用DAG图表示一个工程，其顶点表示活动，用有向边\(<V_i,V_j>\)表示活动\(V_i\)必须先于活动\(V_j\)进行的一种关系
特点：
- 每个顶点出现且只出现一次
- 若顶点A在序列中排在顶点B的前面，则在图中不存在从顶点B到顶点A的路径
时间复杂度：
| 邻接表 | 邻接矩阵 |
|---|---|
| O(V + E) | \(O(V^2)\) |
若其邻接矩阵是三角矩阵，则存在拓扑序列，反之则不一定成立
6.4.5 关键路径
AOE网：在带权有向图中，以顶点表示事件，以有向边表示活动，以边上权值表示完成该活动的开销
性质：
- 只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始
- 只有在进入某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发生
关键路径： 从源点到汇点的所有路径中，具有最大路径长度的路径
关键路径上的活动称为关键活动
1. 事件\(V_k\)的最早发生时间ve(k)
ve(源点) = 0
ve(k) = max(ve(j) + weight(\(v_j, v_k\)))
2. 事件\(v_k\)的最迟发生时间vl(k)
vl(汇点) = ve(汇点)
vl(k) = min( vl(j) - weight(\(v_k. v_j\))) \(v_k\)为\(v_j\)的任意前驱
3. 活动\(a_i\)的最早开始时间e(i)
4. 活动\(a_i\)的最迟开始时间l(i)
5. 差值 d(i) = l(i) - e(i)
总结
- 关键路径上的所有活动都是关键活动，因此可通过加快关键活动来缩短整个工程的工期
- 网中的关键路径并不唯一，对于有几条关键路径的网，只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期，只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的
- 只要无向连通图中没有权值相同的边，则其最小生成树唯一
- 深度优先遍历，拓扑排序，求关键路径 可以判断一个有向图是否有环（回路）