图的数据结构
用 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)); } 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 中已存在)
按照该顺序遍历道直到队列为空,即完成了图的广度优先遍历
示意图:
代码:
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); 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(); for (Node next : curr.nexts) { if (!set.contains(next)) { stack.push(curr); stack.push(next); set.add(next); System.out.println(next.value); break ; } } } } }
图的拓扑排序
有向无环 图的排序——拓扑排序
在图论中,拓扑排序(Topological Sorting) 是一个有向无环图(DAG, Directed Acyclic Graph) 的所有顶点的线性序列。且该序列必须满足下面两个条件:
每个顶点出现且只出现一次。
若存在一条从顶点 A 到顶点 B 的路径,那么在序列中顶点 A 出现在顶点 B 的前面。
有向无环图(DAG)才有拓扑排序 ,非 DAG 图没有拓扑排序一说。
DAG 的拓扑排序流程:
找出图中入度为0的顶点;
依次在图中删除这些顶点(并将与其关联的边删掉),再找出新的入度为0的顶点;
然后再删除这些顶点并重复该过程,直至删除所有顶点,即完成拓扑排序
图示:
代码:
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()) { if (node.in == 0 ) { queue.add(node); list.add(node); } } while (!queue.isEmpty()) { Node curr = queue.poll(); for (Node next : curr.nexts) { next.in--; 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 { 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 > { @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 (Node node : graph.nodes.values()) { if (!nodesSet.contains(node)) { nodesSet.add(node); for (Edge edge : node.edges) { priorityQueue.add(edge); } while (!priorityQueue.isEmpty()) { Edge currEdge = priorityQueue.poll(); Node toNode = currEdge.to; if (!nodesSet.contains(toNode)) { nodesSet.add(toNode); result.add(currEdge); for (Edge nextEdge : toNode.edges) { priorityQueue.add(nextEdge); } } } } } return result; } }
Dijkstra 算法
https://www.cnblogs.com/goldsunshine/p/12978305.html#dijkstra-算法思想介绍
适用范围:没有权值累加和为负数的环 。
如下图是一个多节点,多路径图。下面以该图为例子讲解Dijkstra算法寻找最短路径的过程。
以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) { Map<Node, Integer> distanceMap = new HashMap<>(); distanceMap.put(head, 0 ); Set<Node> selectedNodes = new HashSet<>(); Node minDistanceNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes); while (minDistanceNode != null ) { Integer distance = distanceMap.get(minDistanceNode); for (Edge edge : minDistanceNode.edges) { Node toNode = edge.to; if (!distanceMap.containsKey(toNode)) { distanceMap.put(toNode, distance + edge.weight); } else { distanceMap.put(toNode, Math.min(distanceMap.get(toNode), distance + edge.weight)); } } selectedNodes.add(minDistanceNode); minDistanceNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes); } return distanceMap; } public Node getMinDistanceAndUnselectedNode (Map<Node, Integer> distanceMap, Set<Node> selectedNodes) { int minDistance = Integer.MAX_VALUE; Node minNode = null ; for (Map.Entry<Node, Integer> entry : distanceMap.entrySet()) { Node node = entry.getKey(); Integer distance = entry.getValue(); 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 ; for (int i = 0 ; i < grid.length; i++) { for (int j = 0 ; j < grid[0 ].length; j++) { if (grid[i][j] == '1' ) { infect(grid, i, j, grid.length, grid[0 ].length); count++; } } } return count; } public void infect (char [][] grid, int i, int j, int M, int N) { if (i < 0 || i >= M || j < 0 || j >= N || grid[i][j] != '1' ) { return ; } 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”(单词中的字母已标出)。
思路:本问题是典型的矩阵搜索问题,可使用 深度优先搜索(DFS)+ 剪枝 解决。
深度优先搜索: 可以理解为暴力法遍历矩阵中所有字符串可能性。DFS 通过递归,先朝一个方向搜到底,再回溯至上个节点,沿另一个方向搜索,以此类推。
剪枝: 在搜索中,遇到 这条路不可能和目标字符串匹配成功
的情况(例如:此矩阵元素和目标字符不同、此元素已被访问) ,则应立即返回,称之为 可行性剪枝
。
DFS 解析 :
递归参数: 当前元素在矩阵 board
中的行列索引 i
和 j
,当前目标字符在 word
中的索引 k
。
终止条件:
返回 false: (1) 行或列索引越界 或 (2) 当前矩阵元素与目标字符不同 或 (3) 当前矩阵元素已访问过 ( (3) 可合并至 (2) )
返回 true: k = len(word) - 1
,即字符串 word
已全部匹配。
递推工作:
标记当前矩阵元素: 将 board[i][j]
修改为 空字符 ''
,代表此元素已访问过,防止之后搜索时重复访问。
搜索下一单元格: 朝当前元素的 上、下、左、右 四个方向开启下层递归,使用 或
连接 (代表只需找到一条可行路径就直接返回,不再做后续 DFS ),并记录结果至 res
。
还原当前矩阵元素: 将 board[i][j]
元素还原至初始值,即 word[k]
。
注意 :此类图的 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(); 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 ; } public boolean dfs (int i, int j, int k, char [][] board, char [] words) { if (i < 0 || i >= board.length || j < 0 || j >= board[0 ].length) { return false ; } if (board[i][j] != words[k]) { return false ; } if (k == words.length - 1 ) { return true ; } 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; 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 ; } 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); } public boolean isValid (int i, int j, int k) { int sum = 0 ; while (i != 0 ) { sum += i % 10 ; i /= 10 ; } while (j != 0 ) { sum += j % 10 ; j /= 10 ; } return sum <= k; }