深度优先搜索,广度优先搜索和回溯

图的表示方法

邻接矩阵

V乘V的布尔矩阵,v和w之间有连接的边时,定义v行w列的元素值为true。

问题:不适合含有大量顶点的图。不能表示平行边。

边的数组

使用一个Edge类,含有两个int实例。

问题:实现adj()需要检查图中所有的边。

邻接表数组

以顶点为索引,每个元素都是和该定点相邻的顶点列表。

邻接表添加边

为了添加一条连接v与w的边,将w添加到v的邻接表中,并且把v添加到w的邻接表中。

性能

  • 空间和V+E成正比
  • 所需时间为常数
  • 遍历顶点v的所有相邻顶点所需时间和v的度数成正比

搜索

深度优先搜索

伪码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//Recursive
procedure DFS(G,v):
label v as discovered
for all edges from v to w in G.adjacentEdges(v) do
if vertex w is not labeled as discovered then
recursively call DFS(G,w)

//Non-recursive
procedure DFS-iterative(G,v):
let S be a stack
S.push(v)
while S is not empty
v = S.pop()
if v is not labeled as discovered:
label v as discovered
for all edges from v to w in G.adjacentEdges(v) do
S.push(w)

解决问题

  1. 连通性:判断两个顶点是否连通,或图中有多少个连通子图。
  2. 单点路径:给定一幅图和一个起点s,判断从s到给定顶点v是否存在一条路径。

DFS记录路径

可以添加一个edgeTo[]数组,在由边v-w第一次访问w时,将edgeTo[w]设为v来记住这条路径。也就是v-w是从起点s到w的最后一条已知的边。当最后需要取得路径时,可以通过将edgeTo压栈取得。

广度优先搜索

伪码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Breadth-First-Search(Graph, root):
create empty set S
create empty queue Q

root.parent = NIL
Q.enqueue(root)

while Q is not empty:
current = Q.dequeue()
if current is the goal
return current
for each node n that is adjacent to current:
if n is not in S:
add n to S
n.parent = current
Q.enqueue(n)

解决问题

单点最短路径

BFS查找路径

搜索的一般步骤

在搜索中我们都会先将起点存入数据结构,然后重复以下步骤直到数据结构被清空:

  1. 取其中的下一个顶点并标记它。
  2. 将v的所有相邻而又未被标记的顶点加入数据结构。

回溯(Backtracking)

回溯可以枚举出部分(或)全部问题的解,而不是一个解。

一般一个解被当作潜在搜索树(potential search tree)的一个节点。每个节点的子节点是该节点经过单步拓展所得,树的叶子节点是不能再被拓展的解。

回溯算法递归地搜索该树,按照深度优先的顺序。

伪码

  1. root(P): return the partial candidate at the root of the search tree.
  2. reject(P,c): return true only if the partial candidate c is not worth completing.
  3. accept(P,c): return true if c is a solution of P, and false otherwise.
  4. first(P,c): generate the first extension of candidate c.
  5. next(P,s): generate the next alternative extension of a candidate, after the extension s.
  6. output(P,c): use the solution c of P, as appropriate to the application.
1
2
3
4
5
6
7
procedure bt(c)
if reject(P,c) then return
if accept(P,c) then output(P,c)
s ← first(P,c)
while s ≠ Λ do
bt(s)
s ← next(P,s)

有时候s ← first(P,c)和s ← next(P,s)可以合并写入到那个while循环中。

回溯练习

深刻理解上面的理论后,去leetcode找了几道medium难度的回溯问题。分别是:

17-Letter Combinations of a Phone Number

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
//17-Letter Combinations of a Phone Number
#include <iostream>
#include <string>
#include <vector>
#include <map>
using namespace std;
class Solution {
public:
Solution() {
digitMap['0'] = vector<char>();
digitMap['1'] = vector<char>();
digitMap['2'] = vector<char>{'a', 'b', 'c'};
digitMap['3'] = vector<char>{'d', 'e', 'f'};
digitMap['4'] = vector<char>{'g', 'h', 'i'};
digitMap['5'] = vector<char>{'j', 'k', 'l'};
digitMap['6'] = vector<char>{'m', 'n', 'o'};
digitMap['7'] = vector<char>{'p', 'q', 'r', 's'};
digitMap['8'] = vector<char>{'t', 'u', 'v'};
digitMap['9'] = vector<char>{'w', 'x', 'y', 'z'};
}
vector<string> letterCombinations(string digits) {
this->digits = digits;
vector<string> res;
string tmp;
if (digits.size() == 0) return res;
bt(res, tmp, 0);
return res;
}
private:
map<char, vector<char>> digitMap;
string digits;
void bt(vector<string> &res, string &tmp, size_t level) {
if (level > digits.size()) return;
if (level == digits.size()) {
res.push_back(tmp);
return;
}
vector<char> vc = digitMap[digits[level]];
for (auto &i : vc) {
cout << i << endl;
tmp.push_back(i);
bt(res, tmp, level + 1);
tmp.pop_back();
}
}
};

131-Palindrome Partitioning

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/131-Palindrome Partitioning
#include <iostream>
#include <string>
#include <vector>
#include <cassert>
using namespace std;
class Solution {
public:
vector<vector<string>> partition(string s) {
vector<string> res;
bt(s, res, final, 0);
return final;
}
public:
vector<vector<string>> final;
void bt(string s, vector<string> &res, vector<vector<string>> &final, int start) {
if (start == s.size()) {
final.push_back(res);
return;
}
for (int i = start; i < s.size(); ++i) {
if (is_palindrome(s, start, i)) {
res.push_back(s.substr(start, i - start + 1));
bt(s, res, final, i + 1);
res.pop_back();
}
}
}
bool is_palindrome(const string & s, int start, int end) {
int i = start, j = end;
while (i < j) {
if (s[i] != s[j])
return false;
i++;
j--;
}
return true;
}
};

216-Combination Sum III

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
//216-Combination Sum III
#include <iostream>
#include <vector>
#include <set>
using namespace std;
class Solution {
public:
vector<vector<int>> combinationSum3(int k, int n) {
vector<vector<int>> res;
vector<int> tmp;
this->k = k;
this->n = n;
bt(res, tmp, 0, 0);
return res;
}
private:
int k, n;
void bt(vector<vector<int>> &res, vector<int> &tmp, int level, int cur) {
if (level > k || sum(tmp) > n) return;
if (level == k && sum(tmp) == n) {
res.push_back(tmp);
return;
}
for (int i = cur + 1; i <= 9; ++i) {
tmp.push_back(i);
bt(res, tmp, level + 1, i);
tmp.pop_back();
}
}
int sum(vector<int> &vec) {
int res = 0;
for (int i : vec) {
res += i;
}
return res;
}
};

参考资料

  1. Depth-first-search
  2. Breadth-first-search
  3. Backtracking
  4. <<算法>>