简单介绍图及其相关算法。


什么是图

定义 一个图 $G = (V, E)$ 由顶点(或结点)的非空集 $V$ 和边的集合 $E$ 构成,每条边有一个或两个顶点与它相连,这样的顶点称为边的端点。边连接它的端点。

图的表示

  • 邻接链表:稀疏图
  • 邻接矩阵:稠密图,或者需要快速判断任意两个结点之间是否有边的情况

图的表示

广度优先搜索

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/** u.color 存放结点 u 的颜色属性
  *         白色表示未被发现
  *         灰色表示邻接结点中还有白色结点
  *         黑色表示邻接结点均被发现
  * u.π 存放前驱结点
  * u.d 存放从源结点 s 到结点 u 之间的距离
  **/
BFS(G, s)
        for each vertex u in G.V - {s}
                u.color = WHITE
                u.d = 
                u.π = NIL
        s.color = BLACK
        s.d = 0
        s.π = NIL
        Q = 
        ENQUEUE(Q, s)
        while Q    // 灰色结点的集合
                u = DEQUEUE(Q)
                for each v in G.Adj[u]
                        if v.color == WHITE
                                v.color = GRAY
                                v.d = u.d + 1
                                v.π = u
                                ENQUEUE(Q, v)
                u.color = BLACK

BFS 的总运行时间为 O(V + E)

BFS

BFS 的性质

  1. BFS 可以计算出从源结点 s 到 结点 v 的最短路径。
  2. BFS 在对图进行搜索的过程中将创建一棵广度优先树

深度优先搜索

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/** u.color 存放结点 u 的颜色属性
  *         白色表示未被发现
  *         灰色表示邻接结点中还有白色结点
  *         黑色表示邻接结点均被发现
  * u.π 存放前驱结点
  * u.d 记录结点 u 第一次被发现的时间
  * u.f 记录搜索完成对 u 的邻接链表扫描的事件
  **/
DFS(G)
        for each vertex u in G.V
                u.color = WHITE
                u.π = NIL
        time = 0
        for each vertex u in G.V
                if u.color == WHITE
                        DFS-VISIT(G, u)

DFS-VISIT(G, u)
        time = time + 1 // white vertex u has just been discovered
        u.d = time
        u.color = GRAY
        for each v in G.Adj[u] // explore edge (u, v)
                if v.color == WHITE
                        v.π = u
                        DFS-VISIT(G, v)
        u.color = BLACK  // blacken u, it is finished
        time = time + 1
        u.f = time

DFS 的总运行时间为 O(V + E)

DFS

DFS 的性质

  1. 括号化定理:在对有向或无向图进行的任意 DFS 中,对于任意两个结点 u 和 v 来说,下面三种情况只有一种成立:

    • 区间 $[u.d, u.f]$ 和 区间 $[v.d, v.f$ 完全分离,在深度优先森林中,结点 u 不是结点 v 的后代,结点 v 也不是结点 u 的后代
    • 区间 $[u.d, u.f]$ 完全包含在 区间 $[v.d, v.f$ 内,在深度优先树中,结点 u 是结点 v 的后代
    • 区间 $[v.d, v.f]$ 完全包含在 区间 $[u.d, u.f$ 内,在深度优先树中,结点 v 是结点 u 的后代
  2. 边的分类

    • 树边:是深度优先森林 $G_π$ 中的边。如果结点 v 是因算法对边 (u, v) 的探索而首先被发现,则 (u, v) 是一条树边
    • 后向边:是将结点 u 连接到其在深度优先树中祖先结点 v 的边。由于有向图中可以有自循环,自循环也被认为是后向边
    • 前向边:是将结点 u 连接到其在深度优先树中后代结点 v 的边
    • 横向边:其他所有的边

在对无向图 G 进行深度优先搜索时,每条边要么是树边,要么是后向边。

拓扑排序

对于一个有向无环图 G(V, E) 来说,其拓扑排序是 G 中所有结点的一种线性次序,该次序满足如下条件:如果图 G 包含边 (u, v),则结点 u 在拓扑排序中处于结点 v 的前面。

拓扑排序

1
2
3
4
TOPOLOGICAL-SORT(G)
    call DFS(G) to compute finishing time v.f for each vertex v
    as each vertex is finished, insert it onto the front of a linked list
    return the linked of list of vertices

强连通分量

定义: 如果一个有向图中任意两个顶点互相可达,则该有向图是强连通的。 图 G 的转置 $G^T = (V, E^T)$,其中 $E^T = {(u, v): (u, v) \in E}$。

1
2
3
4
5
6
7
STRONGLY-CONNECTED-COMPONENTS(G)
    call DFS(G) to compute finishing time u.f for each vertex u
    compute G^T
    call DFS(G^T), but in the main loop of DFS, consider the vertices
            in order of decreasing u.f (as computed in line 1)
    output the vertices of each tree in the depth-first forest formed
            in line 3 as a separate strongly connected component

强连通分量

最小生成树

定义: 连通加权图里的最小生成树是具有边的权值之和最小的生成树。

1
2
3
4
5
6
7
8
// 在每遍循环之前,A 是某棵最小生成树的一个子集
// 加入集合 A 而不会破坏 A 的循环不变式的边称为集合 A 的安全边
GENERIC-MST(G, w)
    A = 
    while A does not form a spanning tree
            find an edge(u, v) that is safe for A
            A = A  {(u, v)}
    return A

定理: 设 G = (V, E) 是一个在边 E 上定义了实数值权重函数 w 的连通无向图。设集合 A 为 E 的一个子集,且 A 包括在图 G 的某棵最小生成树中,设 (S, V - S) 是图 G 中尊重集合 A 的任意一个切割(集合 A 中不存在横跨该切割的边),又设 (u, v) 是横跨切割 (S, V - S) 的一条轻边。那么边 (u, v) 对于集合 A 是安全的。

Kruskal 算法

在 Kurskal 算法中,集合 A 是一个森林,其结点就是给定图的结点。每次加入集合 A 中的安全边永远是权重最小的连接两个不同分量的边。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
MST-KRUSKAL(G, w)
    A = 
    for each vertex v in G.V
            MAKE-SET(v)
    sort the edge of G.E into nondecreasing order by weight w
    for each edge (u, v) in G.E, taken in nondecreasing order by weight
        if FIND-SET(u)  FIND-SET(v)
            A = A  {(u, v)}
            UNION(u, v)
    return A

Kruskal 算法的时间复杂度为 $O(ElgV)$。

Kruskal 算法

Prim 算法

在 Prim 算法里,集合 A 则是一棵树。这棵树从一个任意的根结点 r 开始,一直长大到覆盖 V 中的所有结点时为止。每次加入到 A 中的安全边永远是连接 A 和 A 之外某个结点的边中权重最小的边。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
MST-PRIM(G, w, r)
    for each u in G.V
        u.key = 
        u.π = NIL
    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.π = u
                v.key = w(u, v)

如果使用二叉最小优先队列来实现最小优先队列 Q,时间复杂度为 $O(ElgV)$; 如果使用斐波那契堆来实现最小优先队列 Q,则 Prim 算法的运行时间将改进到 $O(E + VlgV)$

Prim算法

单源最短路径

  1. 最短路径的子路径也是最短路径
  2. 如果从结点 s 到结点 v 的某条路径上存在权重为负值的环路,我们定义 $\delta(s, v) = -\infty$
  3. 一般地,我们假定在找到的最短路径中没有环路,即它们都是简单路径。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
/** 初始化
  * v.d:s 到 v 的最短路径估计
  * v.π:前驱结点 */
INITIALIZE-SINGLE-SOURCE(G, s)
    for each vertex v in G.V
        v.d = 
        v.π = NIL
    s.d = 0

// 松弛操作
RELAX(u, v, w)
    if v.d > u.d + w(u, v)
        v.d = u.d + w(u, v)
        v.π = u

Dijkstra 算法和用于有向无环图的最短路径算法对每条边仅松弛一次。 Bellman-Ford 算法则对每条边松弛 |V| - 1 次。

Bellman-Ford 算法

Bellman-Ford 算法解决的是一般情况下的最短路径问题。该算法返回 TRUE 值当且仅当输入图不包含可以从源结点到达的权重为负值的环路。

1
2
3
4
5
6
7
8
9
BELLMAN-FORD(G, w, s)
    INITIALIZE-SINGLE-SOURCE(G, s)
    for i = 1 to |G.V|-1
        for each edge (u, v) in G.E
            RELAX(u, v, w)
    for each edge (u, v) in G.E
            if v.d > u.d + w(u, v)
                return FALSE
    return TRUE

Bellman-Ford 算法的总运行时间为 O(VE)

Bellman-Ford 算法

有向无环图中的单源最短路径问题

根据结点的拓扑排序次序来对带权重的有向无环图 G = (V, E) 进行边的松弛操作,我们便可以在 $O(V + E)$ 时间内计算出从单个源结点到所有结点之间的最短路径。

1
2
3
4
5
6
DAG-SHOPTEST-PATHS(G, w, s)
    topologically sort the vertice of G
    INITIALIZE-SINGLE-SOURCE(G, s)
    for each vertex u, taken in topologically sorted order
        for each vertex v in G.Adj[u]
            RELAX(u, v, w)

DAG

Dijkstra 算法

Dijkstra 算法解决的是带权重的有向图上的单源最短路径问题,该算法要求所有边的权重都为非负值。

1
2
3
4
5
6
7
8
9
DIJKSTRA(G, w, s)
    INITIALIZE-SINGLE-SOURCE(G, s)
    S = 
    Q = G.V
    while Q  
        u = EXTRACT-MIN(Q)
        S = S  {u}
        for each vertex v in G.Adj[u]
            RELAX(u, v, w)

如果使用二叉最小优先队列来实现最小优先队列 Q,时间复杂度为 $O(ElgV)$; 如果使用斐波那契堆来实现最小优先队列 Q,则 Dijkstra 算法的运行时间将改进到 $O(E + VlgV)$

Dijsktra算法