一、dfs
1. 定义
dfs，即深度优先搜索。顾名思义，即尽可能递归到达最深处，然后再回溯，以此类推，直到遍历完整个图。
2. 解析
通过递归实现。
主要用于解决找迷宫路径等问题。
dfs代码比bfs简单。要领：
用vis数组维护是否走过，记得清零；
dfs中continue的条件分三类：出界、已走过、不是所求。不要遗漏了。
3. 模板
const int Fx[8][2] = {{1, 0}, {1, 1}, {0, 1}, {-1, 1}, {-1, 0}, {-1, -1}, {0, -1}, {1, -1}}; // 方向
string a[maxn]; // 记录地图
bool vis[maxn][maxm]; // vis数组记录是否走过
void dfs(int x, int y) {
vis[x][y] = 1;
for(int k = 0; k < 8; k ++) {
int nx = x + Fx[k][0], ny = y + Fx[k][1];
if(nx < 0 || nx >= n || ny < 0 || ny >= m || vis[nx][ny] || a[nx][ny] == '*') continue; // 出界、已走过、不是所求
dfs(nx, ny); // 递归
}
}4. 例题
Uva-572：https://blog.nowcoder.net/n/8e03fa67e5f5427dace3bdcf7adad4cc
二、bfs
1. 定义
bfs，即广度优先搜索。顾名思义，即先走完这一层，再走下一层，以此类推，直到遍历完整个图。
2. 解析
通过队列实现。
主要用于解决简单（权值为1）的最短路问题。要领：
bfs问题要先想清楚“状态点”如何定义，然后维护相应维度的vis、a数组（地图）。
如果需要打印路径需要用p数组进行父节点的存储。debug时不要太着急，可以将打印信息写的详细一点，这样才能有利于更快地发现问题！
注意区分Dijkstra模板：bfs用的是普通队列，vis数组的更新位置在push后。
3. 变式
双向bfs
先通过逆向bfs求出距离d[maxn]，然后再进行正向的“bfs”，这样就能实现一些比较复杂的最短路径问题。复杂状态的表示
有时后一些状态点具有很多维度（比如八数码），或取值范围很大（超过1e8），这时没有办法通过vis数组来存储，因为会爆空间。
这时可以考虑这些方法来保存vis状态：set、哈希法（推荐）、康托展开。
4. 模板
const int Fx[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; // 方向
struct node { // 队列中的结点
int x, y, dist;
node(int x, int y, int dist) : x(x), y(y), dist(dist) {}
};
int a[maxn][maxm], vis[maxn][maxm], ans;
void bfs(int x0, int y0) {
queue<node> que;
que.push(node(x0, y0, 0)), vis[x0][y0] = 1; // 入队后紧接着更新vis
while(!que.empty()) {
node u = que.front();
que.pop();
if(u.x == n - 1 && u.y == m - 1) { // 退出条件（可选）
ans = u.dist;
break;
}
for(int i = 0; i < 4; i ++) {
int nx = u.x + Fx[i][0], ny = u.y + Fx[i][1];
if(nx < 0 || nx >= n || ny < 0 || ny >= m || vis[nx][ny] || a[nx][ny] == '#') continue;
que.push(node(nx, ny, u.dist + 1)), vis[nx][ny] = 1; // 入队后紧接着更新vis
}
}
}5. 例题
Uva-1600：https://blog.nowcoder.net/n/5aeea79a2a14464b9cc101e8d376442e
Uva-1599：https://blog.nowcoder.net/n/7c15d9766ba3450bbea4a55fd554dfc5
Uva-10085：https://blog.nowcoder.net/n/6a23a0608d0c43b6a7422c32beeaffd6
Uva-816：https://blog.nowcoder.net/n/d4265122a1454285b73e6b1f1ddeb9b4
三、并查集
1. 定义
将若干点进行加边联通，每个连通块形成一个代表元Fa[i]（i为连通块中的任意一点）。
2. 解析
并查集通常用于解决与连通相关的图论问题。
优化方法有：路径压缩、启发式连接。一般为了方便，只是用路径压缩就足够了。
3. 变式
在一些比较复杂的题目中，除了要维护父子关系，要需要维护其它的关系，这个时候需要 使用额外的辅助数组。
4. 模板
- 普通并查集
int n, Fa[maxn]; // 并查集要使用的Fa数组
int find(int x) {
return Fa[x] == x ? x : Fa[x] = find(Fa[x]); // 路径压缩
}
int main() {
......
for(int i = 1; i <= n; i ++) Fa[i] = i; // Fa初始化
......
for(const auto& e : E) { // 逐条加边
int u = find(e.u), v = find(e.v);
if(u == v) continue; // 若连通
Fa[u] = v; // 若不连通则将其连通
......
}
.....
}- 复杂并查集
int Fa[maxn], dist[maxn]; // 辅助数组：到father的距离（非路径压缩的距离）
int find(int x) {
if(Fa[x] == x) return x;
int fx = Fa[x];
Fa[x] = find(fx);
dist[x] += dist[fx]; // 在回溯过程中更新，需要用到原father即fx
return Fa[x];
}5. 例题
最小生成树专题：https://blog.nowcoder.net/n/d806b758176c4f7e9b1de4895dd36279
四、链式前向星
1. 定义
一种比vector快且省空间的存图方法。
2. 解析
链式向前星 就是一种用一个链表来存放每个结点的所有出边的结构，新的边从链表头插入，用于加快读图。
链表头数组：head[maxn]，head[u]指向一条包含了u的所有邻接边的链表
存所有边：E[maxm]
边序号：cnt
3. 模板
struct edge {
int to, w, next;
edge() {}
edge(int to, int w, int next) : to(to), w(w), next(next) {}
} E[maxm]; // 用链式向前星来存图
int cnt, head[maxn]; // head[u]指向一条包含了u的所有邻接边的链表
void addEdge(int u, int v, int w) {
E[cnt] = edge(v, w, head[u]); // 从链表的头部插入
head[u] = cnt ++; // 更改头指针
}
int main() {
......
fill(head, head + n + 1, -1); // 初始化链表头，-1表示链表尾部
cnt = 1; // cnt表示当前加入的边序号
while(m --) {
......
addEdge(u, v, w);
......
}
......
for(int i = head[u]; ~i; i = E[i].next) { // 遍历u的所有出边的方法
int v = E[i].to, w = E[i].w;
......
}
}4. 例题
Poj-3159：https://blog.nowcoder.net/n/4ab5d9ec4f3945829d259dc8c23dc5fa
五、判断二分图
1. 定义
判断一个图是否为二分图。
2. 解析
- 通过 染色法 实现。
用 1 和 -1 两种颜色给图的点染色，用col[maxn]来存放点的颜色, 0 表示还没染色。 - 若无法相间染色，则不是二分图，否则是。
3. 模板
bool dye(int u, int color){
col[u] = color; // 先染色
for(int v : G[u]){
if(!col[v] && !dye(v, -color)) return 0; // 下一个点没染色 就染上不同色，染不上则失败
else if(col[v] == color) return 0; // 若下一个点染了色且和当前点颜色相同， 则必不是二分图
}
return 1;
}
int main() {
......
bool ok = 1; // 是否是二分图
for(int i = 1; ok && i <= n; i ++) {
if(!col[i] && !dye(i, 1)) ok = 0;
}
......
}全原创
京公网安备 11010502036488号