chap22 基本的图算法

广度优先搜索 深度优先搜索 拓扑排序 强连通分量 算法导论

内容

图的表示

1. 邻接矩阵，数组的优点，快速查找，适用于稠密图
2. 邻接链表，适用于稀疏图

广度优先搜索 Breadth-first search

1. 适用于无向图和有向图，边的权重为单位值或者都相等。
2. 基本思路：给定图和一个源结点s，从s出发依次寻找距离为k的结点，当找到所有距离为k的结点后，再继续寻找距离为k+1的结点。
3. 技巧：使用颜色来区分结点是否被发现，白色表示未被发现，黑色和灰色表示被发现，所有与黑色结点相邻的结点都已被发现，所有与灰色结点相邻的结点中可能存在白色结点（黑色和灰色可以不进行区分）
4. 算法输出，一棵以s为结点的广度优先搜索树，包含所有s可以达到的结点，并且从s到达某个结点的简单路径就是最短路径。
5. 注意的地方：每个结点因为颜色的标注，会且只会被发现1次，因而产生的数中结点是不会重复的；另外扫描的顺序会影响树的形状，但不会影响最终各个结点的d属性
6. 假设： 对应1，边的权重为1；以邻接链表来表示
7. 时间复杂度$O(V+E)$：初始化V步，队列至多操作V次，扫描至多E次

BFS(G,s)————$O(V+E)$

for each vertex u in G.V -{s}
    u.color = white
    u.d = 00            #s到u的距离
    u.p = nil           #u的前驱
s.color = gray
s.d = 0
s.p = nil
Q = empty queue
enqueue(Q,s)
while Q is not empty
    u = dequeue(Q)
    for each v in G.adj[u]
        if v.color == white
            v.color = gray
            v.d = u.d + 1
            v.p = u
            enqueue(Q,v)
    u.color = black

深度优先搜索 Depth-first search

1. 适用于无向图和有向图
2. 基本思路：给定图，算法选择一个结点作为源结点，与bfs不同的是，此处采取的是一种类似于分支模式处理问题的方式，即沿一条路走到底，再往上回溯；另外，该算法不会只满足一个源结点，它要求穷尽所有结点，因而h会产生对个源结点，从而产生多棵树（注意bfs是能而不为）
3. 技巧：除使用颜色外，还使用时间戳来进行标记，作用在于为了进行回溯；直观地说结点的时间区间包含于父结点的时间区间，而兄弟结点时间区间是不相交的
4. 算法输出，多棵深度优先树构成的深度优先森林，各棵树不想交
5. 注意的地方：与bfs不同，这里d和f属性表示发现和完成时间，另外，深度优先树给出的是路径，而不是最短路径
6. 假设：以邻接链表来表示
7. 时间复杂度$\Theta(V+E)$：初始化V步，扫描结点至多V次，扫描边E次

DFS(G)

for each vertex u in G.V
    u.color = white
    u.p = nil   
time = 0
for each u in G.V
    if u.color == white
        DFT-visit(G,u)

DFT-visit(G,u)

time = time + 1
u.d = time
u.color = gray
for each v in G.adj[u]
    if v.color == white
        v.p = u
        DFT-visit(G,v)
u.color = black
time = time + 1
u.f = time

深度优先搜索的性质

1. 结点的发现时间和完成时间具有所谓的括号化结构，即不同结点之间要么完全包含，要么完全分离。前者两个结点一个是另一个的后代，后者两个节点不具备这种关系
2. 白色路径定理，在深度优先森林中，如果v是u的后代当且仅当在在发现u时，存在一条u到v的纯白路径

3. 边的分类

   • 树边：结点v是因算法对边（u，v）探索而首次被发现，则（u，v）是树边
   • 后向边： 后向边（u，v）是将u连接到其祖先结点v的边，比如有向图的自循环就是后向边
   • 前向边： 将结点u连接到其后代结点v的边
   • 横向边： 除此之外的其他边

4. DFS会产生对边进行分类的信息，对于边（u，v）

   • 结点v是白色——树边
   • 结点v是灰色——后向边
   • 结点v是黑色——前向边或后向边

5. 对于无向图G，在对无向图进行深度优先搜索中，从来不会出现前向边和横向边。启发式证明，至所以有向图会出现这两种边，在于边是有方向的，从u不能到v但反之可以，从而使得从v探索到u时，u已经被发现

拓扑排序

1. 对于有向无环图G=(V,E)，拓扑排序就是对所有结点的一种线性排序，满足：如果图G包含边（u，v），则结点u再拓扑排序中处于结点v的前面（因而要求有向无环）
2. 此处使用深度优先搜索来对有向图进行拓扑排序
3. 引理22.11一个有向图是无环的当且仅当对其进行深度优先搜索不产生后向边。
4. 时间复杂度$\Theta(V+E)$

topological-sort(G)

call dfs(G) to compite finishing time v.f for each vertex v
as each vertex is finished, insert in onto the front of the linked list
return the linked list

强连通分量

1. 有向图$G=(V,E)$的强连通分量是一个最大结点集合$C \subseteq V$ ，对于该集合中的任意一对结点u和v来说，路径u~v和v~u同时存在
2. 使用深度优先搜素来将图分解成强连通分量，说白了就是寻找图中的环
3. 需要用到图的转置
4. 证明：
5. 时间复杂度$\Theta(V+E)$

strongly-connected-components(G)

call dfs(G) to compute finishing time u.f for each vertex u
compute G.transvertion
call dfs(G^T), but in the main loop of dfs,consider the
    vertices in order of decreasing u.f
output the vertices of each tree in the df forest formed in the
    second call of dfs as a seperate strongly connected component

习题

to be continued

代码实现