图
图的概念
图的存储结构
邻接矩阵
邻接矩阵表示法的空间复杂度为O(n^2),其中n为图的顶点数 无向图的邻接矩阵一定是一个对称矩阵(并且唯一)。因此在实际存储邻接矩阵时只需存储上(或下)三角矩阵的元素 对于无向图邻接矩阵的第行(或第列)非零元素(或非0元素)的个数正好是第ⅰ个顶点的度 对于有向图邻接矩阵的第行(或第冽)非零元素(或非元素)的个数正好是第个顶点的出度 用邻接矩阵法存储图很容易确定图中任意两个顶点之间是否有边相连。但是要确定图中有多少条边,则必须按行、按列对毎个元素进行检测所花费的时间代价很大 稠密图适合使用邻接矩阵的存储表示
邻接表
若G为无向图则所需的存储空间为O(|N|+2|E|)若G为有向图则所需的存储空间为O(|N|+|E|) 对于稀疏图采用邻接表表示将极大地节省存储空间 在邻接表中,给定一顶点,能很容易地找出它的所有邻边,因为只需要读取它的邻接表 在有向图的邻接表表示中求一个给定顶点的出度只需计算其邻接表中的结点个数 但求其顶点的入度则需要遍历全部的邻接表
图的遍历
广度优先搜索
类似二叉树的层次遍历，利用队列实现。
性能分析：
最坏的情况，空间复杂度为O（|V|） （就是所有结点都入队的情况）
时间复杂度分为两种：
-
邻接表存储：
顶点:O(|V|) 边:O(|E|)，总复杂度：O(|V|+|E|)
-
邻接矩阵：O(|V|^2)
最短路径问题可以用BFS解决。
在广度遍历的过程中可以获得一颗遍历树，也称为广度优先生成树。邻接矩阵生成树唯一，邻接表不唯一。
深度优先搜索
类似树的先序遍历，尽可能深的探索一个图。
使用栈来实现。
性能分析：
空间复杂度：O(|V|)
时间复杂度：
- 邻接矩阵：O(|V|^2)
- 邻接链表：O(|E|+|V|)
基于邻接矩阵的遍历所得到的DFS序列和BFS序列是唯一的 基于邻接表的遍历所得到的DFS序列和BFS序列是不唯一的
图的应用
最小生成树
最小生成树不唯一，但权值之和总是相同的且是最小的。最小生成树边数为顶点数-1。
Prim算法：
- 时间复杂度O(|V|^2),不依赖E
- 适合边多点少的图
Kruskal算法：
- 时间复杂度O(log|E|)
- 适合边疏散顶点多的图
最短路径
Dijkstra算法：
时间复杂度：两种存储结构都是O(|V|^2)
不适用于边权值为负数的情况
Floyd算法：
时间复杂度：O(|V|^3)
允许带负值的权值
拓扑排序
每个顶点出现且只出现一次 若顶点A在序列中排在顶点B的前面则在图中不存在从顶点B到顶点A的路径
拓扑排序流程：
- 从AOV网中选择一个没有前驱的顶点并输出
- 从网中删除该顶点和所有以它为起点的有向边
- 重复①和②直到当前的Ao网为空或当前网中不存在无前驱的顶点为止后一种情况说明有向图中必然存在环
需要注意的点
- 入度为零的顶点即没有前驱活动的或前驱活动都已经完成的顶点工程可以从这个顶点所代表的活动开始或继续
- 若一个顶点有多个直接后继,则拓扑排序的结果通常不唯一
- 若各个顶点已经排在一个线性有序的序列中每个顶点有
- 唯一的前驱后继关系则拓扑排序的结果是唯一的
- 生成AOV网的新的邻接存储矩阵,可以是三角矩阵
- 对于一般的图来说若其邻接矩阵是三角矩阵,则存在拓扑序列;反之则不一定成立
- 拓扑排序、逆拓扑排序序列可能不唯 若图中有环,则不存在拓扑排序序列/逆拓扑排序序列
关键路径
关键路径上的所有活动都是关键活动是决定整个工程的关键因素,因此可通过加快关键活动来缩短整个工程的工期 不能任意缩短关键活动因为一旦缩短到一定的程度该关键活动就可能会变成非关键活动 网中的关键路径并不唯一,只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的 若关键活动耗时增加,则整个工程的工期将增长 缩短关键活动的时间,可以缩短整个工程的工期 当缩短到一定程度时,关键活动可能会变成非关键活动
易错点
- 如果无向连通图没有权值相同的边，则最小生成树唯一（遍历方式唯一）
- 有向图邻接矩阵为三角矩阵（对角线上元素为0），则不存在环