Acwing - 算法基础课 - 笔记（七）

今天药忘吃喽~ 2022-10-09 03:29 155阅读 0赞

### 文章目录 ###

*   *  搜索与图论（一）
     *   *  DFS和BFS
         *   *  概述
             *  DFS
             *  BFS
         *  树与图的存储
         *  树与图的深度优先遍历
         *  树与图的宽度优先遍历
         *  拓扑排序

## 搜索与图论（一） ##

本节讲的是，普通的DFS和BFS，树和图的存储，拓扑排序。

### DFS和BFS ###

#### 概述 ####

DFS：深度优先搜索（Depth-First-Search）

BFS：宽度优先搜索（Breadth-First-Search）

**DFS和BFS的对比**

*  DFS使用**栈**（stack）来实现，BFS使用**队列**（queue）来实现
 *  DFS所需要的空间是树的高度h，而BFS需要的空间是2h （DFS的空间复杂度较低）
 *  DFS不具有最短路的特性，BFS具有最短路的特性

通常来说，求“最短”的操作，都可以用BFS来做，而其他一些奇怪的操作，或者对空间复杂度要求比较高，则用DFS来做

#### DFS ####

DFS中的2个重要概念：

*  回溯：回溯的时候，一定要记得恢复现场
 *  剪枝：提前判断某个分支一定不合法，直接剪掉该分支

**DFS练习题**：

[acwing - 842: 排列数字][acwing - 842_]

经典DFS问题，对于数n，其排列一共有n个位置，我们深搜从第一个位置开始枚举，直到第n个位置，每个位置放一个数字，而每个数字只能使用一次，所以对于1~n这n个数字，我们需要维护一个状态，来表示某个数字是否已经被使用过。当我们深搜到某个位置x时，若在这个位置之前，某个数k已经被使用过，则位置x上不能再放数k。即，每次在某一个位置上枚举数字，选择一个当前还未被使用过的数字，放置在该位置上，然后深搜下一个位置。**记得回溯时，需要还原这个数字的状态**。将这个数字从**已被使用**，还原为**未被使用**。另外需要一个`path`变量，来存储当前深搜所经过的路径，当深搜到叶子节点时，这个`path`即是一种排列，输出即可。

#include<iostream>
    using namespace std;
    const int N = 10;
    bool visited[N];
    int n, path[N];
    
    // x 代表当前是第几个位置的数， x 可能取值为1，2，3....，n
    void dfs(int x) { 
    	if(x == n + 1) { 
    		// 到达根节点, 深搜结束, 输出
    		for(int i = 1; i <= n; i++) printf("%d ", path[i]);
    		printf("\n");
            return ;
    	}
        // 否则, 枚举1~n, 找到一个可用数字, 放到当前位置
    	for(int i = 1; i <= n; i++) { 
    		if(!visited[i]) { 
                // 当数字i还未被使用过时, 将i放到当前位置x上, 并标记其为 已被使用, 随后深搜下一个位置x + 1
    			path[x] = i;
    			visited[i] = true;
    			dfs(x + 1);
    			visited[i] = false; // 这里只需要还原状态变量即可, path[x]会在下一个循环被覆盖掉
    		}
    	}
    }
    
    int main() { 
    	scanf("%d", &n);
    	dfs(1); // 先从第一个位置的数开始深搜
    	return 0;
    }

[acwing - 843: n-皇后问题][acwing - 843_ n-]

**解法一**：

首先经过思考和提炼，容易发现，每一行只能放一个皇后，则问题被精简成了，从第一行开始，到第n行，依次确定每一行的皇后的摆放位置。我们需要针对**行，列，对角线，反对角线**，维护状态变量。比如`col[i]`表示第`i`列上的状态，若`col[i] = true`，表示该列已经被一个皇后占用，该列上无法再放多一个皇后，同理，`dg[i]`表示第`i`条对角线的状态，`rdg[i]`表示第`i`条反对角线的状态。而由于我们是依次在每一行上摆放一个皇后，这就变相地保证了，每一行只有一个皇后，则行是不可能冲突的，所以就无需维护针对**行**的状态。另外需要注意，若棋盘是n × n，则一共有n列，n行，但对角线有2n - 1条，反对角线也是2n - 1条，可自行画图验证。我们需要确定对于一个点`[x, y]`，其所在的是第几条对角线，以及第几条反对角线，以及对角线，反对角线的编号从哪里开始。

#include<iostream>
    using namespace std;
    const int N = 20;
    char ans[N][N]; // 结果矩阵
    bool col[N], dg[2 * N], rdg[2 * N]; // 状态变量
    int n;
    
    // 从第一行开始摆放皇后, x代表当前需要摆放的是第几行
    void dfs(int x) { 
    	if(x == n + 1) { 
    		// 深搜到达叶子节点, 输出
    		for(int i = 1; i <= n; i++) { 
    			for(int j = 1; j <= n; j++) printf("%c", ans[i][j]);
    			printf("\n");	
    		}
    		printf("\n");
    		return ;
    	}
    
    	for(int y = 1; y <= n; y++) { 
    		// 枚举的是列, 看这一行的1~n列中, 哪一列可以放皇后
    		if(!col[y] && !dg[x + y - 1] && !rdg[y - x + n]) { 
    			// 若当前位置[x,y] 所在的列, 对角线, 反对角线, 皆没有被占用, 则当前位置可以放皇后
    			col[y] = dg[x + y - 1] = rdg[y - x + n] = true; // 更新状态变量
    			ans[x][y] = 'Q'; // 放皇后
    			dfs(x + 1); // 深搜下一行
    			ans[x][y] = '.'; // 还原
    			col[y] = dg[x + y - 1] = rdg[y - x + n] = false; // 还原状态变量
    		}
    	}
    }
    
    int main() { 
    	scanf("%d", &n);
        // 初始化结果矩阵
    	for(int y = 1; y <= n; y++) { 
    		for(int j = 1; j <= n; j++) ans[y][j] = '.';
    	}
    	dfs(1);
    	return 0;
    }

**解法二**：

若不经过思考提炼，则更一般的做法（更暴力的做法）是：从棋盘的第一个位置`[1, 1]`依次枚举到最后一个位置`[n,n]`。每个位置都有两种选择：**放**或者**不放**皇后（这就对应了两个分支）。对比解法一，此时我们就需要多维护一个针对行的状态变量了。其余逻辑和解法一类似，只是需要对每个位置的点进行枚举

#include<iostream>
    using namespace std;
    const int N = 20;
    char ans[N][N]; // 结果矩阵
    bool row[N], col[N], dg[2 * N], rdg[2 * N]; // 状态变量
    int n;
    
    // x 是第几行, y 是第几列, s 是当前已经放了几个皇后了
    void dfs(int x, int y, int s) { 
    	
    	// 若某一行枚举结束, 移动到下一行第一个元素
    	if(y == n + 1) { 
    		x++;
    		y = 1;
    	}
    	// 所有点已经枚举完毕, 此时只有当摆放了n个皇后时, 才是一个可行的解
        // 因为dfs的全部叶子节点，是对n^2个位置，每个位置选择放或者不放的一种排列, 
        // 则每个叶子节点到根节点的路径, 可能一共摆放了不到n个皇后, 极端一点, 每个位置都选择不放, 也形成了一个叶子节点
    	if(x == n + 1) { 
    		if(s == n) { 
    			for(int i = 1; i <= n; i++) { 
    				for(int j = 1; j <= n; j++) printf("%c", ans[i][j]);
    				printf("\n");
    			}
    			printf("\n");
    		}
    		return ; // 已经枚举完所有位置, 直接返回
    	}
    	// 两种情况
    	// 1. 当前位置不放皇后, 则直接走到下一个位置
    	dfs(x, y + 1, s);
    	// 2. 尝试在当前位置放皇后
    	if(!row[x] && !col[y] && !dg[x + y - 1] && !rdg[y - x + n]) { 
    		// 当前位置可以放皇后
    		ans[x][y] = 'Q'; // 放皇后
    		row[x] = col[y] = dg[x + y - 1] = rdg[y - x + n] = true; // 更新状态变量
    		dfs(x, y + 1, s + 1); // 放下去的皇后数量加一, 走到下一个位置
    		// dfs完毕, 恢复现场
    		ans[x][y] = '.';
    		row[x] = col[y] = dg[x + y - 1] = rdg[y - x + n] = false;
    	}
    }
    
    int main() { 
    	scanf("%d", &n);
    	for(int y = 1; y <= n; y++) { 
    		for(int j = 1; j <= n; j++) ans[y][j] = '.';
    	}
    	dfs(1, 1, 0); // 从[1,1]开始深搜, 初始放的皇后数量为0
    	return 0;
    }

显然，解法二由于枚举了棋盘上的所有位置，其性能相比解法一要差一些

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZjajEwMDk3ODQ4MTQ_size_16_color_FFFFFF_t_70][]

#### BFS ####

从左到右，一层一层的搜，所以叫宽度优先搜索。宽搜的基本框架：

1. 插入一个初始状态到queue中
    2. while(queue非空)
     2.1 把队头拿出来
     2.2 扩展队头
    3. end

**BFS练习题**

[acwing - 844: 走迷宫][acwing - 844_]

#include<cstring>
    #include<iostream>
    #include<queue>
    using namespace std;
    
    typedef pair<int,int> PII;
    
    const int N = 110;
    int n, m;
    int a[N][N], d[N][N]; // a用来存矩阵数组, d用来存从起点走到该点的距离
    
    int main() { 
    	scanf("%d%d", &n, &m);
    
    	for(int i = 0; i < n; i++) { 
    		for(int j = 0; j < m; j++) { 
    			scanf("%d", &a[i][j]);
    		}
    	}
    
    	// -1表示该点还未走到
    	memset(d, -1, sizeof d);
    
    	queue<PII> q;
    	// 初始化
    	q.push({ 0,0});
    	d[0][0] = 0;
        // 每次往下走需要调整的x和y
    	int dx[4] = { 0, 1, 0, -1};	
    	int dy[4] = { 1, 0, -1, 0};
    	while(!q.empty()) { 
    		PII p = q.front();
    		q.pop();
    		for(int i = 0; i < 4; i++) { 
    			int x = p.first + dx[i];
    			int y = p.second + dy[i];
                // 当这个点在边界内, 且这个点为0, 且该点还未被走到过, 则走过去
    			if(x >= 0 && x < n && y >= 0 && y < m && a[x][y] == 0 && d[x][y] == -1) { 
    				q.push({ x,y});
    				d[x][y] = d[p.first][p.second] + 1;
    			}
    		}
    	}
    	printf("%d\n", d[n - 1][m - 1]);
    	return 0;
    }

课后题：[acwing - 845: 八数码][acwing - 845_]

求的其实是个最小的操作步数，考虑用BFS来做。把每一种棋盘的状态，当作树中的一个节点，其实就是寻找初始状态，到最终状态，是否存在一个路径，并找出最短路。难点在于棋盘的状态表示，以及如何将状态进行存储，并记录每种状态之间的距离。

由于这道题涉及到的一些C++语法不是特别熟，所以就写了一版java的题解

import java.util.*;
    
    /** * @Author yogurtzzz * @Date 2021/6/30 16:42 **/
    public class Main { 
    
    	static Scanner scanner = new Scanner(System.in);
    
    	public static void main(String[] args) { 
    		// 读入初始状态
    		StringBuilder sb = new StringBuilder();
    		for(int i = 0; i < 9; i++) { 
    			String c = readString();
    			sb.append(c);
    		}
    		String initialState = sb.toString();
    		System.out.println(find(initialState));
    	}
    
    	static int find(String initialState) { 
    		String finalState = "12345678x";
    		Queue<String> queue = new LinkedList<>();
    		Map<String, Integer> stepCount = new HashMap<>();
    
    		// 将初始状态push进去
    		queue.offer(initialState);
    		stepCount.put(initialState, 0);
    		int[] dx = { 1, 0, -1, 0};
    		int[] dy = { 0, 1, 0, -1};
    
    		// 使用BFS
    		while (!queue.isEmpty()) { 
    			String s = queue.poll();
    			int currentCount = stepCount.get(s);
    			int pos = s.indexOf('x'); // 获取x的坐标
    			// 由于是 3 × 3 的矩阵, 转化一下, 得到二维坐标
    			int x = pos / 3;
    			int y = pos % 3;
    			// 枚举下一个状态(最多可能有4种)
    			for(int j = 0; j < 4; j++) { 
    				int newX = x + dx[j];
    				int newY = y + dy[j];
    				if (newX >= 0 && newX < 3 && newY >= 0 && newY < 3) { 
    					// 新的坐标没有超出边界, 则该状态是一种可能的状态
    					int newPos = newX * 3 + newY; // 二维坐标还原为一维坐标
    					char[] chars = s.toCharArray();
    					// 交换x和另一个数, 即交换pos和newPos
    					char temp = chars[pos];
    					chars[pos] = chars[newPos];
    					chars[newPos] = temp;
    					String nextState = new String(chars);
    					if (Objects.equals(nextState, finalState)) { 
    						// 找到最终的状态
    						return currentCount + 1;
    					}
    					if (!stepCount.containsKey(nextState)) { 
    						// 若先前没有出现过这种状态, 则加入, 因为是BFS, 若在先前出现过该状态, 则先前出现该状态时的步数一定更小
    						queue.offer(nextState);
    						stepCount.put(nextState, currentCount + 1);
    					}
    				}
    			}
    		}
    		return -1;
    	}
    
    	static String readString() { 
    		return scanner.next();
    	}
    }

### 树与图的存储 ###

首先，树是一种特殊的图（无环连通图）。所以，这里只说图的存储即可。

首先，图分为2种，**有向图**和**无向图**。

有向图中2个点之间的边是有方向的，比如`a -> b`，则只能从`a`点走到`b`点，无法从`b`点走到`a`点。

无向图中2个点之间的边是没有方向的，比如`a - b`，则可以从`a`走到`b`，也可以从`b`走到`a`。

通常，我们可以将无向图看成有向图。比如上面，对`a`到`b`之间的边，我们可以建立两条边，分别是`a`到`b`的，和`b`到`a`的。

所以，我们只需要考虑，有向图如何存储，即可。通常有2种存储方式

*  邻接矩阵
    
    用一个二维数组来存，比如`g[a,b]`存储的就是`a`到`b`的边。邻接矩阵无法存储重复边，比如`a`到`b`之间有2条边，则存不了。（用的较少，因为这种方式比较浪费空间，对于有n个点的图，需要n2的空间，这种存储方式适合存储**稠密图**）
 *  **邻接表**
    
    使用单链表来存。对于有n个点的图，我们开n个单链表，每个节点一个单链表。单链表上存的是该节点的邻接点（用的较多）

树和图遍历有2种方式，深度优先遍历和宽度优先遍历。

我们只需要考虑有向图的遍历即可。

### 树与图的深度优先遍历 ###

由于遍历时，每个点最多只会被遍历一次，所以深度优先遍历的时间复杂度是O(n+m)，

n是节点数，m是边数

练习题：[acwing - 846: 树的重心][acwing - 846_]

（深度优先遍历，可以算出每个子树所包含的节点个数）

#include<iostream>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int N = 1e5 + 10;
    int e[2 * N], ne[2 * N], idx; // 单链表
    int h[N]; // 用邻接表, 来存树
    int n, ans = N;
    bool visited[N];
    void add(int a, int b) { 
    	e[idx] = b;
    	ne[idx] = h[a];
    	h[a] = idx++;
    }
    
    // 返回节点x所在子树的节点个数
    int dfs(int x) { 
    	visited[x] = true;
    	// sum 用来存 x 为根节点的子树的节点个数
    	// res 来存, x 的子树的节点个数的最大值
    	int sum = 1, res = 0;
    	for(int i = h[x]; i != -1; i = ne[i]) { 
    		int j = e[i]; // 取节点
    		if(visited[j]) continue;
    		int s = dfs(j);
    		res = max(res, s);
    		sum += s;
    	}
    	res = max(res, n - sum); 
    	ans = min(ans, res);
    	return sum;
    }
    int main() { 
        memset(h, -1, sizeof h);
    	scanf("%d", &n);
    	for(int i = 1; i <= n - 1; i++) { 
    		int a, b;
    		scanf("%d%d", &a, &b);
    		add(a, b);
    		add(b, a);
    	}
    	dfs(1);
    	printf("%d", ans);
    	return 0;
    }

### 树与图的宽度优先遍历 ###

练习题：[acwing - 847: 图中点的层次][acwing - 846_]

#include<iostream>
    #include<queue>
    #include<cstring>
    using namespace std;
    const int N = 1e5 + 10;
    
    int h[N], e[N], ne[N], idx; // 用邻接表来表示
    int d[N]; // 从1号点走到i号点的最短距离
    int n, m;
    bool visited[N]; // 其实可以用d[i] = -1来判断
    
    void add(int a, int b) { 
    	e[idx] = b;
    	ne[idx] = h[a];
    	h[a] = idx++;
    }
    
    void bfs() { 
    	queue<int> q;
    	q.push(1);
    	d[1] = 0;
    	visited[1] = true;
    	while(!q.empty()) { 
    		int t = q.front();
    		q.pop();
    		for(int i = h[t]; i != -1; i = ne[i]) { 
    			int u = e[i];
    			if(!visited[u]) { 
    				d[u] = d[t] + 1;
    				visited[u] = true;
    				q.push(u);
    			}
    		}
    	}
    }
    
    int main() { 
    	memset(h, -1, sizeof h);
    	memset(d, -1, sizeof d);
    	scanf("%d%d", &n, &m);
    	int a, b;
    	while(m--) { 
    		scanf("%d%d", &a, &b);
    		add(a, b);
    	}
    	bfs();
    	printf("%d", d[n]);
    	return 0;
    }

### 拓扑排序 ###

图的宽度优先搜索的应用，求拓扑序（拓扑序是针对有向图的）

什么是拓扑序：将一个图的很多节点，排成一个序列，使得图中的所有边，都是从前面的节点，指向后面的节点。则这样一个节点的排序，称为一个拓扑序。

若图中有环，则一定不存在拓扑序。

可以证明，一个**有向无环图**，一定存在一个拓扑序列。有向无环图，又被称为**拓扑图**。

对于每个节点，存在2个属性，**入度**和**出度**。

入度，即，有多少条边指向自己这个节点。

出度，即，有多少条边从自己这个节点指出去。

所有入度为0的点，可以排在当前最前面的位置。

算法流程：

将所有入度为0的点入队。
    while(queue非空) {
    	t = queue.pop(); // 获取队头
    	枚举t的全部出边 t->j
    	  删掉边t->j, j节点的入度减一
    	  if(j的入度为0) 将j入队
    }

一个有向无环图，一定存在至少**一个入度为0**的点，

练习题：[acwing - 848: 有向图的拓扑序列][acwing - 848_]

#include<cstring>
    #include<iostream>
    using namespace std;
    
    const int N = 1e5 + 10;
    
    int h[N], e[N], ne[N], idx; // 邻接表来存图
    int in[N]; // 每个点的入度
    int q[N], hh, tt = -1; // 数组模拟队列
    
    int n, m;
    
    void add(int x, int y) { 
    	// y的入度加一
    	in[y]++;
    	// 邻接表
    	e[idx] = y;
    	ne[idx] = h[x];
    	h[x] = idx++;
    }
    
    
    int main() { 
    	memset(h, -1, sizeof h);
    	scanf("%d%d", &n, &m);
    	int x, y;
    	while(m--) { 
    		scanf("%d%d", &x, &y);
    		add(x, y);
    	}
    	// 将所有入度为0的点加入到队列中
    	for(int i = 1; i <= n; i++) { 
    		if(in[i] == 0) q[++tt] = i;
    	}
    
    	while(tt >= hh) { 
    		int t = q[hh++]; // 弹出队头
    		for(int i = h[t]; i != -1; i = ne[i]) { 
    			int u = e[i];
    			if(--in[u] == 0) { 
    				// 移除了节点t, 节点u入度减一, 若等于0, 加入到队列
    				q[++tt] = u;
    			}
    		}
    	}
    	if(tt == n - 1) { 
    		for(int i = 0; i < n; i++) printf("%d ", q[i]);
    	} else printf("-1");
    	
    	return 0;
    }

[acwing - 842_]: https://www.acwing.com/problem/content/844/
[acwing - 843_ n-]: https://www.acwing.com/problem/content/845/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZjajEwMDk3ODQ4MTQ_size_16_color_FFFFFF_t_70]: /images/20221005/c166115bf79841dc9b1f0902a9ea4921.png
[acwing - 844_]: https://www.acwing.com/problem/content/846/
[acwing - 845_]: https://www.acwing.com/problem/content/847/
[acwing - 846_]: https://www.acwing.com/problem/content/848/
[acwing - 848_]: https://www.acwing.com/problem/content/850/