[算法] 图论

2019-01-15 本文已影响0人 jingy_ella

图的表示

邻接矩阵
int G [maxv][maxv]或<vector<vector<int> > G
数组元素存储连接与否或连接权重的信息
如果有多个边的相关属性，例如多个权重，则可以声明边的结构体 struct edge替换上面的int
如果有多个节点的相关属性，例如节点的颜色、访问时间、估计最短距离等，只需再单独声明|V|大小的一维数组即可
邻接表
vector<int> G[maxv]

for(int i = 0; i < E; i++)  {
  cin >> s >> t;
  G[s].push_back[t];
  // G[t].push_back[s];
}

每个节点的邻接表中存储连接信息，也可以表示为<vector<vector<int> > G，但与邻接矩阵不同这只能表示无权重图，对于单权重图也需要声明边结构体：
struct edge { int to; int cost; }
vector<edge> G[maxv]

1. 搜索

对于连通图，一次搜索可访问全部节点

BFS

利用BFS可求：

无权图从给定源点出发到所以可以到达结点间的最短路径
树的直径(树的所有最短路径距离的最大值)：两次BFS即可实现，第二次BFS选择第一次遍历得到的最长路径的末节点作为源节点

DFS

深度优先森林的前驱子图的深度优先森林中包含：
树边（遍历路径）、后向边（已访问过的某级父节点）、前向边（已访问过的某子节点）、横边（其他所有的边，包括不同树间的边）
第一次访问边（u,v）时，如果v为白色即树边，如果v为灰色即后向边，如果v为黑色即横向边或前向边（无向图中是不会出现前向边和横向边的）

利用DFS可求：

有向图或无向图是无环图<=>DFS不产生后向边
对于无向图这一判定算法的时间复杂度O(V)与E无关，因为对于无环的森林|E| < |V|-1，因此如果存在后向边，遍历V个结点后后向边一定已经出现
拓扑排序
DFS结束时间的反序
$O(V+E)$
连通分量
无向图的连通分量个数即DFS森林树的颗数
有向图的强连通分量即对G和G的转置分别DFS得到的结果
有向图的单连通分量判定：
从每个点作一次DFS，得到一棵DFS树，如果没有出现DFS树内cross edge和forward edge，则此图必为单连通图
有向图的半连通分量判定：
计算强连通分量，对得到的分量图SCC进行拓扑排序，如果拓扑排序的结果<v1,v2...vk>线性链的各边<v0,v1>..<vk-1,vk>存在，则半连通
时间复杂度O(V+E)
衔接点、桥、双连通分量
朴素方法
对于每个点，删除该点判断图的连通性O(V(V+E))
利用深度优先森林
前驱子图的根节点是图的衔接点<=>它在前驱子图中至少有两个子节点
欧拉回路
如果图的每个节点的出度等于入度则存在欧拉回路
如果一个无向图连通图最多只有两个奇点（就是度数为奇数的点），则一定存在欧拉回路
二分图判定
二分图：若能将无向图G=(V,E)的顶点V划分为两个交集为空的顶点集，并且任意边的两个端点都分属于两个集合，则称图G为一个为二分图
二分图判定：染色法

LCA 多个点的最近公共祖先
RMQ区间最值查询

2. 连通无向图的最小生成树

最小生成树：
贪心算法核心是找到一个安全边(u,v)加入到集合A使得 A U {(u,v)} 依然是最小生成树的一个子集
横跨切割的权重最小的边即轻量级边

Kruskal算法：集合A是森林，按权重从低到高考察每条边，如果它将两棵不同的树连接起来就加入到森林A里并完成两棵树的合并
实现：不相交数据结构

MST-Kruskal(G, w)
A = 空集
for each vertex v in G.V
  make-set(v)
sort edges E in G.E in nodecreasing order
for each edge (u,v) in sorted G.E
  if find-set(u) != find-set(v) //否则会形成环
    A.push((u,v))
    union(u,v)
return A

时间复杂度O(ElgV)

Prim算法：集合A是一棵树，每次加入连接集合A和A之外结点的所有边中权重最小的边
实现：优先队列
增加最小生成树的根节点r作为输入
v.key存在v和树中节点的所有边中的最小权重

MST-Prim(G, w, r)
for each vertex v in G.V
  v.key = 无穷
  v.pi = null
r.key = 0
Q = G.V
while Q 不为空
  u = extract-min(Q)
  for each v in G.adj[u]
    if v in Q  and w(u,v) < v.key
        v.pi = u
        v.key = w(u,v)

第一次循环队列中为MST根节点r
建堆总时间O(V)
extract-min时间 $lgV$ 共V次
使用二叉堆 $O(VlgV+ElgV) = O(ElgV)$
使用斐波那契堆 $O(E + VlgV)$ 时间复杂度与迪杰斯特拉算法相同
差别主要在于for循环(E次)中v.key隐含的decrease-key操作在斐波那契堆上的执行成本可以从lgV降为1

3. 最短路径

3.1 问题分析

最短路径具有最优子结构：最短路径的子路径也是最短路
无权重图的最短路径可以直接使用BFS求解，因此本节讨论的图均有权重
最短路径问题可以包含负权重边(例如Bellman-Ford)，但不支持负权重环(不过Bellman-Ford算法可以检测是否存在负权重环)
最短路径必定不包括环路，路径长度至多为|V| - 1
最短路径的表示是以源点s为根节点的一颗最短路径树，由于s到每个可以从s到达的节点的最短路径不唯一，最短路径树不唯一
三角不等式 $\delta(s, v) <= \delta(s, u) + w(v, u)$ $\delta$ 表示两点间最短路径

松弛操作

v.d -- 最短路径估计

Relax(u, v, w)
if v.d > u.d + w(u, v)
  v.d = u.d + w(u, v)    
  v.pi = u

松弛满足
上界性质 $v. d >= \delta(s, v)$
收敛性质一旦 $v.d = \delta(s, v)$ v.d收敛不会再发生变化
非路径性质对于不可达点 $v.d = \infty$

3.2 单源最短路径

Bellman-Ford

每条边松弛|V| -1次（最坏情况下每次循环只松弛了一条边）之后如果存在不满足三角不等式的结点v.d > u.d + w(u,v)说明存在负权重环

时间复杂度O(VE)

Bellman-Ford的改进

改进关键是对松弛顶点的顺序重排序
Yen的改进Ex 21-1
分解图对节点拓扑排序后两图交替松弛

DAG-Shortest-Path

DSP只适用于有向无环图
拓扑排序后按照节点依赖顺序依次对发节点发出的所有边进行松弛
时间复杂度O(V + E)

利用DSP可以求解PERT图的关键路径：

关键路径：
将图中所有权重变为负数，运行DSP 或将松弛操作改为反向操作，初始化对应变为负无穷

Dijkstra

Dijkstra可用于有环图，但不允许存在负权重的边
贪心策略：维护一个已求出最短路径节点的集合S，以v.d为key构造最小堆，每次选择V-S中的最小堆顶，将其加入S并松弛所有与其相邻的边。注意第一次执行循环extract-min得到的是源点s。

Dijkstra(G, w, s)
for each vertex v in G.V
  v.d = 无穷大
  v.pi = null
s.d = 0
Q = G.V
while Q 不为空
  u = extract-min(Q)
  S.push(u)
  for each v in G.adj[u]
    if v.d > u.d + w(u, v)
        v.d = u.d + w(u, v)    
        v.pi = u

时间复杂度

应用

差分约束

将m*n的线性规划矩阵看作是n个节点和m条边构成的图的邻接矩阵的转置
约束图增加节点 $v_0$ 与其他所有节点以权重为0的边连接
约束条件 $x_j - x_i <= b_k$ 转换为 $w(x_i, x_j) = b_k$
约束图的最短路径的解即差分约束系统的解

3.3 多源最短路径

重复平方法

类比矩阵乘法

Floyd

适用负权重边，不允许存在负权重环 O(V^3)
动态规划
递归定义最优解：
中间节点恰好经过k节点 VS 中间节点不包括k节点

Floyd-warshall

利用Floyd求图的传递闭包
有向图的传递闭包：如果存在从i到j的路径则闭包中(i,j)有边相连
每条边权重赋值1，运行Floyd算法，根据中间求解结果是否包含无穷的边来判断 O(n^3)

稀疏图的Johnson算法-Reweight

适用负权重边，调用Bellman-ford可检测负权重环
要满足重新赋值权重后最短路径不变，新增节点s与所有节点相连且w(s,v) = 0，使用Bellman-ford计算 $\delta(s,v)$ ，令 $h(v) = \delta(s,v)$ ，则新权重 $w'(u,v) = w(u,v)+h(u)-h(v)$ 且负权重边均变为正，运行V次Dijkstra算法，最后将最短路径还原即可。
$O(V^2 \lg V+VE)$