图第一讲
图论是计算机科学中非常重要也非常有趣的一部分，在日常生活中也有广阔的应用场景。
本章主要关注图的搜索，首先来看图的定义。
定义
图是由若干顶点E和连接顶点的边V组成，定义一张图一般使用邻接表或者邻接矩阵，本文统一使用邻接表。
对于边只用来连接两个定点，没有明确方向的，称为无向图，后续图中顶点都用直线连接。
相对应边有方向的，称为有向图，图中顶点用带方向的箭头连接。
首先看一个无向图及其表示。
可以看到有3个顶点(0,1,2)和三条边，邻接表是这样的。
可以看到邻接表本质上是一个二维数组，我们用List<List
深度优先搜索
这里我们默认大家对深度优先搜索有一定了解，我们直接从题目入手。
岛屿数量
给定一个二维矩阵，只包含'1'(陆地)和'0'(水)，计算所有的岛屿数量。
岛屿被水包围，岛屿都由水平和垂直方向上相邻的陆地连接而成，矩阵外的部分都是水。
上图中就有3个岛屿，我们可以使用三种方式来求解
- 深度遍历，每次搜索上下左右四个方向的未遍历到的节点，单次遍历到的节点属于一个岛屿
- 广度遍历，和深度遍历类似，只是每次同时向四个方向扩展
- 并查集，每个连通分量就是一个岛屿
我们展示方法一和三的代码
// https://leetcode.cn/problems/number-of-islands/submissions/612053722
char[][] grid;
boolean[][] visited;
public int numIslands(char[][] grid) {
boolean[][] visited = new boolean[grid.length][grid[0].length];
int count = 0;
this.grid = grid;
this.visited = visited;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == '1' && !visited[i][j]) {
count++;
search(i, j);
}
}
}
return count;
}
private void search(int i, int j) {
if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length) {
return;
}
if (visited[i][j] || grid[i][j] == '0') {
return;
}
visited[i][j] = true;
search(i + 1, j);
search(i - 1, j);
search(i, j + 1);
search(i, j - 1);
}
注意对坐标和是否已访问的检查是在进入无效坐标之后进行的，也可以在调用search之前检查。
// https://leetcode.cn/problems/number-of-islands/submissions/612072522
private static class UnionFind {
int[] parent, size;
public UnionFind(char[][] grid) {
int m = grid.length, n = grid[0].length;
parent = new int[m * n];
size = new int[m * n];
for (int i = 0; i < parent.length; i++) {
parent[i] = i;
size[i] = grid[i / n][i % n] == '1' ? 1 : 0;
}
}
public int find(int i) {
while (parent[i] != i) {
i = parent[i];
}
return i;
}
public void union(int i, int j) {
int parentI = find(i), parentJ = find(j);
if (parentI == parentJ) {
return;
}
if (size[parentI] < size[parentJ]) {
size[parentJ] += size[parentI];
size[parentI] = 0;
parent[parentI] = parentJ;
} else {
size[parentI] += size[parentJ];
size[parentJ] = 0;
parent[parentJ] = parentI;
}
}
public int parts() {
int result = 0;
for (int i = 0; i < size.length; i++) {
if (size[i] != 0) {
result++;
}
}
return result;
}
}
private static final int[][] DIR = new int[][]{ {1, 0}, {0, 1}, {-1, 0}, {0, -1}};
public int numIslands(char[][] grid) {
int m = grid.length, n = grid[0].length;
UnionFind unionFind = new UnionFind(grid);
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '1') {
for (int k = 0; k < DIR.length; k++) {
int nextI = i + DIR[k][0], nextJ = j + DIR[k][1];
if (0 <= nextI && nextI < m && 0 <= nextJ && nextJ < n && grid[nextI][nextJ] == '1') {
unionFind.union(i * n + j, nextI * n + nextJ);
}
}
}
}
}
return unionFind.parts();
}
注意并查集中只有为陆地的节点size设为了1。
克隆图
给定某无向连通图的一个节点，返回该图的 深拷贝。
节点由值和邻居列表组成
class Node {
public int val;
public List<Node> neighbors;
}
我们可以用深度搜索，边遍历节点，边创建新节点，用Map记录老节点和新节点的映射。
关键问题在于，怎么添加邻居，可以不重复。
深度遍历时，每对相邻的节点会遇到两次，假设有a和b两个节点，
第一次是a遍历到未访问的b，第二次是b遍历到已访问的a，如果每次都添加邻居肯定会重复。
所以我们只在序号小的节点访问到序号大的节点时添加邻居。
// https://leetcode.cn/problems/clone-graph/submissions/612209043
public Node cloneGraph(Node node) {
if (node == null) {
return null;
}
Map<Node, Node> oldToNew = new HashMap<>();
dfs(node, oldToNew);
return oldToNew.get(node);
}
private void dfs(Node node, Map<Node, Node> oldToNew) {
if (oldToNew.containsKey(node)) {
return;
}
Node newNode = new Node(node.val);
oldToNew.put(node, newNode);
for (Node neighbor : node.neighbors) {
if (!oldToNew.containsKey(neighbor)) {
dfs(neighbor, oldToNew);
}
Node newNeighbor = oldToNew.get(neighbor);
if (node.val < neighbor.val) {
newNode.neighbors.add(newNeighbor);
newNeighbor.neighbors.add(newNode);
}
}
}
同理使用广度搜索也可以达到同样的效果。
除法求值
给定一个变量对数组 equations 和一个实数值数组 values，
其中equations[i] = [A,B] 表示 A / B = values[i]，A和B是表示一个变量的字符串。
另有数组queries作为问题，queries[j] = [C,D]表示需要求 C / D的值，C和D也是表示变量的字符串。
如果答案无法求解，返回-1.0，如果有不存在的变量，也返回-1.0。
输入：equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"]]
输出：[6.0,0.5,-1.0] (a / c = (a / b) * (b / c) = 6, b / a = 1 / (a / b) = 0.5, e未定义所以返回-1)
本题本质上是一个无向图中连通分量的问题，每个变量都是一个节点，每个等式是一条边，同一连通分量中的节点可以相除。
连通分量问题适合用并查集处理，每个节点额外存储一个值，表示find找到的点和自身相除的结果，
假设find(b)=a,find(c)=a，b / c = a / c / (a / b)。
// https://leetcode.cn/problems/evaluate-division/submissions/544066889
private static class UnionFind {
private int[] id, weight;
private double[] value;
public UnionFind(int len) {
id = new int[len];
weight = new int[len];
value = new double[len];
for (int i = 0; i < len; i++) {
id[i] = i;
weight[i] = 1;
value[i] = 1;
}
}
public int find(int i) {
while (id[i] != i) {
i = id[i];
}
return i;
}
public void union(int a, int b, double value) {
int groupA = find(a), groupB = find(b);
if (groupA == groupB) {
return;
}
int weightA = weight[groupA], weightB = weight[groupB];
if (weightA > weightB) {
id[groupB] = groupA;
weight[groupA] += weight[groupB];
this.value[groupB] = getValue(a) / getValue(b) * value;
} else {
id[groupA] = groupB;
weight[groupB] += weight[groupA];
this.value[groupA] = getValue(b) / getValue(a) / value;
}
}
public double getValue(int i) {
double result = 1;
while (id[i] != i) {
result *= value[i];
i = id[i];
}
return result;
}
}
public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
Map<String, Integer> varToIdx = new HashMap<>();
int idx = 0;
for (List<String> equation : equations) {
if (!varToIdx.containsKey(equation.get(0))) {
varToIdx.put(equation.get(0), idx++);
}
if (!varToIdx.containsKey(equation.get(1))) {
varToIdx.put(equation.get(1), idx++);
}
}
int varCount = varToIdx.size();
UnionFind uf = new UnionFind(varCount);
for (int i = 0; i < equations.size(); i++) {
List<String> equation = equations.get(i);
uf.union(varToIdx.get(equation.get(0)), varToIdx.get(equation.get(1)), values[i]);
}
double[] result = new double[queries.size()];
for (int i = 0; i < queries.size(); i++) {
List<String> querie = queries.get(i);
if (!varToIdx.containsKey(querie.get(0)) || !varToIdx.containsKey(querie.get(1))) {
result[i] = -1;
continue;
}
int idx1 = varToIdx.get(querie.get(0)), idx2 = varToIdx.get(querie.get(1));
int group1 = uf.find(idx1), group2 = uf.find(idx2);
if (group1 != group2) {
result[i] = -1;
} else {
result[i] = uf.getValue(idx2) / uf.getValue(idx1);
}
}
return result;
}
varToIdx存储变量名到节点序号的映射，求解节点未定义或不在一个连通分量内，则返回-1，
在同一个连通分量内，则对节点分别求值并相除。
当然用深度搜索也是可以的，找到两点间的路径就能求它们相除的值，题目保证路径唯一。
广度优先搜索
以下内容默认大家了解广度优先搜索的基本原理和使用。
腐烂的橘子
给定m x n网格grid，每个单元格有以下三个值之一：
· 0代表空白格
· 1代表新鲜橘子
· 2代表腐烂的橘子
每分钟，腐烂的橘子会传染周围四个方向的相邻橘子，使其腐烂。
求所有橘子腐烂的最小分钟数，如果不会都腐烂，返回-1。
如上图，使用🍊表示新鲜橘子，带下标i的橘子表示在第i分钟腐烂的橘子。
上图中所有橘子在第一分钟就都腐烂了，所以返回1。
本题可以通过广度优先搜索来处理，在每个单元格记录橘子腐烂的最小分钟，值为最小分钟数加二，以兼容0、1、2三个值。
以每个开始就腐烂的橘子a为起点作广度搜索，将周围橘子b的腐烂时间更新为\(min(time(a)+1,time(b))\)。
如果将整个网格的开始就腐烂的橘子作为起点都搜索完，如果仍有新鲜橘子，返回-1，否则返回找到的最大值-2。
如上图，执行三轮广度搜索，直到以右下角的腐烂橘子为起点搜索完，得到全部腐烂的最小时间为2。
private static final int[][] DIR = new int[][]{ {1, 0}, {-1, 0}, {0, 1}, {0, -1}};
public int orangesRotting(int[][] grid) {
int m = grid.length, n = grid[0].length;
boolean[][] visited = new boolean[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 2) {
bfs(i, j, visited, grid);
clear(visited);
}
}
}
int max = 2;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
return -1;
}
max = Math.max(max, grid[i][j]);
}
}
return max - 2;
}
private void bfs(int i, int j, boolean[][] visited, int[][] grid) {
int m = grid.length, n = grid[0].length;
Deque<int[]> queue = new ArrayDeque<>();
visited[i][j] = true;
queue.addLast(new int[]{i, j});
while (!queue.isEmpty()) {
int size = queue.size();
for (int k = 0; k < size; k++) {
int[] pair = queue.pollFirst();
int row = pair[0], col = pair[1];
for (int l = 0; l < DIR.length; l++) {
int nextI = row + DIR[l][0], nextJ = col + DIR[l][1];
if (isValid(nextI, nextJ, m, n) && grid[nextI][nextJ] != 0 && !visited[nextI][nextJ]) {
queue.addLast(new int[]{nextI, nextJ});
visited[nextI][nextJ] = true;
if (grid[nextI][nextJ] == 1) {
grid[nextI][nextJ] = 1 + grid[row][col];
} else {
grid[nextI][nextJ] = Math.min(grid[nextI][nextJ], 1 + grid[row][col]);
}
}
}
}
}
}
private void clear(boolean[][] visited) {
for (int i = 0; i < visited.length; i++) {
for (int j = 0; j < visited[0].length; j++) {
visited[i][j] = false;
}
}
}
private boolean isValid(int i, int j, int m, int n) {
return 0 <= i && i < m && 0 <= j && j < n;
}
单词接龙
在字典（单词列表） wordList 中，从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列：
· 序列中第一个单词是 beginWord 。
· 序列中最后一个单词是 endWord 。
· 每次转换只能改变一个字母。
· 转换过程中的中间单词必须是字典 wordList 中的单词。
给定两个长度相同但内容不同的单词 beginWord 和 endWord 和一个字典 wordList ，找到从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。
如果不存在这样的转换序列，返回 0。
输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
输出：5 (一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的长度 5。)
把每个单词视为一个点，问题就转换为 beginWord 到 endWord的最短路径问题，每个点间如果有路径的话长度为1，答案为长度+1。
问题在于怎么找出可相互转换的单词，一般方法是两两比较，如果不同字母只有一个，则可相互转换，复杂度为\(O(mn^2)\)，m为单词长度，n为字典大小。
还有一种更高效的方式，把每个单词扩展成m个通配符，以”hit”为例，扩展成[“*it”,”h*t”,”hi*“]三个单词，显然”hit”和这三个单词都是互相连接的(*表示任意单个字符)。
这样两个可转换的单词就通过通配符相互连接了，以”hit”和”hot”为例，如下图，两个节点通过”h*t”相连。
这样构造路径总的节点数膨胀为\((m+1)n\)，最差的情况下，每两个非通配符节点都相连，每条边都会构造一次，这样复杂度为\(O((m+1)n+n^2)\)，即两者的最大值，
而最好的情况下，没有节点互连，则复杂度为\(O((m+1)n)\)。
需要注意的是，路径上的通配符节点不计算在结果里。
// https://leetcode.cn/problems/word-ladder/submissions/540361326
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
int endWordIdx = -1;
int len = beginWord.length();
for (int i = 0; i < wordList.size(); i++) {
if (endWord.equals(wordList.get(i))) {
endWordIdx = i;
break;
}
}
if (-1 == endWordIdx) {
return 0;
}
int idx = 0;
Map<String, Integer> wordToIdx = new HashMap<>();
Map<Integer, String> idxToWord = new HashMap<>();
List<List<Integer>> edges = new ArrayList<>();
for (int i = 0; i <= wordList.size(); i++) {
String word = i == 0 ? beginWord : wordList.get(i - 1);
if (!wordToIdx.containsKey(word)) {
wordToIdx.put(word, idx);
idxToWord.put(idx++, word);
edges.add(new ArrayList<>());
}
int wordIdx = wordToIdx.get(word);
for (int j = 0; j < len; j++) {
String wildcard = word.substring(0, j) + '*' + word.substring(j + 1);
if (!wordToIdx.containsKey(wildcard)) {
wordToIdx.put(wildcard, idx);
idxToWord.put(idx++, wildcard);
edges.add(new ArrayList<>());
}
int wildcardIdx = wordToIdx.get(wildcard);
edges.get(wordIdx).add(wildcardIdx);
edges.get(wildcardIdx).add(wordIdx);
}
}
boolean[] visited = new boolean[wordToIdx.size()];
return bfs(0, wordToIdx.get(endWord), edges, visited, wordToIdx, idxToWord);
}
private int bfs(int from, int to, List<List<Integer>> edges, boolean[] visited, Map<String, Integer> wordToIdx, Map<Integer, String> idxToWord) {
int[] parent = new int[visited.length];
Deque<Integer> queue = new ArrayDeque<>();
queue.addLast(from);
visited[from] = true;
parent[from] = -1;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
int current = queue.pollFirst();
if (current == to) {
int count = 1;
int parentIdx = parent[current];
while (parentIdx != -1) {
boolean isWildcard = idxToWord.get(parentIdx).contains("*");
count += isWildcard ? 0 : 1;
parentIdx = parent[parentIdx];
}
return count;
}
for (int next : edges.get(current)) {
if (!visited[next]) {
queue.addLast(next);
visited[next] = true;
parent[next] = current;
}
}
}
}
return 0;
}