深度优先搜索（DFS）

回溯，剪枝。想清楚搜索顺序。回溯时注意恢复现场。

搜索框架

排列数字

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
#include <iostream>
using namespace std;

const int N = 10;

// 记录是否使用过
bool st[N];
int n;
// 保存每次搜索的路径。path 用于存每个方案。
int path[N];
// u 代表搜索第几层，第 0 层时，填写了 0 个元素
void dfs(int u) {
    if(u == n) {
        for(int i=0;i<n;i++) cout << path[i] << " ";
        cout << endl;
        return;
    }
    // 在每一层时，从 1 到 n 依次查看当前位置能不能填 i
    for(int i=1;i<=n;i++) {
        if(!st[i]) {
            st[i] = true;
            path[u] = i;
            dfs(u+1);
            st[i] = false;
        }
    }
}

int main() {
    cin >> n;
    dfs(0);
    return 0;
}

n 皇后

第一种搜索方式

遍历每一行，考虑将皇后放在第几列上。

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
#include <iostream>
using namespace std;

const int N = 20;

bool col[N], dg[N], udg[N];
int n;
char g[N][N];

// 遍历每一行
void dfs(int u) {
    if(u == n) {
        for(int i=0;i<n;i++) puts(g[i]);
        puts("");
        return;
    }
    // 考虑将皇后放在哪一列
    for(int i=0;i<n;i++) {
        if(!col[i] && !dg[u+i]&&!udg[n-u+i]) {
            g[u][i] = 'Q';
            col[i] = dg[u+i] = udg[n-u+i] = true;
            dfs(u+1);
            col[i] = dg[u+i] = udg[n-u+i] = false;
            g[u][i] = '.';
        }
    }
}

int main() {
    cin >> n;
    for(int i=0;i<n;i++) {
        for(int j=0;j<n;j++) {
            g[i][j] = '.';
        }
    }
    dfs(0);
    return 0;
}

第二种搜索方式

从上到下，从左到右依次考虑每个格子放不放皇后。

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
#include <iostream>
using namespace std;

const int N = 20;
char g[N][N];
int row[N], col[N], dg[N], udg[N];
int n;

void dfs(int x, int y, int s) {
    if(y == n) y=0, x++;
    if(x == n) {
        if(s == n) {
            for(int i=0;i<n;i++) {
                for(int j=0;j<n;j++) {
                    cout << g[i][j];
                }
                cout << endl;
            }
            cout << endl;
        }
        return;
    }

    dfs(x, y+1, s);

    if(!row[x] && !col[y] && !dg[x+y] && !udg[x-y+n]) {
        row[x] = col[y] = dg[x+y] = udg[x-y+n] = true;
        g[x][y] = 'Q';
        dfs(x, y+1, s+1);
        g[x][y] = '.';
        row[x] = col[y] = dg[x+y] = udg[x-y+n] = false;
    }
}

int main() {
    cin >> n;
    for(int i=0;i<n;i++) {
        for(int j=0;j<n;j++) {
            g[i][j] = '.';
        }
    }

    dfs(0,0,0);
    return 0;
}

宽度优先搜索（BFS）

BFS 可以搜索边权相同的图中的最短路。

走迷宫

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
47
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

const int N = 110;

typedef pair<int, int> PII;

int g[N][N];
// d[x][y] 表示点 (x, y) 到起点 (0, 0) 的距离。
int d[N][N];

PII q[N * N];

int n, m;
int bfs() {
    int hh = 0, tt = 0;
    q[0] = {0,0};

    memset(d, -1, sizeof d);
    d[0][0] = 0;
    int dx[4] = {-1,0,1,0}, dy[4] = {0,1,0,-1};
    while(hh <= tt) {
        auto t = q[hh++];
        for(int i=0;i<4;i++) {
            int x = t.first + dx[i], y = t.second + dy[i];
            if(x>=0 && x<n && y>=0 && y<m && d[x][y] == -1 && g[x][y] == 0) {
                // (x, y) 距离起点的距离等于当前点距离起点的距离加 1
                d[x][y] = d[t.first][t.second] + 1;
                // prev[x][y] = t;
                q[++tt] = {x, y};
            }
        }
    }
    return d[n-1][m-1];
}
int main() {
    cin >> n >> m;
    for(int i=0;i<n;i++) {
        for(int j=0;j<m;j++) {
            cin >> g[i][j];
        }
    }
    cout << bfs() << endl;
    return 0;
}

DFS 与 BFS 对比

算法 数据结构 空间 优点
DFS 栈 O(h)O(h) 路径不具备最短性
BFS 队列 O(2h)O(2^{h}) 可以搜索最短路

树和图

树是一种特殊的图，无环连通图。

图分为有向图和无向图。

无向图是一种特殊的有向图。可以看成两条边互相连通的有向图。

图的存储

邻接矩阵

适合存储稠密图，空间复杂度为 O(n2)O(n^{2})。n 为节点数量。

邻接表

每个节点都对应一个单链表，存储与当前节点相连的其他节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
图：

2 ----------> 4
| \         ^ ^
|   \     /   |
|     \ /     |
|     / \     |
|   /     \   |
v /         v |
1 ----------> 3

邻接表：

h[1]: ---> 3 ---> 4 ---> ø
h[2]: ---> 1 ---> 4 ---> ø
h[3]: ---> 4 ---> ø
h[4]: ---> ø

树的重心

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
47
48
49
50
51
#include <iostream>
#include <cstring>

using namespace std;
const int N = 1e5 + 10, M = N*2;
int n,m;
// 邻接表
// h[a] 表示 a 节点对应的链表的头的编号。h[节点] 可以找到与节点相邻的所有节点。
int h[N], e[M], ne[M], idx;
bool st[N];
int ans = N;

// 插入一条由 a 指向 b 的边
void add(int a, int b) {
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

// dfs 遍历树的一个好处是可以返回每个子树的大小。
// 返回以 u 为根的子树的节点数量
int dfs(int u) {
    st[u] = true;
    int sum = 1, res = 0;
    for(int i=h[u];i!=-1;i=ne[i]) {
        int j = e[i];
        if(!st[j]) {
            int s = dfs(j);
            res = max(res, s);
            sum+=s;
        }
    }
    res = max(n-sum, res);
    ans = min(res, ans);
    return sum;
}

int main() {
    cin >> n;
    // 邻接表初始化，将所有的链表头初始化为 -1
    memset(h, -1, sizeof h);
    for(int i=0; i<n-1; i++) {
        int a,b;
        cin >>a >> b;
        add(a,b);
        add(b,a);
    }
    dfs(1);
    cout << ans << endl;
    return 0;
}

图中点的层次

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
#include <iostream>
#include <cstring>
using namespace std;

const int N = 100010;
int n,m;
int h[N], e[N], ne[N], idx;
int d[N], q[N];

void add(int a, int b) {
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

int bfs() {
    int hh = 0, tt = 0;
    q[0] = 1;

    memset(d, -1, sizeof d);
    d[1] = 0;
    while(hh <= tt) {
        int t = q[hh++];
        for(int i=h[t]; i!=-1; i=ne[i]) {
            int j = e[i];
            if(d[j] == -1) {
                d[j] = d[t] + 1;
                q[++tt] = j;
            }
        }
    }
    return d[n];
}

int main() {
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for(int i=0;i<m;i++) {
        int a, b;
        cin >> a >> b;
        add(a, b);

    }
    cout << bfs() << endl;
    return 0;
}

拓扑排序

有向无环图也称为拓扑图。

如果有环，那一定没有拓扑序。

拓扑序不一定唯一。

若一个由图中所有点构成的序列 A 满足：对于图中的每条边 (x, y)，x 在 A 中都出现在 y 之前，则称 A 是该图的一个拓扑序列。

有向图的拓扑序列

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
47
48
49
50
51
52
53
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1e5 + 10;

int q[N], d[N];
int e[N], ne[N], h[N], idx;

int n, m;
void add(int a, int b) {
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}
bool toposort() {
    int hh = 0, tt = -1;
    for(int i=1;i<=n;i++) {
        if(!d[i]) {
            q[++tt] = i;
        }
    }
    while(hh<=tt) {
        int t = q[hh++];
        for(int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
            d[j]--;
            if(!d[j]) {
                q[++tt] = j;
            }
        }
    }

    return tt == n-1;
}
int main() {
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for(int i=0;i<m;i++) {
        int a, b;
        cin >> a >> b;
        add(a, b);
        d[b]++;
    }
    if(toposort()) {
        for(int i=0;i<n;i++) cout << q[i] << " ";
        cout << endl;
    } else {
        puts("-1");
    }
    return 0;
}