图与图算法¶
图的基本概念,存储与遍历¶
图是一个二元组\(G=(V,E)\)其中\(V\)为顶点的集合,\(E\)是两个顶点间边(弧)的集合
图的基本术语¶
有向图 弧(边)具有方向性的图,用\(<V_1,V_2>\)表示一条由\(A_1\rightarrow A_2\)有向弧,其中\(A_1\)被称为弧尾,\(A_2\)被称为弧头.
无向图 弧(边)不具有方向性的图,用\((V_1,V_2)\)表示\(V_1,V_2\)之间具有一条无向边.
在使用中一般将无向图视为具有两条有向边的有向图处理
出度,入度,与度 有向图的出度,是某一顶点射出的弧的个数;有向图的入度,是某一顶点射入弧的个数;无向图的度,是某一顶点连接弧的总数
简单图与多重图 若一个图中不含重边也不包含自环则为简单图,否则为多重图.
完全图 点与点之间有向边(无向边)都存在,其中无向图边数为\(C_{n}^{2}=n(n-1)/2\),有向图为\(P_{n}^{2}=n(n-1)\)
子图 假设有两个图\(G=(V,E), G'=(V',E')\),若有\(V'\subset V, E'\subset E\),则称\(G'\)为\(G\)的子图
连通图,连通分量与生成树
连通图若一个无向图任意两点直接都存在路径则称该图为一个连通图,若一个有向图任意两个顶点直接也都存在一条路径则称该图为强连通图.
连通分量在一个无向图中,若存在某一个子图是连通图,加上一个顶点后导致不连通,则称该子图为极大连通子图;若是有向图则称为强连通分量.
生成树连通图的生成树是指其的最小连通子图.该连通子图具有所有n个顶点,但只有n-1条边,如果去掉一条边则必定不连通;如果加上一条边则会产生回路.
Warning
生成树并不唯一
图的存储 (邻接矩阵+邻接表)¶
邻接矩阵(顺序存储)
空间复杂度 \(O(n^2)\) 适合存储稠密图(\(m\approx O(n^2)\))
对于无向图,连接矩阵一定是一个对称矩阵,只需要存储\(\frac{n(n-1)}{2}\)个元素即可
邻接表(链式存储)
空间复杂度 \(O(\max{(n,m)})\)
逆邻接表 记录指向顶点的边,而非从顶点指出的边,便于计算入度.
临接多重表
对于某个结点,其边结点更改为存储两个点的信息
比如说A与其相连的边有三条(A,C)(A,E)(A,D),随便选一条边作为其边结点,这里选择的是(0,3)->(A,D)
由于结点0的位于ver1字段中,遍历next1字段的下一个结点,发现0仍然在ver1字段,故(0,2)->(A,C)也存在边
接着遍历var1的next1结点,发现0还在,故(0,4)->(A,E)也有一条边,
此时var1的next1指向空,所以边就找完了.
邻接多重表式对无向图需要存储两次同一条边的优化
十字链表
十字链表是对有向图一次只能简单读出度\入度问题的优化
图的遍历¶
主要有dfs和bfs两种,需要掌握手动模拟和代码.
简单来说深度优先遍历就是一路走到黑,不撞南墙不回头;而宽度优先遍历则是优先遍历最近的点.
在代码实现上dfs通常用递归实现,代码比较简单;bfs通过队列实现,代码比较长.
算法实现
图算法¶
Dijkstra算法(单源无负权重最短路问题)¶
解决从一个顶点到其他顶点间的最短路问题
考研一般只需要掌握距离矩阵的如何更新,会手动模拟Dijkstra的过程即可.当然不排除考察代码实现
算法描述
- 初始化:
- 设置源点s的距离为0(dist[s] = 0)
- 其他所有顶点距离初始化为无穷大
- 集合S初始为空
- 主循环:
- 从未确定顶点中选择距离最小的顶点u
- 将u加入集合S(表示已确定u的最短路径)
- 对u的所有邻居v进行松弛操作:
- 如果dist[u] + w(u,v) < dist[v],则更新dist[v] -终止条件:
- 当所有顶点都加入S时,算法结束
算法实现
Floyd算法 (三重循环--DP)¶
解决所有顶点到其他顶点最短路问题
这个很少考察,本质是基于DP的但DP不属于考研内容.
算法实现
Prim算法(选点)¶
算法描述
- 初始化一个空的最小生成树集合(通常记作 U)
- 任选一个起始顶点加入 U
- 在连接 U 与 V-U(未选顶点集)的所有边中,选择权重最小的边及其对应的新顶点
- 将该顶点加入 U
- 重复直到 U 包含所有顶点
算法实现
Kruskal算法(选边)¶
算法描述
- 初始化
- 将图中所有的边权按从小到大排序
- 创建一个空的边集
- 初始化一个并查集,用于检测是否有环路
- 遍历所有边(按排序后的结果)
- 对于当前边(u,v),检查(u,v)是否是一个集合
- 如果不在,则将该边加入边集,并在并查集中合并u和v
- 如果存在,则跳过这条边
- 当边集包含(n-1)条边的时候算法结束.
算法实现
拓扑排序与关键路径(AOE)¶
拓扑排序本质是描述一种前驱关系,只有有向无环图(DAG)才有拓扑序列.
算法描述(基于入度的实现)
- 计算每个顶点的入度
- 选择一个入度为0的点加入队列
- 当队列不为空的时候
- 取出队首元素记作u,并输出
- 对于u的所有邻接点v
- 将v的入度减1
- 如果v的入度减为0则加入队列
- 如果输出顶点树不等于图中顶点数则说明图存在环
- 若在算法过程中队列中最大元素大于1,则说明拓扑序列不唯一
算法实现
C++ | |
---|---|
算法描述(基于DFS实现) - 对图进行深度优先遍历 - 当一个顶点完成对其所有邻接顶点的访问后,将该顶点加入列表头 - 最终的结果即为拓扑排序
如果不加入头,而是加入列表尾则输出的是逆拓扑序列
AOE网相关内容 - 活动 (activity-> A) 弧(edge->E)表示活动,弧的权值表示活动时间 - 时间 顶点表示事件,事件在指向其的弧全部完成后被触发 - 关键路径 权值之和最大的那一条路径
对于最迟开始时间和最早开始时间的计算
- 事件最早开始时间
- 源点的最早开始时间为0,从源点按照拓扑序列计算
- 对于顶点v,其最早开始时间等于其所有前驱结点的最早开始时间与对应活动时间之和的最大值
- 事件最迟开始时间
- 汇点的最迟开始时间为关键路径权值之和,从汇点开始按照逆拓扑排序计算
- 对于顶点v,其最迟开始的事件等于其所有后继结点的最迟开始时间与对应活动之差的最小值
对于活动 \(E<i,j>\) 其最早开始时间为 \(EST[i]\) ,最晚开始时间为 \(LST[j]-duration(i,j)\) 其中duration表示活动\(<i,j>\)的持续时间
以下面这个例题说明具体计算过程
首先确定事件(顶点的)最早开始时间,从源点1
开始,其最早开始时间为0
接着按照拓扑序,应该确定2
和3
的`最早开始时间,显然为2和5
其他类似....,可以得到
1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|
0 | 2 | 5 | 8 | 9 | 12 |
再确定事件的最迟发生时间,从汇点6
开始,其最迟发生事件为12
接着按照逆拓扑序确定,所谓逆拓扑序就是每次寻找出度为0的结点
例如再6
确定后,只有5
的出度为0故确定结点5的最迟发生事件,等于其所有后继结点与活动持续时间之差的最小值,由于5
只有6
一个后继结点,故其最晚发生时间为11
接着发现只有4
的出度为0,而其后继结点为5
和6
分别减去其对应活动的持续时间为10,8
取最小值,结果为8
其余结点类似,最终有
1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|
0 | 4 | 5 | 8 | 11 | 12 |
确定了事件后通过活动与时间的关系可以很容易的确定活动的最早开始时间和最晚开始时间.
例如活动a
其最早开始时间与弧尾1
的最早开始时间一致,而最迟开始时间为弧头2
的最迟开始-活动a
的持续时间=4-2=2,其余结点类似.