leetcode总结无止境系列之DFS与BFS

####广度优先搜索BFS 伪代码如下:

BFS(G, s) // 图G=(V,E)使用邻接链表表示
for each vertex u belongs to G.V - {s}
u.color = WHITE // u结点颜色
u.d = ∞ // 从源节点s到u结点的距离
u.π = NIL // u结点在广度优先搜索中的前驱
s.color = GRAY
s.d = 0
s.π = NIL
Q = Empty
ENQUEUE(Q, s)
while Q != Empty
u = DEQUEUE(Q)
for each v belongs to G.Adj[u]
if v.color == WHITE
v.color = GRAY
v.d = u.d + 1
v.π = u;
ENQUEUE(Q, v)
u.color = BLACK

算法的初始化成本为O(V),每个结点进行一次入队出队操作,因此队列操作时间为O(V),扫描邻接链表总时间为O(E)。算法总复杂度为O(V+E),因此广度搜索时间是图G的邻接链表大小的一个线性函数。

####深度优先搜索DFS

伪代码如下:

DFS(G) //图G=(V,E)使用邻接链表表示
for each vertex u belongs to G.V
u.color = WHITE
u.π = NIL
time = 0; //time是个全局变量,用来计算时间戳
for each vertex u belongs to G.V
if u.color == WHITE
DFS-VISIT(G.u)

DFS-VISIT(G, u)
time = time + 1
u.d = time
u.color = GRAY
for each v belongs to G.Adj[u]
if v.color == WHITE
v.π = u
DFS-VISIT(G, v)
u.color = BLACK
time = time + 1
u.f = time

算法总复杂度为O(V+E)。

####深度优先搜索与广度优先搜索异同

相同点

  • 1、这两种方式都是盲目的搜索,只有在搜索空间小于计算机内存时才具有可行性。
  • 2、两种方式都有open集合和closed集合,open集合用来存储将要访问的节点,closed集合存储访问过的节点。
  • 3、两种方式的平均时间复杂度都是O(b^d).其中b是分支因子,d是搜索深度。
  • 4、两种访问方式都要涉及到在closed集合中查找节点是否已经访问过,对closed集合采用不同的数据结构存储有不同的性能,线性查找需要O(n)的时间复杂度,散列查找则需要常数的时间复杂度。

不同点

  • 1、很明显的搜索策略不同,一个是深度,一个是广度。
  • 2、深度优先搜索需要使用栈来存储open集合,添加和删除操作只需要常数时间,广度优先搜索需要使用队列来存储open集合,添加和删除操作只需要常数时间。
  • 3、深度优先搜索中栈只需要存储b*d个状态节点。广度优先搜索则存储b^d个状态节点。所以两种搜索方式的存储规模不同。
  • 4、深度优先搜索可以找到到目标状态的多条路径,广度优先搜索则保证找到的是到目标状态的最短路径。注:如果搜索的是树,则深度优先搜索等价先根遍历,广度优先搜索等价层次遍历。

leetcode 上相关题目汇总

1.Unique Paths

2.Unique Paths II

3.Word Search

4.Subsets

5.Subsets II

6.Path Sum

7.Path Sum II

8.Binary Tree Maximum Path Sum

crystal /
Published under (CC) BY-NC-SA in categories 面试  tagged with 算法  leetcode