Bread-First-Search and Depth-First-Search
Algorithm BFS DFS Graph
CodingBetter
Publish Date:   2019-04-30
Word Count:   1.7k
Read Times:   7 Min
Read Count:  

Graph

一般图算法的输入：|V| 和 |E| （G = (V, E)）
图的表示：

  • 链表：多用于稀疏图，即|E|远小于|V|^2。对于有向图来说，所有链表长度和为|E|；对于无向图来说，所有链表长度和为2|E|。链表占用空间O(V+E)。链表无法快速判断有无包含一条edge，因此我们引入矩阵。
  • 矩阵：多用于稠密图，即即|E|接近|V|^2。矩阵占用空间O(V^2)。无向图可以只存对角线以上部分，因而减少储存空间。

深度优先搜索会尽可能的深入，总是从最近发现的结点v的出发边进行探索，直到该结点所有出发边都被发现为止。一旦所有出发边都被发现，则回溯到v的前驱结点u，搜索该结点的所有出发边。此过程一直重复，知道所有可到达结点都被到达。如果图中仍有未发现结点，随机挑选另一source vertex进行探索，直到图中没有任何未发现结点。深度优先算法将生成深度优先森林。
初始结点是白色，被发现后变为灰色，邻接链表被扫描完成变为黑色。此方法保证每个结点只会在深度优先树中出现一次。
深度优先的特殊属性：时间戳（Time Stamp）v.d 记录结点第一次发现的时间（变灰的时间），v.f记录结点扫描完成的时间（变黑的时间），对于每一个结点我们有：v.f > v.d

DFS(G)
for each vertex u ∈ G.V
    u.color = White
    u.pi = Nil
time = 0

for each vertex v ∈ G.V
    if v.color = White
        DFS-VISIT(G, v)

DFS-VISIT(G, v)
time = time + 1
v.d = time
v.color = Gray
for each u ∈ G.adj(v)
    if u.color = White
        u.pi = v
        GFS-VISIT(G, u)
v.color = Black
time = time + 1
v.f = time

O(V + E)
深度优先的性质（properties）

  • 图结构：其生成的前驱子图G‘形成一个深度森林（深度优先树的结构与DFS-VISIT的调用结构完全相似，只有v在链表中被发现的适合，u才成为v的前驱（在u为灰色时间段里发现））
  • 发现时间和完成时间具有括号化结构（parenthesis structure），左括号是发现时间，右括号是结束时间。well-formed expression
  • Parenthesis Theorem:
    • [u.d, u.f] and [v.d, v.f] are entirely disjoint, and neither u nor v is a descendant of the other
    • [u.d, u.f] is contained entirely within the [v.d, v.f], u is a descendant of v
    • [v.d, v.f] is contained entirely within the [u.d, u.f], v is a descendant of u
  • White - Path Theorem: vertex u 是 vertex v的后代，当且仅当v被发现的时候，有一条从v到u都是白色结点的路径

Topological Sort

G中所有结点的线性次序，如果G包含边（u, v），则结点u在拓扑排序中处于结点v的前面（必须无环），因为u有一条边指向v，则u的结束时间一定比v晚，u的次序也一定比v前

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

O(V + E), 因为DFS需要此时间完成。插入linkedlist时间是O(1*V)
Correctness：

  • 一个有向图（directed graph）是无环(acyclic graph)的当且仅当对其进行深度搜索不产生后向边
  • 拓扑排序生成的是有向无环图的拓扑排序 - 所以有向无环图一定可以生成一个现行次序

Strong Connected Components

DFS can decompose a directed graph into its strongly connected components. (By two DFS) SCC will be start states for many graph algorithms. Strong Connected Components (SCC) of a directed graph G is a maximal set of vertices C ⊆ V such that for every pair of vertices u and v in C, we have both u -> v and v -> u (u and v are reachable from each other).
G and the transpose of G share the same SCC. 强连通分量可以收缩成一个结点（用一个结点替换整个连通分量），这样的浓缩分量图G’是无环的。

To find SCC:
Use the transpose of G. G’ = (V, E’), where E’ contains the edges of G with their directions reversed. Time to create G’: O(V + E).

SCC(G)
call DFS(G) to compute finishing times 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) 'Visit the G^T in the topological sort order'
output the vertices of each tree in the depth-first forest formed in line 3 as a separate strongly connected component

Propoerty:

  • Component Graph GSCC 将SCC的所有结点收缩到一起，构建出GSCC分量图
  • 如果C和C’是有向图G的两个不同SCC，假设C有u和v，C‘有u’和v‘，如果G包含一条从u到u’的路径，按么G不可能包含另一条从v到v‘的路径（因为u和v，u‘和v’是互通的）
  • 因为按照Topological sort order进行第二次DFS，因此我们可以推广时间的概念到SCC上。对于每一个SCC，定义d是最早发现的时间，即min(u.d)，f是最晚完成的时间，即max(u.f)。C和C‘是G的两个SCC，如果存在一条边(u,v)从C到C‘，则f(C) > f(C’). 如果(u,v）存在于transpose G中，我们有f(C) < f(C’) (路径是从C’到C的)

输入：G(V,E) and s

  • 以s为根结点，找寻所有可以从s到达的结点

  • 计算s与其可到达节点的距离

  • 输出广度优先树
  • 广度优先树在未探索距离s为k距离的结点之前，一定不会探索（k+1）距离的结点。
  • 广度：沿着已发现结点和未发现结点的边界向外探索（广）
  • Q管理的是所有灰色结点。灰色和黑色都是已经发现的结点，唯一的不同是，灰色代表白色和黑色的边界。
  • O(V+E)

最短路径与BFS

LeetCode Practical Experience

相较于Recursive solution，依靠Queue实现Iterative BFS能够节省大量的空间

N-ary Tree 的实现

Public class Node {
  int val;
  List<Node> children;
}

q.add(root);

while(q.size() != 0) {
    int size = q.size(); //get a unchangeable value
  for(int i = 0; i < size; i++) {
    Node node = q.poll();
    //Implement some operations for each node here
    for(Node c : node.children) {
      q.add(c); //add node's children into queue
    }
  }
  //Implement some operations for each level here
}

从左到右与从右到左添加children：

//For binary tree 
//from left to right: 
if(node.left != null) {q.add(node.left);}
if(node.right != null) {q.add(node.right);}

//from right to left:
if(node.right != null) {q.add(node.right);}
if(node.left != null) {q.add(node.left);}

一些注意事项：

  • 分清楚Node和TreeNode
  • 善用Integer.MIN_VALUE和Integer.MAX_VALUE（对于负值，0会输出错误答案）
赏

   Reprint policy


《Bread-First-Search and Depth-First-Search》 by Mie is licensed under a Creative Commons Attribution 4.0 International License
  TOC