【数据结构】图

发表于2021-10-17更新于2022-03-02字数统计7.1k阅读时长49分阅读次数

图的数据结构

用 Graph 代表图的数据结构，其又由 Node 和 Edge 两种数据结构组成。

1
2
3
4
5
6
7
8
9
public class Graph {
    public HashMap<Integer, Node> nodes;
    public HashSet<Edge> edges;

    public Graph() {
        nodes = new HashMap<>();
        edges = new HashSet<>();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Node {
    public int value;
    public int in;
    public int out;
    public ArrayList<Node> nexts;
    public ArrayList<Edge> edges;

    public Node(int value) {
        this.value = value;
        this.in = 0;
        this.out = 0;
        nexts = new ArrayList<>();
        edges = new ArrayList<>();
    }
}
1
2
3
4
5
6
7
8
9
10
11
public class Edge {
    public int weight;
    public Node from;
    public Node to;

    public Edge(int weight, Node from, Node to) {
        this.weight = weight;
        this.from = from;
        this.to = to;
    }
}

图结构的转换

将邻接数组结构的表达形式转换为我们规定的结构：

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
public class GraphGenerator {
    public Graph graphGenerator(Integer[][] matrix) {
        Graph graph = new Graph();
        for (int i = 0; i < matrix.length; i++) {
            Integer weight = matrix[i][0];
            Integer from = matrix[i][1];
            Integer to = matrix[i][2];

            // 如果图中已经有了当前节点，则不再加入
            if (!graph.nodes.containsKey(from)) {
                graph.nodes.put(from, new Node(from));
            }
            if (!graph.nodes.containsKey(to)) {
                graph.nodes.put(to, new Node(to));
            }

            // 不能直接根据传入的矩阵创建出节点，而应该从图的Set集合中获取，这样能保证不重复
            Node fromNode = graph.nodes.get(from);
            Node toNode = graph.nodes.get(to);

            // 创建新边
            Edge newEdge = new Edge(weight, fromNode, toNode);

            // 更新节点里的出度入度信息和顶点集、出边集信息
            // 顶点集只包含当前节点指向的顶点，出边集只包含从当前顶点出去的边（当前顶点为弧尾）
            fromNode.out++;
            toNode.in++;
            fromNode.nexts.add(toNode);
            fromNode.edges.add(newEdge);

            graph.edges.add(newEdge);
        }
        return graph;
    }
}

图的遍历

广度优先遍历（BFS）

图的广度优先遍历类似于树的层次遍历。

思想：把当前顶点的相邻顶点都遍历完，再遍历其相邻顶点的相邻顶点（不能重复遍历）。

  • 首先准备一个队列存储当前节点的所有相邻顶点（不重复添加）
  • 再准备一个 HashSet 存储每一个遍历过的顶点（保证不重复遍历）。
  • 每次弹出队首顶点，然后将其相邻顶点一一入队（要先判断是否在 HashSet 中已存在）
  • 按照该顺序遍历道直到队列为空，即完成了图的广度优先遍历

示意图：

img

代码：

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
public class BFS {
    public void bfs(Node node) {
        if (node == null) {
			return;
		}
        
        Queue<Node> queue = new LinkedList<>();
        Set<Node> set = new HashSet<>();

        queue.add(node);
        set.add(node);

        while (!queue.isEmpty()) {
            Node curr = queue.poll();

            // 来到了当前顶点，进行一些操作
            // ....
            System.out.println(curr.value);

            // 将当前顶点的相邻节点都加入到 set 和队列中（不能重复包含）
            // for (int i = 0; i < curr.nexts.size(); i++) {
            //     if (!set.contains(curr.nexts.get(i))) {
            //         set.add(curr.nexts.get(i));
            //         queue.add(curr.nexts.get(i));
            //     }
            // }
            for (Node next : curr.nexts) {
                if (!set.contains(next)) {
                    set.add(next);
                    queue.add(next);
                }
            }
        }
    }
}

深度优先遍历

图的深度优先遍历类似于树的前序遍历。

思想：选择当前顶点的某一个顶点进行遍历，一直到底，然后返回时再遍历其他未遍历过的顶点。

  • 首先准备一个栈结构用于存储遍历过程中的顶点
  • 再准备一个 HashSet 用于记录当前顶点是否已经被遍历过
  • 从给定顶点开始，先将其入栈入 Set，并打印
  • 栈结构不为空就一直进行循环：
    • 弹出栈顶顶点，判断其是否有某个相邻顶点还未被遍历过（体现在 Set 中不包含该顶点）
    • 如果有，则先将栈顶顶点入栈，目的是为了在前序遍历到底后往回遍历时能够再沿着原先入栈的顺序遍历回去。然后将当前顶点入栈，入 Set，并打印
    • 如果没有，则不再将当前顶点入栈，说明当前顶点以下的顶点都遍历完了（类比与树结构中当前顶点的子树都遍历完了）
  • 一直到栈结构为空，说明所有顶点都不重复地遍历了一次。

打印操作都是在某一个节点入 Set 后操作的，代表刚遍历到他就打印。

示意图：

图的遍历|深度优先遍历- 掘金

将栈顶节点弹出后再压入栈的原因就是在上图中访问到了 H 顶点以后（到底了），再往回遍历时能够根据栈中保存的其上面所有顶点的顺序，逐个遍历回去。

代码：

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
public class DFS {
    public void dfs(Node node) {
        if (node == null) {
            return;
        }

        Stack<Node> stack = new Stack<>();
        Set<Node> set = new HashSet<>();
        // 根顶点入栈
        stack.push(node);
        set.add(node);

        // 第一次来到根顶点
        System.out.println(node.value);

        while (!stack.isEmpty()) {
            // 弹出栈顶的顶点
            Node curr = stack.pop();
            // 逐个判断当前顶点的相邻顶点是否还有没有遍历过的（体现在 Set 中不存在的）
            // 如果没遍历过，就先将当前顶点再次压栈，然后再将该邻居节点压栈
            for (Node next : curr.nexts) {
                if (!set.contains(next)) {
                    // 如果当前顶点有某一个邻居顶点还没遍历过，就先将当前顶点入栈
                    // 将当前顶点压栈的目的是为了能记录当前顶点，
                    // 在前序遍历到底后往回遍历时能够再沿着原先入栈的顺序遍历回去，
                    // 从而不遗漏的遍历所有顶点（因为还要遍历回去找其他未遍历过的顶点，如果不记录当前顶点就找不回去了）
                    stack.push(curr);
                    stack.push(next);
                    set.add(next);
                    // 每次都是往 Set 中存储后打印（代表第一次遍历到）
                    System.out.println(next.value);
                    break;
                }
            }
        }
    }
}

图的拓扑排序

有向无环图的排序——拓扑排序

在图论中，拓扑排序（Topological Sorting） 是一个有向无环图（DAG, Directed Acyclic Graph） 的所有顶点的线性序列。且该序列必须满足下面两个条件：

  1. 每个顶点出现且只出现一次。
  2. 若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。

有向无环图（DAG）才有拓扑排序，非 DAG 图没有拓扑排序一说。

image-20211104183243762

DAG 的拓扑排序流程：

  • 找出图中入度为0的顶点；
  • 依次在图中删除这些顶点（并将与其关联的边删掉），再找出新的入度为0的顶点；
  • 然后再删除这些顶点并重复该过程，直至删除所有顶点，即完成拓扑排序

图示：

img

代码：

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
public class TopologySort {
    public List<Node> topologySort(Graph graph) {
        if (graph == null) {
            return null;
        }

        List<Node> list = new ArrayList<>();
        Queue<Node> queue = new LinkedList<>();
        for (Node node : graph.nodes.values()) {
            // 如果当前顶点入度为 0，则加入队列
            if (node.in == 0) {
                queue.add(node);
                list.add(node);
            }
        }

        // 队首顶点依次出队，并将其指向的顶点的入度减一
        while (!queue.isEmpty()) {
            Node curr = queue.poll();
            for (Node next : curr.nexts) {
                next.in--;
                 // 减一后判断：如果入度为0，则该顶点加入到队列中
                if (next.in == 0) {
                    queue.add(next);
                    list.add(next);
                }
            }
        }

        return list;
    }
}

生成图的最小生成树

两种算法可用于生成图的最小生成树，返回的结果为 Set<Edge>：

  • Kruskal 算法：以边为目标。按照边的权重值大小依次将权重较小的边合并起来。时间复杂度为 O(e * loge)，其中 e 为边数
  • Prim 算法 ：以顶点为目标。从任意顶点出发，不断将当前访问过的顶点集中的最小权重边合并到最小生成树集合中。时间复杂度为 O(n^2)，其中 n 为顶点数

一个是从边的角度出发，按照权重值从小到大的顺序遍历边并加入到结果集中；一个是从顶点的角度出发，每一次都从当前访问过的顶点集中找出最小权重边添加到结果集中。

Kruskal 算法主要针对边来展开，边数少的时候效率非常高，所以对于稀疏图有很大的优势；Prim 算法对于稠密图，即边数非常多的情况会更好一些。

Kruskal 算法

算法思想：以边为目标。先将边按照权重值从小到大进行排序。然后从最小权重值的边开始，逐个组合边，一次加入一条边（要保证新加入的边的两个顶点必须不在同一个集合中），直至形成最小生成树。

算法流程：

  • 将每个顶点分别创建其所在的并查集（开始时所有顶点都是独立的，从属于不同的集合中）
  • 将所有边加入到优先级队列中，按照边的权重值从小到大进行排序
  • 遍历该队列，从最小权重值的边开始遍历每一个边，判断该边两端的顶点是否是同一个集合：
    • 若是，说明这两个顶点已经在一个连通树上了，因此当前边是多余的，不需要添加
    • 若不是，说明这两个顶点还没不在一个连通树上，则将当前边加入到结果集中
  • 该队列遍历完成后，即生成了最小生成树

在组合边的过程中可能会将两片原先完全不连通的顶点集合组合起来，即一片一片的组合。Prim 算法则不会一片一片的添加边，而是一次添加一个点所在的边。

代码：

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
package com.zhao;

import java.util.*;

public class Kruskal {
    // Union-Find Set
    public static class UnionFind {
        private HashMap<Node, Node> fatherMap;
        private HashMap<Node, Integer> rankMap;

        public UnionFind() {
            fatherMap = new HashMap<Node, Node>();
            rankMap = new HashMap<Node, Integer>();
        }

        private Node findFather(Node n) {
            Node father = fatherMap.get(n);
            if (father != n) {
                father = findFather(father);
            }
            fatherMap.put(n, father);
            return father;
        }

        public void makeSets(Collection<Node> nodes) {
            fatherMap.clear();
            rankMap.clear();
            for (Node node : nodes) {
                fatherMap.put(node, node);
                rankMap.put(node, 1);
            }
        }

        public boolean isSameSet(Node a, Node b) {
            return findFather(a) == findFather(b);
        }

        public void union(Node a, Node b) {
            if (a == null || b == null) {
                return;
            }
            Node aFather = findFather(a);
            Node bFather = findFather(b);
            if (aFather != bFather) {
                int aFrank = rankMap.get(aFather);
                int bFrank = rankMap.get(bFather);
                if (aFrank <= bFrank) {
                    fatherMap.put(aFather, bFather);
                    rankMap.put(bFather, aFrank + bFrank);
                } else {
                    fatherMap.put(bFather, aFather);
                    rankMap.put(aFather, aFrank + bFrank);
                }
            }
        }
    }

    public static class EdgeComparator implements Comparator<Edge> {
        // 返回正整数代表 o1 大于 o2
        // 返回负整数代表 o1 小于 o2
        @Override
        public int compare(Edge o1, Edge o2) {
            return o1.weight - o2.weight;
        }
    }

    public Set<Edge> kruskalMST(Graph graph) {
        UnionFind unionFind = new UnionFind();
        unionFind.makeSets(graph.nodes.values());

        // 所有边先加到优先队列中，按照定制排序器排序，权值小的放前面
        PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(new EdgeComparator());
        for (Edge edge : graph.edges) {
            priorityQueue.add(edge);
        }

        Set<Edge> result = new HashSet<>();
        while (!priorityQueue.isEmpty()) {
            Edge edge = priorityQueue.poll();
            // 如果当前边的两个顶点不在一个集合中，就将当前边加入到结果边集中，
            // 并且将这两个顶点所在集合合并
            if (!unionFind.isSameSet(edge.from, edge.to)) {
                result.add(edge);
                unionFind.union(edge.from, edge.to);
            }
        }
        return result;
    }
}

其中，priorityQueue 是一个小根堆结构。

Prim 算法

算法思路：以顶点为目标。从任意顶点出发，不断将当前访问过的顶点集中的最小权重边合并到最小生成树集合中。

算法流程：

  • 创建一个优先级队列用于在遍历过程中动态存储当前访问过的顶点集所连接的边
  • 创建一个 HashSet 保存最小生成树上的顶点集 nodesSet，用于判断当前顶点是否已经被加入到生成树中，防止重复添加顶点导致闭环
  • 从任意一个顶点出发，先将其添加到顶点集 nodesSet 中，然后将当前顶点所连接的所有边都加入到优先级队列中。将会在接下来从这些边中找到最小权重边
  • while 循环遍历优先级队列：
    • 获取当前边集中的最小权重边
    • 获取该边的 to 顶点。该边已经在之前加入到了优先级队列中，说明该边的 from 点已经加入到了顶点集 nodesSet 中。此时获取 to 顶点是将其看为种子选手（因为该顶点和 from 顶点组成的边的权重值在当前阶段最小），如果其满足条件就可以加入到最小生成树中（条件是该点之前没被加入到树中过）
    • 判断该 to 顶点是否在访问过的顶点集 Set 中，若在，则不再添加当前边（否则会闭环），若不在，则添加到顶点集 nodesSet 中
    • 若在，则将当前边的 to 顶点（该顶点已被判断成功加入到生成树中）连接的边都加入到队列中。这些边将在接下来的 while 循环中继续找出最小权重边。进行判断+合并
    • 重复进行上述操作，直到队空即完成了正科最小生成树的构建

该过程只需要一个哈希表 nodesSet 存储已添加到最小生成树中的顶点，不需要额外的结构。不像 Kruskal 算法还需要并查集结构判断两个集合是否相同。这是因为 Kruskal 算法是以边为目标，每次添加一条边，可能会造成一片顶点合并一片顶点，因此要判断两片顶点是否重合。

P 算法从任意一个点出发，寻找最小权重的边（之所以从任意一个点是因为所有点最后总归是要加入到树中的，所以从哪个点出发都一样，反正最后都得加入到树中，总归是要加入该顶点所连接的最小权重的边）

每次新遍历到一个顶点，就将其连接的边加入到优先级队列中，接下来就会获取该队列里的最小权重边，也对应了开始时从任意一个点出发，因为每个顶点都会经历该过程：从该顶点连接的边中挑选一个最小权重边加入到最小生成树中（每个顶点都会从其连接的边中挑出来一条，所以谁先谁后无所谓）

代码：

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
public class Prim {
    public static class EdgeComparator implements Comparator<Edge> {
        @Override
        public int compare(Edge e1, Edge e2) {
            return e1.weight - e2.weight;
        }
    }

    public Set<Edge> prim(Graph graph) {
        // 保存组成最小生成树的边集
        Set<Edge> result = new HashSet<>();
        // 保存最小生成树上的顶点集，用于判断当前顶点是否已经被加入到生成树中，防止重复添加顶点导致闭环
        Set<Node> nodesSet = new HashSet<>();
        // 优先级队列用于在遍历过程中动态存储当前访问过的顶点集所连接的边
        PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(new EdgeComparator());

        // 该 for 循环的目的是防止图森林的存在：即多个互不相连的图组成的一个森林
        // 如果题目表示是连通图，则可以省略该步骤
        for (Node node : graph.nodes.values()) {
            // 防止重复添加
            // node 是随便选择的一个初始点
            if (!nodesSet.contains(node)) {
                nodesSet.add(node);
                // 将当前顶点所连接的所有边都加入到优先级队列中
                // 将会在接下来从这些边中找到最小权重边 
                for (Edge edge : node.edges) {  // 由一个点解锁所有相连的边
                    priorityQueue.add(edge);
                }

                while (!priorityQueue.isEmpty()) {
                    // 获取当前边集中的最小权重边
                    Edge currEdge = priorityQueue.poll(); // 弹出解锁的边中，最小的边
                    // 当前边的 currEdge.to 为 node 顶点指向的 to 顶点 
                    // 该顶点就是种子选手，如果其满足条件就可以加入到最小生成树中（条件是该点之前没被加入到树中过）
                    Node toNode = currEdge.to;  // 可能的一个新点（种子选手）
                    // 判断其是否在访问过的点集 Set 中，若在，则不再添加当前边（否则会闭环），若不在，则添加
                    if (!nodesSet.contains(toNode)) {  // 如果不包含，则该种子选手就是新点，可以加入树中
                        nodesSet.add(toNode);
                        result.add(currEdge);
                        // 将当前边的 to 顶点（该顶点已被判断成功加入到生成树中）连接的边都加入到队列中
                        // 这些边将在接下来的 while 循环中继续找出最小权重边。进行判断+合并
                        for (Edge nextEdge : toNode.edges) {
                            priorityQueue.add(nextEdge);
                        }
                    }
                }
            }
        }

        return result;
    }
}

Dijkstra 算法

https://www.cnblogs.com/goldsunshine/p/12978305.html#dijkstra-算法思想介绍

适用范围：没有权值累加和为负数的环。

如下图是一个多节点，多路径图。下面以该图为例子讲解Dijkstra算法寻找最短路径的过程。
img

以A点为起始点，求A点到其他点 B C D E F 5个点的最短路径，最后得出A到其他点的最短路径。

因为要求A到其他5个点的最短距离，所以构造一个数组记录A到B C D E F 5个点的路径距离。约定：

  • 如果A能够直接达到节点，则使用路径长度即权值作为其距离
  • 如果A节点不能直接达到节点则使用无穷大表示A到该点距离。
  • 任何点到自身都为0

那么在最开始时，A点到图中所有点的距离数组如下：

A B C D E F
0 10 无穷大 4 无穷大 无穷大

Dijkstra 的算法思想是：从以上最短距离数组中每次选择一个最近的点，将其作为下一个点，然后重新计算从起始点经过该点到其他所有点的距离，更新最短距离数据。已经选取过的点就是确定了最短路径的点，不再参与下一次计算。

算法流程：

代码：

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
public class Dijkstra {
    public Map<Node, Integer> dijkstra(Node head) {
        // 保存从指定出发点head到其他点的距离，将在遍历时不断更新（就是那张距离数组表）
        //    key: 顶点
        //    value: head到该顶点的距离
        Map<Node, Integer> distanceMap = new HashMap<>();
        // 设置 head 到自己的距离为 0
        distanceMap.put(head, 0);
        // 保存已经锁定的顶点（已经确定的，不会再改变距离大小的顶点）
        Set<Node> selectedNodes = new HashSet<>();

        // 先找出初始状态的最小距离点：就是head本身
        Node minDistanceNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes);
        while (minDistanceNode != null) {
            // 将head加入到selectedSet中
            // distance为head到当前顶点的距离
            Integer distance = distanceMap.get(minDistanceNode);
            // 将当前minDistanceNode的相邻顶点都加入到distanceMap中
            for (Edge edge : minDistanceNode.edges) {
                Node toNode = edge.to;
                // 如果当前边的to顶点还没被锁定，则加入到distance中
                if (!distanceMap.containsKey(toNode)) {
                    // 第一次计算出从head到当前顶点的值
                    distanceMap.put(toNode, distance + edge.weight);
                } else {
                    // 更新最小值
                    // distanceMap.get(toNode) 是之前其他顶点更新的值，是暂定的
                    // 可能随着遍历其他顶点的过程而更新
                    distanceMap.put(toNode, Math.min(distanceMap.get(toNode),
                           distance + edge.weight));
                }
            }

            selectedNodes.add(minDistanceNode);
            minDistanceNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes);
        }
        return distanceMap;
    }

    // 用于从distanceMap中查找到head的距离最小，且还没有锁定的顶点（不在selectedNodes中）
    // distanceMap中保存的就是到head的距离值，selectedNodes中保存的是已经锁定的顶点（已经确定的，不会再改变距离大小的顶点）
    public Node getMinDistanceAndUnselectedNode(Map<Node, Integer> distanceMap, Set<Node> selectedNodes) {
        // 遍历distanceMap中的每个顶点，找出最小的距离值
        int minDistance = Integer.MAX_VALUE;
        Node minNode = null;
        for (Map.Entry<Node, Integer> entry : distanceMap.entrySet()) {
            Node node = entry.getKey();
            Integer distance = entry.getValue();

            // 注意，需要满足两个条件：
            //   1. 当前顶点还未锁定：不在selectedNodes中
            //   2. 当前顶点距离head的距离小于当前最小值
            if (!selectedNodes.contains(node) && distance < minDistance) {
                minDistance = distance;
                minNode = node;
            }
        }
        // 将找到的最短距离的顶点返回
        return minNode;
    } 
}

图的常见题目

岛屿问题

200. 岛屿数量：给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。此外，你可以假设该网格的四条边均被水包围。

示例 1：

1
2
3
4
5
6
7
输入：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出：1

思路：使用深度优先遍历，对图中的每一个元素都进行深度优先遍历，将其连通的元素都设置为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
public int numIslands(char[][] grid) {
    if (grid == null || grid.length < 1) {
        return 0;
    }

    int count = 0;

    // 遍历每一个元素，进行infect传染操作，将其连通的元素都设置为2
    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[0].length; j++) {
            if (grid[i][j] == '1') {
                // 如果当前位置为1，说明是一个岛屿，开始传染
                infect(grid, i, j, grid.length, grid[0].length);
                count++;
            }
        }
    }
    return count;
}

// M：矩阵的行数，N：矩阵的列数
// i：当前行，j：当前列
public void infect(char[][] grid, int i, int j, int M, int N) {
    // 如果当前位置超出矩阵范围，或值不为'1'，则代表当前位置不是岛屿
    if (i < 0 || i >= M || j < 0 || j >= N || grid[i][j] != '1') {
        return;
    }

    // 如果当前位置是岛屿，则将其设置为2
    grid[i][j] = '2';

    // 然后递归传染上下左右位置
    infect(grid, i - 1, j, M, N); // 上
    infect(grid, i + 1, j, M, N); // 下
    infect(grid, i, j - 1, M, N); // 左
    infect(grid, i, j + 1, M, N); // 右
}

矩阵中的路径

矩阵中的路径：给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

例如，在下面的 3×4 的矩阵中包含单词 “ABCCED”（单词中的字母已标出）。

image-20211209154348176

思路：本问题是典型的矩阵搜索问题，可使用 深度优先搜索（DFS）+ 剪枝 解决。

  • 深度优先搜索： 可以理解为暴力法遍历矩阵中所有字符串可能性。DFS 通过递归，先朝一个方向搜到底，再回溯至上个节点，沿另一个方向搜索，以此类推。
  • 剪枝： 在搜索中，遇到 这条路不可能和目标字符串匹配成功 的情况（例如：此矩阵元素和目标字符不同、此元素已被访问），则应立即返回，称之为 可行性剪枝 。
image-20211209154502018

DFS 解析：

  • 递归参数： 当前元素在矩阵 board 中的行列索引 i 和 j ，当前目标字符在 word 中的索引 k 。
  • 终止条件：
    • 返回 false： (1) 行或列索引越界 或 (2) 当前矩阵元素与目标字符不同 或 (3) 当前矩阵元素已访问过 （ (3) 可合并至 (2) ）
    • 返回 true： k = len(word) - 1 ，即字符串 word 已全部匹配。

递推工作：

  1. 标记当前矩阵元素： 将 board[i][j] 修改为 空字符 '' ，代表此元素已访问过，防止之后搜索时重复访问。
  2. 搜索下一单元格： 朝当前元素的 上、下、左、右 四个方向开启下层递归，使用 或 连接 （代表只需找到一条可行路径就直接返回，不再做后续 DFS ），并记录结果至 res 。
  3. 还原当前矩阵元素： 将 board[i][j] 元素还原至初始值，即 word[k] 。

img

注意：此类图的 DFS 问题都需要遍历图中的每一个元素，从其开始进行深度优先遍历。同时需要使用 || 的短路原则，缩短搜索时间。

代码：

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
public boolean exist(char[][] board, String word) {
    if (board == null || board.length < 1 || word == null || board.length * board[0].length < word.length()) {
        return false;
    }
    char[] words = word.toCharArray();
    // 图的dfs问题，都需要遍历图的每一个元素，判断从其出发能否找到匹配的字符
    // 类似于岛问题
    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[0].length; j++) {
            if (dfs(i, j, 0, board, words)) {
                return true;
            }
        }
    }
    return false;
}

// 换个思路：使用record无法处理这类问题，那么就可以修改原字符数组，将处理成功的设置为' '
// 那么再重复找时就会直接返回false不会重复查找
// 如果当前没成功，则其邻居再回来时发现又不满足等于curr的条件，还是会失败
public boolean dfs(int i, int j, int k, char[][] board, char[] words) {
    // 1. 越界，返回false
    if (i < 0 || i >= board.length || j < 0 || j >= board[0].length) {
        return false;
    }
    // 2. 如果当前位置元素值不等于目标值，返回false
    if (board[i][j] != words[k]) {
        return false;
    } 
    // ps：该情况其实无需额外判断，已经和上一条合并了
    // 3， 如果当前位置已经搜索过，并且是成功的，代表当前分支重复访问了，返回false
    // if (board[i][j] == ' ') {
    //     return false;
    // }

    // 4. 如果当前元素等于目标值，且如果k到底了，说明匹配完毕，返回true
    if (k == words.length - 1) {
        return true;
    }

    // 5. 如果当前位置还没搜索过，并且匹配当前word的字符
    // 先修改为' '防止其后的分支重复访问当前字符
    char tmp = board[i][j]; // 暂存一下在回溯完成后重新赋值给原数组
    board[i][j] = '\0';

    // 开始搜索
    // 使用 || 的短路原则，缩短搜索时间，否则如果第一个分支就成功，后面的分支就会多余搜索，浪费了大量时间
    boolean res = dfs(i + 1, j, k + 1, board, words) || dfs(i, j + 1, k + 1, board, words)
        || dfs(i - 1, j, k + 1, board, words) || dfs(i, j - 1, k + 1, board, words);
    // 恢复回去
    board[i][j] = tmp;
    // 四条搜索路线有一条为true即可代表当前路径搜索到了
    return res;
}

机器人的运动范围

剑指 Offer 13. 机器人的运动范围：地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0]的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？

注意机器人只能从[0,0]位置出发，所以不能使用for循环遍历每一个位置，和上一题还不一样（上一题可以从任意位置出发寻找目标字符串）

代码：

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
public int movingCount(int m, int n, int k) {
    int[][] record = new int[m][n];
    movingCountHelper(0, 0, m, n, k, record);
    return count;
}
public int count = 0;

public void movingCountHelper(int i, int j, int m, int n, int k, int[][] record) {
    // 如果超出了边界，返回
    if (i < 0 || i >= m || j < 0 || j >= n) {
        return;
    }
    // 如果当前坐标和超过了k，也直接返回
    if (!isValid(i, j, k)) {
        return;
    }
    // 当前格子已经访问过，则不在继续访问
    if (record[i][j] == 1) {
        return;
    }

    // 设置当前为访问过
    record[i][j] = 1;
    // 别忘了加一
    count++;
    movingCountHelper(i - 1, j, m, n, k, record);
    movingCountHelper(i, j - 1, m, n, k, record);
    movingCountHelper(i + 1, j, m, n, k, record);
    movingCountHelper(i, j + 1, m, n, k, record);
}

// return true：符合条件
public boolean isValid(int i, int j, int k) {
    int sum = 0;
    // 计算i与j的位数和
    while (i != 0) {
        sum += i % 10;
        i /= 10;
    }
    while (j != 0) {
        sum += j % 10;
        j /= 10;
    }
    return sum <= k;
}