第11章图论-part01，深搜和广搜在图这种数据结构上的应用。
1. 图论理论基础
1.1 连通性
连通图：在无向图中，任何两个节点都是可以到达的。
强连通图：在有向图中，任何两个节点是可以相互到达的。
连通分量：在无向图中的极大连通子图称之为该图的一个连通分量。
强连通分量：在有向图中的极大强连通子图称之为该图的一个连通分量。
1.2 图的构造
如何用代码表示一个图呢？主要有三种方式：朴素存储、邻接表和邻接矩阵。
1.2.1 朴素存储
名字是自创的，这种存储方式就是将所有边存下来，可以用数组、map或者类来存储。
优点是直观，节点之间的关系很容易展现；缺点是如果想知道两个节点之间是否存在边，需要把存储空间整个枚举一遍。
1.2.2 邻接矩阵
邻接矩阵使用二维数组来表示图结构，并且从节点的角度来表示图，有多少节点就申请多大的二维数组。
有向图和无向图的邻接矩阵，数组元素表示上有所区别，例如：
grid[2][5] = 6，表示节点2 连接 节点5为有向图，节点2指向节点5，边的权值为6。- 无向图如果想表示节点2和节点5之间相互连通，则对称的有
grid[2][5] = 6、grid[5][2] = 6。
优点：
- 检查任意两个顶点间是否存在边的操作非常快。
- 适合稠密图，空间利用率高。
缺点：
- 遍历边的时候需要遍历整个n*n矩阵，造成时间浪费。
- 不适合稀疏图，二维数组过大，造成空间浪费。
1.2.3 邻接表
邻接表使用数组+链表的方式来表示图结构，从边的数量来表示图，有多少边才会申请对应大小的链表。
优点：
- 对于稀疏图的存储，只需要存储边，空间利用率高。
- 遍历节点连接情况相对容易。
缺点：
- 检查任意两个节点之间是否存在边，效率相对较低，需要O(V)时间，V表示某节点连接其他节点的数量。
- 实现相对复杂，不易理解。
1.3 图的遍历方式
基本是两大类：
在讲解二叉树章节的时候，就已经讲过这两种遍历方式，例如二叉树的递归遍历，是dfs在二叉树上的遍历方式。
dfs和bfs是一种搜索算法，可以在不同的数据结构上进行搜索，在二叉树章节里是在二叉树这样的数据结构上搜索。而在图论章节，则所在图（邻接表或者邻接矩阵）上进行搜索。
2. 深搜理论基础
2.1 dfs搜索过程
关键就2点：
- 搜索方向，是认准一个方向搜索，直到碰壁（到达终点或之前已访问过的节点）之后再换方向。
- 换方向是指撤销最近的一次操作，改为节点链接的下一个路径，这是回溯的过程。
dfs的过程，其实就是回溯算法，dfs的代码框架如下：
1
2
3
4
5
6
7
8
9
10
11
12
| void dfs(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本节点所连接的其他节点) {
处理节点;
dfs(图，选择的节点);
回溯，撤销处理结果
}
}
|
2.2 深搜三部曲
深搜三部曲：
- 确定递归函数的参数
- 确定终止条件
- 处理目前搜索节点出发的路径
总之，和之前的回溯算法、递归三部曲很类似啊，只不过是用在图结构的搜索上了，代码还是好写的。
98. 所有可达路径
1.1 解题分析
- 图的构造、结果的输出在ACM模式下都很重要，所以从本题开始所有图论的题目均采用ACM模式做题。
深搜三部曲：
- 确定递归函数的参数: 传入有向图（存储方式为邻接矩阵/邻接表）、当前遍历到的节点x、终止节点n；全局变量，一维列表path，以及结果集result。
- 确定终止条件: 遍历到终止节点，收割结果存入结果集，并结束递归。
- 处理目前搜索节点出发的路径: for循环横向遍历，从x出发指向的节点，递归负责纵向遍历，并配合回溯使用。
1.2 解题小结
- 邻接矩阵（图存储），写的时候注意静态main方法，dfs和全局变量都要加static修饰符。
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
| import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
static List<Integer> path = new ArrayList<>();
static List<List<Integer>> results = new ArrayList<>();
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[][] graph = new int[n + 1][n + 1];
while (m-- > 0) {
int s = scanner.nextInt();
int t = scanner.nextInt();
graph[s][t] = 1;
}
path.add(1);
dfs(graph, 1, n);
if (results.isEmpty()) System.out.println(-1);
for (List<Integer> p : results) {
for (int i = 0; i < p.size() - 1; i++) {
System.out.print(p.get(i) + " ");
}
System.out.println(p.get(p.size() - 1));
}
}
private static void dfs(int[][] graph, int x, int n) {
if (x == n) {
results.add(new ArrayList<>(path));
return;
}
for (int i = 1; i <= n; i++) {
if (graph[x][i] == 1) {
path.add(i);
dfs(graph, i, n);
path.remove(path.size() - 1);
}
}
}
}
|
- 邻接表（图存储），这次定义的是数组+链表的
List<LinkedList<Integer>> graph。
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
| import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
public class Main {
static List<Integer> path = new ArrayList<>();
static List<List<Integer>> results = new ArrayList<>();
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
List<LinkedList<Integer>> graph = new ArrayList<>(n + 1);
for (int i = 0; i <= n; i++) {
graph.add(new LinkedList<>());
}
while (m-- > 0) {
int s = scanner.nextInt();
int t = scanner.nextInt();
graph.get(s).add(t);
}
path.add(1);
dfs(graph, 1, n);
if (results.isEmpty()) System.out.println(-1);
for (List<Integer> p : results) {
for (int i = 0; i < p.size() - 1; i++) {
System.out.print(p.get(i) + " ");
}
System.out.println(p.get(p.size() - 1));
}
}
private static void dfs(List<LinkedList<Integer>> graph, int x, int n) {
if (x == n) {
results.add(new ArrayList<>(path));
return;
}
for (int i : graph.get(x)) {
path.add(i);
dfs(graph, i, n);
path.remove(path.size() - 1);
}
}
}
|
4. 广搜理论基础
4.1 广搜的使用场景
广搜的搜索方式适合于解决两个点之间的最短路径问题。因为广搜是从起点出发，以起始点为中心一圈一圈进行搜索，一旦遇到终点，记录之前走过的节点就是一条最短路。
当然，也有一些问题的特征是不涉及具体的遍历方式，只要能把相邻且相同属性的节点标记上就行。例如岛屿问题，深搜和广搜都可以解决。
其实在二叉树章节的层序遍历中，我们也讲过一次广搜，相当于是广搜在二叉树这种数据结构上的应用。这次则从图论的角度上再详细讲一次广度优先遍历。
4.2 广搜的过程
BFS具体是怎么一圈一圈来搜呢？我们用一个方格地图，假如每次搜索的方向为上下左右（不妨含斜上方），那么给出一个start起始位置，BFS就是从四个方向走出第一步。如果加上一个end终止位置，那么使用BFS的搜索过程如图所示：
4.3 代码框架
一圈一圈的搜索过程，放在什么容器中实现？
我们仅需要一个容器，能保存我们要遍历过的元素就可以，那么用队列，还是用栈、数组，都是可以的。用队列的话，就是能保证每一圈是一个方向去转，例如统一顺时针或逆时针。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1};
void bfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y) {
queue<pair<int, int>> que;
que.push({x, y});
visited[x][y] = true;
while(!que.empty()) {
pair<int ,int> cur = que.front(); que.pop();
int curx = cur.first;
int cury = cur.second;
for (int i = 0; i < 4; i++) {
int nextx = curx + dir[i][0];
int nexty = cury + dir[i][1];
if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;
if (!visited[nextx][nexty]) {
que.push({nextx, nexty});
visited[nextx][nexty] = true;
}
}
}
}
|
5. 今日收获
- 知识点和前面学过的回溯算法、二叉树的递归遍历、二叉树的层序遍历连起来了，学起来还行。
- 学习时长：3.5小时