0%

算法基础（7）

发表于 更新于 分类于 本文字数： 7.8k
第三章内容：深度优先搜索、宽度优先搜索、树与图的存储、树与图的深度优先遍历，树与图的宽度优先遍历，拓扑排序。

第三章 搜索与图论

DFS

深度优先搜索—DFS，宽度优先搜索—BFS

数据结构 空间
DFS 栈stack $O(h)$ 不具有最短性
BFS 队列queue $O(2^h)$ “最短路”

DFS中关键的两点是：回溯和剪枝，DFS可以从搜索树的角度来考虑。DFS解题最重要的考虑搜索的顺序。

DFS例题1：排列数字（Acwing 842）

给定一个整数n，将数字1~n排成一排，将会有很多种排列方法。现在，请你按照字典序将所有的排列方法输出。

输入格式：共一行，包含一个整数n。

输出格式：按字典序输出所有排列方案，每个方案占一行。

数据范围：$1 \le n \le 7$。

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

const int N = 10;

int n;
int path[N];
bool st[N];

void dfs(int u)
{
    if(u == n)
    {
        for(int i = 0; i < n; i++)  printf("%d ", path[i]);
        puts("");
        return;
    }
    
    for(int i = 1; i <= n; i++)   //注意i从1开始，因为要枚举的数是从1到n
        if(!st[i])
        {
            path[u] = i;
            st[i] = true;
            dfs(u + 1);
            st[i] = false;
        }
}
int main()
{
    cin >> n;
    
    dfs(0);
    
    return 0;
}

DFS例题2：n-皇后问题（Acwing 843）

n-皇后问题是指将 n 个皇后放在 n∗n 的国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上。现在给定整数n，请你输出所有的满足条件的棋子摆法。

输入格式：共一行，包含整数n。

输出格式：每个解决方案占n行，每行输出一个长度为n的字符串，用来表示完整的棋盘状态。其中”.”表示某一个位置的方格状态为空，”Q”表示某一个位置的方格上摆着皇后。每个方案输出完成后，输出一个空行。输出方案的顺序任意，只要不重复且没有遗漏即可。

数据范围：$1 \le n \le 9$。

思路1：搜索顺序类似于全排列，从第一行开始，枚举皇后可以放到哪。可以提前判断当前方案一定是不合法的，就不用继续向下搜索了，直接回溯即可，这一过程就是“剪枝”。（时间复杂度：$O(n \cdot 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
39
40
#include<iostream>
using namespace std;

const int N = 10;

int n;
char g[N][N];
bool col[N], dg[2 * N], udg[2 * 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;
}

思路2：按棋盘格子开始枚举，放下皇后是一个分支，不放是另一个分支。（时间复杂度：$O(2^{n^2})$）

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

const int N = 10;

int n;
char g[N][N];
bool row[N], col[N], dg[2 * N], udg[2 * N];  //分别代表列，对角线，反对角线

void dfs(int x, int y, int s)    //x, y, s分别代表当前遍历的格子的行，列，已经摆好的皇后的个数
{ 
    if (y == n)  y = 0, x ++;   //遍历完一行后，转向下一行
    if (x == n)
    {
        if(s == n)
        {
            for(int i = 0; i < n; i++)  puts(g[i]);
            puts("");
        }
        return;
    }
    
    //下一个格子不放皇后
    dfs(x, y + 1, s);
    
    //下一个格子放皇后
    if(!row[x] && !col[y] && !dg[x + y] && !udg[x - y + n])
    {
        g[x][y] = 'Q';
        row[x] = col[y] = dg[x + y] = udg[x - y + n] = true;
        dfs(x, y + 1, s + 1);
        row[x] = col[y] = dg[x + y] = udg[x - y + n] = false;
        g[x][y] = '.';
    }
}

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的优势是可以搜索到最短路。（最短路问题包含DP动态规划问题，DP是没有环的最短路问题。）

不是所有的问题都是最短路问题，只有当所有边的权重都相同时，才可以用BFS求最短路，一般情况下都要用专门的最短路算法求。

BFS例题1：走迷宫（Acwing 844）

给定一个n*m的二维整数数组，用来表示一个迷宫，数组中只包含0或1，其中0表示可以走的路，1表示不可通过的墙壁。最初，有一个人位于左上角(1, 1)处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。请问，该人从左上角移动至右下角(n, m)处，至少需要移动多少次。数据保证(1, 1)处和(n, m)处的数字为0，且一定至少存在一条通路。

输入格式：第一行包含两个整数n和m。接下来n行，每行包含m个整数（0或1），表示完整的二维数组迷宫。

输出格式：输出一个整数，表示从左上角移动至右下角的最少移动次数。

数据范围：$1 \le n,m \le 100$。

从起点开始搜，第一步把所有距离为1的点搜一遍，第二步把所有距离为2的点搜一遍，……，

BFS解题的基本框架：

1
2
3
4
5
6
初始状态放入队列 queue;
while queue 不空
{
	t = 队头;
	拓展 t;
}
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
54
55
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>

using namespace std;

typedef pair<int, int> PII;
const int N = 110;

int n, m;
int g[N][N];  //存放地图
int d[N][N];  //存放每一个点到起点的距离

int bfs()
{
    queue<PII> q;  //存每个点的坐标(x, y)
    
    memset(d, -1, sizeof d);  //初始化d，表示没有被搜索过
    d[0][0] = 0;   //从(0, 0) 开始
    q.push({0, 0});
    
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};   //用向量表示搜索的四个方向：上，右，下， 左
    
    while(q.size())
    {
        auto t = q.front();  //取队头元素
        q.pop();  //将队头元素弹出，队列里保持只有一个元素
        
        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 && g[x][y] == 0 && d[x][y] == -1)
            {
                d[x][y] = d[t.first][t.second] + 1;
                q.push({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;
}

BFS例题2：八数码（Acwing 845）

可以把3*3矩阵的一个状态看作图论中的一个点，若从一个状态经过一次操作可以变成另一个状态，就在对应的两个点之间连一条边。

本题难点：

  • 状态表示复杂，可以将3*3矩阵中的数用一个字符串来表示，如"1234x5678"，queue<string> queue；dist[]数组可以用字典来存，如unordered_map<string, int> dist

  • 如何记录每个状态的“距离” dist[]数组：（1）3*3矩阵；（2）枚举x能移动的位置；（3）将x移动后的矩阵恢复成字符串

树与图的遍历

树是特殊的图——无环连通图。图分为有向图和无向图，而无向图又可以看作是特殊的有向图，因此我们只需考虑有向图的遍历问题即可。

有向图的存储方式：

  1. 邻接矩阵：g[a][b]，表示$a \to b$的一条边；
  2. 邻接表：每个节点上开一个单链表，存这个点可以走到哪些点。若有新连接的边，一般在链表的头节点插入新的点。

树与图的遍历方式：

  1. 深度优先遍历
  2. 宽度优先遍历

深度优先遍历例题：树的重心（Acwing 846）

给定一颗树，树中包含n个结点（编号1~n）和n-1条无向边。请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。

输入格式：第一行包含整数n，表示树的结点数。接下来n-1行，每行包含两个整数a和b，表示点a和点b之间存在一条边。

输出格式：输出一个整数m，表示重心的所有的子树中最大的子树的结点数目。（树的重心可能不唯一）

数据范围：$1 \le n \le 10^5$。

在树的深度优先遍历时，可以求出每棵子树中的点的数量。

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
54
55
56
57
58
59
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 100010, M = N * 2;

int n;    
int h[N], e[M], ne[M], idx;  //idx 存当前的边数
bool st[N];  //表示当前点是否已经被搜过了；在深度优先遍历或者宽度优先遍历中每个点只会被遍历一次

int ans = N;   //存最后的结果，即删除重心后，使剩余连通块点的数目的最大值最小 的那个值

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

int dfs(int u)    //深度优先遍历，返回以u为根的子树中的点的数量
{
    st[u] = true;  //标记当前点已经被搜过了
    
    //sum存当前子树中点的数目，res存将当前点删除后，剩余连通块中点的数目的最大值
    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(res, n - sum);
    
    ans = min(ans, res);
    return sum;
}

int main()
{
    cin >> n;
    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);   //搜索的是图中的结点编号，结点编号从1开始
    
    cout << ans << endl;
    return 0;
}

宽度优先遍历例题：图中点的层次（Acwing 847）

给定一个n个点m条边的有向图，图中可能存在重边和自环。所有边的长度都是1，点的编号为1~n。请你求出1号点到n号点的最短距离，如果从1号点无法走到n号点，输出-1。

输入格式：第一行包含两个整数n和m。接下来m行，每行包含两个整数a和b，表示存在一条从a走到b的长度为1的边。

输出格式：输出一个整数，表示1号点到n号点的最短距离。

数据范围：$1 \le n,m \le 105$。

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
54
55
56
57
58
59
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 100010;

int n, m;
int h[N], e[N], ne[N], idx;
int d[N], q[N];   //q[]存 用数组模拟的队列

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是该图的一个拓扑序列。

也就是说，当把图按照拓扑序排列好后，所有的边都是从前指向后的（点在序列中的顺序）。并不是所有图都有拓扑序列，如存在环的图。一个有向无环图，一定存在拓扑序列，因此有向无环图也叫作拓扑图。

点的入度与出度：

  • 入度：一个点有多少条边指向自己，就是它的入度；

  • 出度：一个点有多少条边从自己出去，就是它的出度。

入度为0的点可以作为起点（当前最前面的位置），一个有向无环图，至少存在一个入度为0的点。

1
2
3
4
5
6
7
8
9
10
所有入度为0的点入队列 queue
while queue 不空
{
    t = 队头;
    枚举t的所有出边 t-j
    {   删掉t-j, j的入度减1;
        if(j的入度为0):
        	队头 = j;
    }
}
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
54
55
56
57
58
59
60
61
62
63
#include<iostream>
#include<cstring>
using namespace std;

const int N = 100010;

int n, m;
int h[N], e[N], ne[N], idx;
int q[N], d[N];   //d[] 表示一个点的入度

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

bool topsort()
{
    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] == 0)  q[++ tt] = j;
            
        }
        
    }
    
    return tt == n - 1;  //若所有点已经入队，那队尾就是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] ++;    //d[]表示一个点的入度，注意这里要入度++
    }
    
    if(topsort())
    {
        for(int i = 0; i < n; i++)  printf("%d ", q[i]);  //q[]中的次序恰好就是拓扑序列
        puts("");
    }
    else puts("-1");
    
    return 0;
}