图的应用1

对于两种搜索方法，广度优先搜索和深度优先搜索，广度优先搜索的应用主要是最短路径；深度优先搜索应用就比较广泛：

• 图的环路存在性判定(Circuit Judgement)
• 拓扑排序(Topological Sort)
• 强连通分量(Strong Connected Components)

图的环路存在性判定

图可以分为有向图和无向图。

有向图的环路存在性判定

如何判定出现环路：在深度优先搜索中出现了后向边（从后代指向祖先的边）。

输入：有向图$G=$，$V$是顶点集合，$E$是边集。

输出：图中是否存在环路。

$DFS_Judge_Circuit(G)$

1
2
3
4
5
6
7
8
9

//初始化
for v ∈ V do
    color[v] = White
    prev[v] = NULL
for v ∈ V do
    if color[v] == White then
        if DFS_Visit_Judge_Circuit(G,v) then
            return True
return False

递归函数$DFS_Visit_Judge_Circuit(G,v)$

1
2
3
4
5
6
7
8
9
10
11

color[v] = Gray //开始访问顶点v，尚未访问完
for u ∈ G.Adj(v) do
    if color[u] == Gray then 
        //正在访问顶点u，如果是黑色顶点，代表不在一条路上，是前顶点分叉的顶点
        return True
    if color[u] == White then
        pred[u] = v
        if DFS_Visit_Judge_Circuit(G,u) then
            return True
color[v] = Black
return False

在邻接表存储的图中的算法时间复杂度是$O(|V|+|E|)$。

拓扑排序

什么是拓扑？在图论中，拓扑可以指图的某种排列或结构，特别是有向图(Directed Graph)中的顶点关系。

有向无环图(Directed Acyclic Graph, DAG)：表示事件发生的先后顺序。
拓扑排序是针对有向无环图（DAG, Directed Acyclic Graph）的一种排序方式。它将图中的所有节点排列成一个线性序列，使得对于每一条有向边$v\rightarrow u$，顶点$v$在序列中出现在顶点$u$之前。这种排序方式在许多应用中非常有用，比如任务调度、课程安排等。

有向图的顶点分为入度和出度。若顶点入度为0，则说明该顶点所对应事件无制约，可直接完成。

算法步骤：

1. 完成入度为0的顶点的事件，并加入拓扑序列。
2. 删除该顶点，产生新的入度为0的顶点，继续完成，直到图中没有其他点存在。

辅助数组：

1. 当前保存入度为0的顶点的队列。
2. 拓扑序列。

拓扑排序算法

输入：有向图$G=$。

输出：图顶点$V$的拓扑排序的序列$S$，对任意有向边$v\rightarrow u$，拓扑序列中$v$在$u$之前。

$Topological_Sort_BFS(G)$

拓扑排序算法可以使用广度优先搜索思想。

1
2
3
4
5
6
7
8
9
10
11
12

//初始化入度为0的顶点队列
for v ∈ V do
    if v.in_degree == 0 then
        Q.Enqueue(v) //将顶点v加入队列
while !Q.not_empty() do
    u = Q.Dequeue() //取队首元素
    topo_list.add(u) //将顶点添加到拓扑序列中
    for v ∈ G.Adj(u) do
        v.in_degree = v.in_degree - 1
        if v.in_degree == 0:
            Q.Enqueue(v)
return topo_list

$Topological_Sort_DFS(G)$

拓扑排序算法可以使用深度优先搜索思想，通过顶点的完成时间序列$finish[|V|]$实现。顶点$v$的完成操作在$DFS_Visit(G,v)$递归函数的$return$操作前。

• $DFS(G)$

  1 2 3 4 5 6

  for v ∈ V do color[v] = White for v ∈ V do if color[v] == White then topo_list = topo_list + DFS_Visit(G,v) return topo_list.reverse()

• $DFS_Visit(G,v)$

  1 2 3 4 5 6 7

  color[v] = Gray //顶点被找到，但是还没完成 for u ∈ G.Adj(v) do if color[u] == White then L = L + DFS_Visit(G,u) color[v] = Black //该顶点已经完成 L = L + [v] return L

  强连通分量

  可以将图划分为几个强连通分量。
  强连通分量中的任意两个顶点都相互可达，并且加入新的顶点后，不保证相互可达。

输入：有向图$G=$。

输出：图的所有强连通分量$C_1,C_2,…,C_n$。

算法步骤：

1. 将图中的所有边都反向，得到反向图$G^{Reverse}$。
2. 在$G^{Reverse}$上执行深度优先搜索算法(DFS)，得到顶点完成时刻序列$L$。
3. 在$G$上按$L$逆序执行DFS，得到强连通分量。

$Strongly_Connected_Component(G)$

1
2
3
4
5
6
7
8
9
10

G_Reverse = G.reverse() //将图中的所有边反向，得到反向图G_Reverse
L_Reverse = DFS(G_Reverse) //获取反向图的完成时间序列
for v ∈ V do
    color[v] = White
for (i = L_Reverse.length()-1;i >= 0; i--) do
    v = L_Reverse[i]
    if color[v] == White then
        current_scc = DFS_Visit(G,v) //获得当前的强连通分量
        set_scc.add(current_scc) //将该强连通分量加入到结果集合中
return R

$DFS_Finish_List(G.v)$

1
2
3
4
5
6
7
8

color[v] = Gray
for u ∈ G.Adj(v) do
    if color[u] == White then
        L = L + DFS_Visit(u)

color[v] = Black
L = L + [v]
return L

$DFS(G,v)$

1
2
3
4
5
6
7
8

color[v] = Gray
for u ∈ G.Adj(v) do
    if color[u] == White then
        L + L + DFS_Visit(u)

color[v] = Black
L = L + [v]
return L

• ← Previous Post
• Next Post →