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

Posted on | In | Views:
简单回顾一下DFS、BFS和backtracking。

图的表示方法

邻接矩阵

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. <<算法>>