2018-09-06

图算法

1. 图
2. 图的搜索
3. 最小生成树
- 3.1. Kruskal 算法
- 3.2. Prim 算法
4. 单源最短路
5. 所有结点对的最短路问题
6. 最大流
7. 参考资料

1. 图

1.1. 概念

顶
顶点的度 d
边
相邻
重边
环
完全图: 所有顶都相邻
二分图: $V(G) = X \cup Y, X\cap Y = \varnothing$, X中, Y 中任两顶不相邻
轨道
圈

1.1.1. 性质

$\sum_{v\in V} d(v) = 2|E|$
G是二分图 $\Leftrightarrow$ G无奇圈
树是无圈连通图
树中, $|E| = |V| -1$

1.2. 图的表示

邻接矩阵
邻接链表

1.3. 树

无圈连通图, $E = V-1$, 详细见树,

2. 图的搜索

Introduction to algorithm¹

2.1. BFS

for v in V:
    v.d = MAX
    v.pre = None
    v.isFind = False
root. isFind = True
root.d = 0
que = [root]
while que !=[]:
    nd = que.pop(0)
    for v in Adj(nd):
        if not v.isFind :
            v.d = nd.d+1
            v.pre = nd
            v.isFind = True
            que.append(v)

时间复杂度 $O(V+E)$

2.2. DFS

$\Theta(V+E)$

def dfs(G):
    time = 0
    for v in V:
        v.pre = None
        v.isFind = False
    for v in V : # note this, 
        if not v.isFind:
            dfsVisit(v)
    def dfsVisit(G,u):
        time =time+1
        u.begin = time
        u.isFind = True
        for v in Adj(u):
            if not v.isFind:
                v.pre = u
                dfsVisit(G,v)
        time +=1
        u.end = time

begin, end 分别是结点的发现时间与完成时间

2.2.1. DFS 的性质

其生成的前驱子图$G_{pre}$ 形成一个由多棵树构成的森林, 这是因为其与 dfsVisit 的递归调用树相对应
括号化结构
括号化定理:
考察两个结点的发现时间与结束时间的区间 [u,begin,u.end] 与 [v.begin,v.end]
- 如果两者没有交集, 则两个结点在两个不同的子树上(递归树)
- 如果 u 的区间包含在 v 的区间, 则 u 是v 的后代

2.3. 拓扑排序

利用 DFS, 结点的完成时间的逆序就是拓扑排序

同一个图可能有不同的拓扑排序

2.4. 强连通分量

在有向图中, 强连通分量中的结点互达
定义 $Grev$ 为 $G$ 中所有边反向后的图

将图分解成强连通分量的算法
在 Grev 上根据 G 中结点的拓扑排序来 dfsVisit, 即

compute Grev
initalization
for v in topo-sort(G.V):
    if not v.isFind: dfsVisit(Grev,v)

然后得到的DFS 森林(也是递归树森林)中每个树就是一个强连通分量

3. 最小生成树

利用了贪心算法,

Generate-Minimum-spanning-tree(G)
    A = []
    while len(A)!=len(G.V)-1:
        add a safe edge for A to A
    return A

3.1. Kruskal 算法

总体上, 从最开始每个结点就是一颗树的森林中(不相交集合, 并查集), 逐渐添加不形成圈的(两个元素不再同一个集合),最小边权的边.

edges=[]
for  edge as u,v in sorted(G.E):
    if find-set(u) != find-set(v):
        edges.append(edge)
        union(u,v)
return edges

如果并查集的实现采用了按秩合并与路径压缩技巧, 则 find 与 union 的时间接近常数
所以时间复杂度在于排序边, 即 $O(ElgE)$, 而 $E\lt V^2$, 所以 $lgE = O(lgV)$, 时间复杂度为 $O(ElgV)$

3.2. Prim 算法

用了 BFS, 类似 Dijkstra 算法
从根结点开始 BFS, 一直保持成一颗树

for v in V: 
    v.minAdjEdge = MAX
    v.pre = None
root.minAdjEdge = 0
que = priority-queue (G.V)  # sort by minAdjEdge
while not que.isempty():
    u = que.extractMin()
    for v in Adj(u):
        if v in que and v.minAdjEdge>w(u,v):
            v.pre = u
            v.minAdjEdge = w(u,v)

建堆 $O(V)$ //note it's v, not vlgv
主循环中
- extractMin: $O(VlgV)$
- in 操作可以另设标志位, 在常数时间完成, 总共 $O(E)$
- 设置结点的 minAdjEdge, 需要$O(lgv)$, 循环 E 次,则总共$O(ElgV)$

综上, 时间复杂度为$O(ElgV)$
如果使用的是斐波那契堆, 在设置 minAdjEdge时调用 decrease-key, 这个操作摊还代价为 $O(1)$, 所以时间复杂度可改进到 $O(E+VlgV)$

4. 单源最短路

求一个结点到其他结点的最短路径, 可以用 Bellman-ford算法, 或者 Dijkstra算法.
定义两个结点u,v间的最短路

$\delta(u,v) = \begin{cases} \min(w(path)),\quad u\xrightarrow{path} v\\ \infty, \quad u\nrightarrow v \end{cases}$

问题的变体

单目的地最短路问题: 可以将所有边反向转换成求单源最短路问题
单结点对的最短路径
所有结点对最短路路径

4.1. 最短路的子路径也是最短路径

$p=(v_0,v_1,\ldots,v_k)$为从结点$v_0$到$v_k$的一条最短路径, 对于任意$0\le i\le j \le k$, 记$p_{ij}=(v_i,v_{i+1},\ldots,v_j)$为 p 中 $v_i$到$v_j$的子路径, 则 $p_{ij}$为 $v_i$到$v_j$的一条最短路径

4.2. 负权重的边

Dijkstra 算法不能处理负值边, 只能用 Bellman-Ford 算法,
而且如果有负值圈, 则没有最短路, bellman-ford算法也可以检测出来

4.3. 初始化

def initialaize(G,s):
    for v in G.V:
        v.pre = None
        v.distance = MAX
    s.distance = 0

4.4. 松弛操作

def relax(u,v,w):
    if v.distance > u.distance + w:
        v.distance = u.distance + w:
         v.pre = u

性质

三角不等式: $\delta(s,v) \leqslant \delta(s,u) + w(u,v)$
上界: $v.distance \geqslant \delta(s,v)$
收敛: 对于某些结点u,v 如果s->…->u->v是图G中的一条最短路径，并且在对边，进行松弛前任意时间有 $u.distance=\delta(s,u)$则在之后的所有时间有 $v.distance=\delta(s,v)$
路径松弛性质: 如果$p=v_0 v_1 \ldots v_k$是从源结点下v0到结点vk的一条最短路径，并且对p中的边所进行松弛的次序为$(v_0,v_1),(v_1,v_2), \ldots ,(v_{k-1},v_k)$, 则 $v_k.distance = \delta(s,v_k)$
该性质的成立与任何其他的松弛操作无关，即使这些松弛操作是与对p上的边所进行的松弛操作穿插进行的。

证明
graph-3

4.5. 有向无环图的单源最短路问题

$\Theta(V+E)$

def dag-shortest-path(G,s):
    initialize(G,s)
    for u in topo-sort(G.V):
        for v in Adj(v):
            relax(u,v,w(u,v))

4.6. Bellman-Ford 算法

$O(VE)$

def bellman-ford(G,s):
    initialize(G,s)
    for ct in range(|V|-1): # v-1 times
        for u,v as edge in E:
            relax(u,v,w(u,v))
    for u,v as edge in E:
        if v.distance > u.distance + w(u,v):
            return False
    return True

第一个 for 循环就是进行松弛操作, 最后结果已经存储在结点的distance 和 pre 属性中了, 第二个 for 循环利用三角不等式检查有不有负值圈.

下面是证明该算法的正确性 graph-4

4.7. Dijkstra 算法

$O(ElogV)$, 要求不能有负值边

Dijkstra算法既类似于广度优先搜索（，也有点类似于计算最小生成树的Prim算法。它与广度优先搜索的类似点在于集合S对应的是广度优先搜索中的黑色结点集合：正如集合S中的结点的最短路径权重已经计算出来一样，在广度优先搜索中，黑色结点的正确的广度优先距离也已经计算出来。Dijkstra算法像Prim算法的地方是，两个算法都使用最小优先队列来寻找给定集合（Dijkstra算法中的S集合与Prim算法中逐步增长的树）之外的“最轻”结点，将该结点加入到集合里，并对位于集合外面的结点的权重进行相应调整。

def dijkstra(G,s):
    initialize(G,s)
    paths=[]
    q = priority-queue(G.V) # sort by distance
    while not q.empty():
        u = q.extract-min()
        paths.append(u)
        for v in Adj(u):
            relax(u,v,w(u,v))

5. 所有结点对的最短路问题

5.1. 矩阵乘法

使用动态规划算法, 可以得到最短路径的结构
设 $l_{ij}^{(m)}$为从结点i 到结点 j 的至多包含 m 条边的任意路径的最小权重,当m = 0, 此时i=j, 则为0,
可以得到递归定义

$l_{ij}^{(m)} =\min( l_{ij}^{(m-1)}, \min_{1\leqslant k\leqslant n}( l_{ik}^{(m-1)}+w_{kj})) = \min_{1\leqslant k\leqslant n}( l_{ik}^{(m-1)}+w_{kj}))$

由于对于所有 j, 有 $w_{jj}=0$,所以上式后面的等式成立.

由于是简单路径, 则包含的边最多为 |V|-1 条, 所以

$\delta(i,j) = l_{ij}^{(|V|-1)} = l_{ij}^{(|V|)} =l_{ij}^{(|V| + 1)}= ...$

所以可以从自底向上计算, 如下
输入权值矩阵 $W(w_{ij})), L^{(m-1)}$,输出$ L^{(m)}$, 其中 $L^{(1)} = W$,

def  f(L, W):
  n = L.rows
  L_new = new matrix(row=n ,col = n)
  for i in range(n):
      for j in range(n):
          L_new[i][j] = MAX
          for k in range(n):
              L_new[i][j] = min(L_new[i][j], L[i][k]+w[k][j])
  return L_new

可以看出该算法与矩阵乘法的关系
$L^{(m)} = W^m$,
所以可以直接计算乘法, 每次计算一个乘积是 $O(V^3)$, 计算 V 次, 所以总体 $O(V^4)$, 使用矩阵快速幂可以将时间复杂度降低为$O(V^3lgV)$

def f(W):
    L = W
    i = 1
    while i<W.rows:
        L = L*L
        i*=2
    return L

5.2. Floyd-Warshall 算法

同样要求可以存在负权边, 但不能有负值圈. 用动态规划算法:
设 $ d_{ij}^{(k)}$ 为从 i 到 j 所有中间结点来自集合 ${\{1,2,\ldots,k\}}$ 的一条最短路径的权重. 则有

$d_{ij}^{(k)} = \begin{cases} w_{ij},\quad k=0\\ min(d_{ij}^{(k-1)},d_{ik}^{(k-1)}+d_{kj}^{(k-1)}),\quad k\geqslant 1 \end{cases}$

而且为了找出路径, 需要记录前驱结点, 定义如下前驱矩阵 $\Pi$, 设 $ \pi_{ij}^{(k)}$ 为从 i 到 j 所有中间结点来自集合 ${\{1,2,\ldots,k\}}$ 的最短路径上 j 的前驱结点
则

$\pi_{ij}^{(0)} = \begin{cases} nil,\quad i=j \ or \ w_{ij}=\infty \\ i, \quad i\neq j\ and \ w_{ij}<\infty \end{cases}$

对 $k\geqslant 1$

$\pi_{ij}^{(k)} = \begin{cases} \pi_{ij}^{(k-1)} ,\quad d_{ij}^{(k-1)}\leqslant d_{ik}^{(k-1)}+d_{kj}^{(k-1)}\\ \pi_{kj}^{(k-1)} ,\quad otherwise \end{cases}$

由此得出此算法

def floyd-warshall(W):
    n = len(W)
    D= W
    initialize pre
    for k in range(n):
        pre2 = pre.copy()
        for i in range(n):
            for j in range(n)
                if d[i][j] > d[i][k]+d[k][j]:
                    d[i][j] =d[i][k]+d[k][j]
                    pre2[i][j] = pre[k][j]
        pre = pre2
return d,pre

5.3. Johnson 算法

思路是通过重新赋予权重, 将图中负权边转换为正权,然后就可以用 dijkstra 算法(要求是正值边)来计算一个结点到其他所有结点的, 然后对所有结点用dijkstra

首先构造一个新图 G’
先将G拷贝到G’, 再添加一个新结点 s, 添加 G.V条边, s 到G中顶点的, 权赋值为 0
用 Bellman-Ford 算法检查是否有负值圈, 如果没有, 同时求出 $\delta(s,v) 记为 h(v)$
求新的非负值权, w’(u,v) = w(u,v)+h(u)-h(v)
对所有结点在新的权矩阵w’上用 Dijkstra 算法

JOHNSON (G, u) 

s = newNode
G' = G.copy()
G'.addNode(s)
for v in G.V: G'.addArc(s,v,w=0)

if BELLMAN-FORD(G' , w, s) ==FALSE 
    error "the input graph contains a negative-weight cycle" 

for v in G'.V:
    # computed by the bellman-ford algorithm, delta(s,v) is the shortest distance from s to v
    h(v) = delta(s,v) 
for edge(u,v) in G'.E:
    w' = w(u,v)+h(u)-h(v)
d = matrix(n,n)
for u in G:
    dijkstra(G,w',u) # compute delta' for all v in G.V
    for v in G.V:
        d[u][v] = delta'(u,v) + h(v)-h(u)
return d

6. 最大流

G 是弱连通严格有向加权图, s为源, t 为汇, 每条边e容量 c(e), 由此定义了网络N(G,s,t,c(e)),

流函数 $f(e):E \rightarrow R$ $\begin{aligned} (1)\quad & 0\leqslant f(e) \leqslant c(e),\quad e \in E\\ (2)\quad & \sum_{e\in \alpha(v)} f(e)= \sum_{e\in \beta(v)}f(e),\quad v \in V-\{s,t\} \end{aligned}$ 其中 $\alpha(v)$ 是以 v 为头的边集, $\beta(v)$是以 v 为尾的边集
流量: $F = \sum_{e\in \alpha(t)} f(e)- \sum_{e\in -\beta(t)}f(e),$
截$(S,\overline S)$: $S\subset V,s\in S, t\in \overline S =V-S$
截量$C(S) = \sum_{e\in(S,\overline S)}c(e)$
6.1. 最大流最小截定理
<<图论>> 王树禾²
对于任一截$(S,\overline S)$, 有 $F = \sum_{e\in (S,\overline S)} f(e)- \sum_{e\in(\overline S,S)}f(e),$
$F\leqslant C(S)$
证明: 由上面定理 $F = \sum_{e\in (S,\overline S)} f(e)- \sum_{e\in(\overline S,S)}f(e),$ 而 $0\leqslant f(e) \leqslant c(e)$, 则 $F\leqslant \sum_{e\in (S,\overline S)} f(e) \leqslant \sum_{e\in (S,\overline S)} c(e) = C(S)$
最大流,最小截: 若$F= C(S) $, 则F’是最大流量, C(S) 是最小截量
6.2. 多个源,汇
可以新增一个总的源,一个总的汇,

6.3. Ford-Fulkerson 方法

由于其实现可以有不同的运行时间, 所以称其为方法, 而不是算法.
思路是循环增加流的值, 在一个关联的”残存网络” 中寻找一条”增广路径”, 然后对这些边进行修改流量. 重复直至残存网络上不再存在增高路径为止.

def ford-fulkerson(G,s,t):
    initialize flow f to 0
    while exists an augmenting path p in residual network Gf:
        augment flow f along p
    return f

6.3.1. 残存网络

graph-7

6.3.2. 增广路径

graph-8

6.3.3. 割

graph-9

6.4. 基本的 Ford-Fulkerson算法

def ford-fulkerson(G,s,t):
    for edge in G.E: edge.f = 0
    while exists path p:s->t  in Gf:
        cf(p) = min{cf(u,v):(u,v) is in p}
        for edge in p:
            if edge  in E:
                edge.f +=cf(p)
            else: reverse_edge.f -=cf(p)

6.5. TBD

7. 参考资料

¹. 算法导论 ↩

². 图论, 王树禾 ↩

本文标题:图算法

文章作者:mbinary

发布时间:2018-09-06, 19:10:00

最后更新:2021-04-23, 08:02:23

原始链接:https://mbinary.xyz/graph.html

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。