BFS and DFS

如何表示一个图

临接列表(adjacency lists)和临接矩阵(adjacency matrix) ,有向图和无向图都可以用这样的方式来表示。

最简单的图的遍历算法之一，而且还是很多重要的其他算法的基础。Prim的最小生成树（minimum-spanning-tree) 和 Dijksra的最短路径算法（single-source shortest-paths)都使用了这个想法。

广度优先搜索在进一步遍历图中顶点之前，先访问当前顶点的所有邻接结点。

a .首先选择一个顶点作为起始结点，并将其染成灰色，其余结点为白色。

b. 将起始结点放入队列中。

c. 从队列首部选出一个顶点，并找出所有与之邻接的结点，将找到的邻接结点放入队列尾部，将已访问过结点涂成黑色，没访问过的结点是白色。如果顶点的颜色是灰色，表示已经发现并且放入了队列，如果顶点的颜色是白色，表示还没有发现

d. 按照同样的方法处理队列中的下一个结点。 基本就是出队的顶点变成黑色，在队列里的是灰色，还没入队的是白色。

算法导论中的伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//图G，从s开始广度优先遍历
BFS(G, s)
  //初始化s之外的所有其他节点
  for s 以外的所有定点 u:
    u.color = WHITE
    u.d = -1
    u.p = NIL //p代表父节点
  //初始化s
  s.color = GRAY
  s.d = 0
  s.p = NIL
  enqueue(s)
  while (u = dequeue()) != NIL
    for v in u的所有临接节点:
      if v.color == WHITE
        v.color = GRAY //入队列前设置为灰
        v.d = u.d + 1
        v.p = u
        enqueue(v)
     u.color = BLACK //访问过的设置为黑

因为每个节点都入队一次，而且，每个节点出来之后，都会对他的临接节点进行访问。所有 最后的时间复杂度为O(E+V)

在《算法》中，使用marked[]来代替对节点上色，用edgeTo[]代替父节点

参考：https://www.cnblogs.com/xiehongfeng100/p/4461772.html

深度优先搜索 Depth-first-seatch

深度优先搜索在搜索过程中访问某个顶点后，需要递归地访问此顶点的所有未访问过的相邻顶点。

初始条件下所有节点为白色，选择一个作为起始顶点，按照如下步骤遍历：

a. 选择起始顶点涂成灰色，表示还未访问

b. 从该顶点的邻接顶点中选择一个，继续这个过程（即再寻找邻接结点的邻接结点），一直深入下去，直到一个顶点没有邻接结点了，涂黑它，表示访问过了

c. 回溯到这个涂黑顶点的上一层顶点，再找这个上一层顶点的其余邻接结点，继续如上操作，如果所有邻接结点往下都访问过了，就把自己涂黑，再回溯到更上一层。

d. 上一层继续做如上操作，知道所有顶点都访问过。

算法导论中的实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
DFS(G)
    //对所有节点做初始化
	for u in G.V: // O(V)
    	u.color = WHITE
        u.p = NIL
    for u in G.V: // O(V)
		if u.color == WHITE
			DFS-Visit(G,u)  
            
GFS-Visit(G,u)
    //先设置为灰色
	u.color = GRAY
	//尝试所有的临接节点，
	for v in u的临接节点： //adj[v]次
		if v.color == WHITE
			v.p = u
			DFS-Visit(G, v)
    //在自己的所有临接节点都访问完成后，设置为黑色
    u.color = BLACK

DFS的时间复杂度为O(V+E)。