现实中有很多的问题可以建模为图论问题，然后使用 DFS 与 BFS 算法轻松的解决，现在我们打算从 LeetCode 选择几道题，来了解如何将现实问题建模为图论问题。
题目介绍 给定一个无向图graph，当这个图为二分图时返回true。如果我们能将一个图的节点集合分割成两个独立的子集 A 和 B，并使图中的每一条边的两个节点一个来自 A 集合，一个来自 B 集合，我们就将这个图称为二分图。
graph 将会以邻接表方式给出，graph[i] 表示图中与节点 i 相连的所有节点。每个节点都是一个在 0 到graph.length-1 之间的整数。这图中没有自环和平行边： graph[i] 中不存在 i，并且 graph[i] 中没有重复的值。
注意:
graph 的长度范围为 [1, 100]。
graph[i] 中的元素的范围为 [0, graph.length - 1]。
graph[i] 不会包含 i 或者有重复的值。
图是无向的: 如果 j 在 graph[i] 里边, 那么 i 也会在 graph[j] 里边。
解题思路 这道题的解法是对图中的节点染色，我们使用 DFS 遍历该图，如果当前节点的颜色为红色，那么就将它未访问过的相邻的节点染为绿色，如果当前节点颜色为绿色，就将未访问过的相邻节点染为红色，根据颜色来区分两个集合。
因为一条边连接的两个节点属于两个不同的几个集合，所以一条边连接的两个节点的颜色是不同的，如果我们在遍历的过程中发现已被访问过的相邻的节点的颜色与当前节点的颜色相同，说明它不符合二分图的定义，不是一个二分图；如果遍历图中所有的联通分量，都没有产生矛盾，说明这个图就是一个二分图。
class Solution private boolean [] visited; private boolean [] colors; public boolean isBipartite (int [][] graph) visited = new boolean [graph.length]; colors = new boolean [graph.length]; for (int i = 0 ; i < graph.length; i++) { if (!visited[i]) { if (!dfs(i, graph)) { return false ; } } } return true ; } private boolean dfs (int v, int [][] graph) visited[v] = true ; for (int w: graph[v]) { if (!visited[w]) { colors[w] = !colors[v]; if (!dfs(w, graph)) return false ; } else if (visited[w] && colors[w] == colors[v]) { return false ; } } return true ; } }
题目介绍 给定一个包含了一些 0 和 1 的非空二维数组 grid 。一个岛屿是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直 方向上相邻。你可以假设 grid 的四个边缘都被 0 (代表水) 包围着。
找到给定的二维数组中最大的岛屿面积(如果没有岛屿，则返回面积为 0 )。
注意: 给定的矩阵grid 的长度和宽度都不超过 50。
解题思路 我们将这个矩阵看做是一个图，矩阵中所有的 1 就是一个个的节点，如果两个 1 是垂直或者水平相邻的，那么就可以认为它们被一条边连着，即在一个联通分量中，而我们的任务就是找出包含节点最多的联通分量，并返回节点数目。
import java.util.Arrays;import java.util.stream.Collectors;public class Solution private int rows; private int columns; private boolean [][] visited; private int [][] grid; public int maxAreaOfIsland (int [][] grid) if (grid == null ) { return 0 ; } this .rows = grid.length; if (rows == 0 ) { return 0 ; } this .columns = grid[0 ].length; if (columns == 0 ) { return 0 ; } this .grid = grid; this .visited = new boolean [rows][columns]; int max = 0 ; for (int row = 0 ; row < rows; row++) { for (int column = 0 ; column < columns; column++) { if (!visited[row][column] && grid[row][column] == 1 ) { max = Math.max(max, dfs(row, column)); } } } return max; } private int dfs (int row,int column) int count = 1 ; visited[row][column] = true ; for (int [] w: adj(row, column)) { int nextRow = w[0 ]; int nextColumn = w[1 ]; if (grid[nextRow][nextColumn] == 0 ) { continue ; } if (!visited[nextRow][nextColumn]) { count += dfs(nextRow, nextColumn); } } return count; } private Iterable<int []> adj(int row, int column) { int [][] dirs = {{-1 , 0 }, {0 , -1 }, {0 , 1 }, {1 , 0 }}; return Arrays.stream(dirs) .map(dir -> new int []{dir[0 ] + row, dir[1 ] + column}) .filter(item -> item[0 ] < rows && item[0 ] >= 0 && item[1 ] < columns && item[1 ] >= 0 ) .collect(Collectors.toList()); } }
题目介绍 在一个 $N \times N$ 的方形网格中，每个单元格有两种状态：空（0）或者阻塞（1）。现在我们的目标是从 $(0, 0)$ 到达 $(N-1, N-1)$，即从左上角到达右下角，而我们的目标是寻找一条最短 路径，并且返回这条路径的长度。如果无法从左上角达到右下角，则返回 -1。
每个单元格有 8 种可能的方向
下面给出一个示例
解题思路 我们将方格看做是一个图，方格中所有的 0 看做是图一个节点，如果两个 0 在各自的 8 个方向之中，就说明这两个节点之间有一条边。为了求得最短路径，我们需要从左上角这个节点进行 BFS，使用 dis[i][j] 记录 $(i, j)$ 距离 $(0, 0)$ 的距离，所以 $dis[N-1][N-1]$ 也就表示从左上角到达右下角的最短路径。
import java.util.Arrays;import java.util.LinkedList;import java.util.Queue;import java.util.stream.Collectors;class Solution private boolean [][] visited; private int [][] dis; private int rows; private int columns; public int shortestPathBinaryMatrix (int [][] grid) this .rows = grid.length; this .columns = grid[0 ].length; if (grid[0 ][0 ] == 1 || grid[rows - 1 ][columns - 1 ] == 1 ) { return -1 ; } if (rows == 1 && grid[rows][columns] == 0 ) { return 1 ; } dis = new int [rows][columns]; visited = new boolean [rows][columns]; Queue<int []> queue = new LinkedList<>(); queue.add(new int []{0 , 0 }); visited[0 ][0 ] = true ; dis[0 ][0 ] = 1 ; while (!queue.isEmpty()) { int [] location = queue.remove(); int row = location[0 ]; int column = location[1 ]; for (int [] nextLocation: adj(row, column)) { int nextRow = nextLocation[0 ]; int nextColumn = nextLocation[1 ]; if (!visited[nextRow][nextColumn] && grid[nextRow][nextColumn] == 0 ) { queue.add(new int []{nextRow, nextColumn}); visited[nextRow][nextColumn] = true ; dis[nextRow][nextColumn] = dis[row][column] + 1 ; if (nextRow == rows - 1 && nextColumn == columns - 1 ) { return dis[nextRow][nextColumn]; } } } } return -1 ; } private Iterable<int []> adj(int row, int column) { int [][] dirs = {{-1 , 0 }, {0 , -1 }, {0 , 1 }, {1 , 0 }, {1 , 1 }, {-1 , 1 }, {1 , -1 }, {-1 , -1 }}; return Arrays.stream(dirs) .map(dir -> new int []{dir[0 ] + row, dir[1 ] + column}) .filter(item -> item[0 ] < rows && item[0 ] >= 0 && item[1 ] < columns && item[1 ] >= 0 ) .collect(Collectors.toList()); } }
题目介绍 你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’ 。每个拨轮可以自由旋转：例如把 ‘9’ 变为 ‘0’，’0’ 变为 ‘9’ 。每次旋转都只能旋转一个拨轮的一位数字。
锁的初始数字为 ‘0000’ ，一个代表四个拨轮的数字的字符串。列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。字符串 target 代表可以解锁的数字，你需要给出最小的旋转次数，如果无论如何不能解锁，返回 -1。
解题思路 我们把密码锁的一种组合称之为一种状态，例如 0000 这个组合表示的就是一种状态，现在我们的模板是将 0000 这种状态转变到 target 表示的状态，并且要求步骤最少。
我们可以把一种状态建模为图中的顶点，如果一个状态能够转变为另一种状态，我们就说这两个状态表示的节点之间存在一条边。对于密码锁来说，每一个拨轮可以前后滚动，共有四个拨轮，这意味着一个状态最多与 8 个状态相邻(考虑到 deadends，少于 8 个)，所以我们只要从 0000 这个状态开始 BFS 遍历，即可找到最少到 target 的拨动次数。
import java.util.*;import java.util.stream.Collectors;class Solution public int openLock (String[] deadends, String target) if ("0000" .equals(target)) { return 0 ; } HashSet<String> deadSet = new HashSet<>(); for (int i = 0 ; i < deadends.length; i++) { deadSet.add(deadends[i]); } if (deadSet.contains("0000" )){ return -1 ; } HashSet<String> visited = new HashSet<>(); HashMap<String, Integer> dis = new HashMap<>(); Queue<String> queue = new LinkedList(); queue.add("0000" ); visited.add("0000" ); dis.put("0000" , 0 ); while (!queue.isEmpty()) { String state = queue.remove(); for (String nextState: adj(state, deadSet)) { if (!visited.contains(nextState)) { queue.add(nextState); visited.add(nextState); dis.put(nextState, dis.get(state) + 1 ); if (target.equals(nextState)) { return dis.get(nextState); } } } } return -1 ; } private Iterable<String> adj (String state, HashSet<String> deadSet) ArrayList<String> list = new ArrayList<>(); for (int i = 0 ; i < 4 ; i++) { char [] chars = state.toCharArray(); char s = chars[i]; chars[i] = Character.forDigit((chars[i] - '0' + 1 ) % 10 , 10 ); list.add(new String(chars)); chars[i] = s; chars[i] = Character.forDigit((chars[i] - '0' - 1 + 10 ) % 10 , 10 ); list.add(new String(chars)); } return list.stream().filter(s -> !deadSet.contains(s)).collect(Collectors.toList()); } }
倒水智力题 有两个桶，一个能装 5 升水，一个能装 3 升水，如何得到 4 升水?
这道题还是将状态看做是一个图的节点，如果状态之间能够互相转变，就说状态之前有一条边。我们定义状态 <x,y> 表示第一个桶有 x 升水，第二个桶有 y 升水。那么 <x, y> 与哪些状态是相连的呢，分为六种情况：
倒空第一桶水：<x, y> => <0, y>
倒空第二桶水：<x, y> => <x, 0>
加满第一桶水：<x, y> => <5, y>
加满第二桶水：<x, y> => <x, 3>
第二桶水倒入第一桶水：
$x + y \geq 5$：<x, y> => <5, x + y - 5>
$x + y < 5$：<x, y> => <x + y, 0>
第一桶水倒入第二桶水：
$x + y \geq 3$：<x, y> => <x + y - 3, 3>
$x + y < 3$：<x, y> => <0, x + y>
我们使用一个两位数表示一个状态，十位数表示第一个桶中有多少升水，个位数表示第二个桶中有多少升水，例如 23 表示第一个桶中有 2 升水，第二个桶中有 3 升水。
import java.util.*;public class WaterPuzzle public Iterable<Integer> waterPuzzle () HashSet<Integer> visited = new HashSet<>(); HashMap<Integer, Integer> pre = new HashMap<>(); Queue<Integer> queue = new LinkedList<>(); queue.add(0 ); visited.add(0 ); pre.put(0 , 0 ); int endState = 0 ; boolean flag = false ; while (!queue.isEmpty()) { int state = queue.remove(); for (int nextState: adj(state)) { if (!visited.contains(nextState)) { visited.add(nextState); queue.add(nextState); pre.put(nextState, state); if (nextState / 10 == 4 || nextState % 10 == 4 ) { endState = nextState; flag = true ; break ; } } } if (flag) { break ; } } ArrayList<Integer> result = new ArrayList(); int cur = endState; result.add(cur); while (pre.get(cur) != 0 ) { cur = pre.get(cur); result.add(cur); } Collections.reverse(result); return result; } private Iterable<Integer> adj (int state) int first = state / 10 ; int second = state % 10 ; Set<Integer> set = new HashSet<>(); set.add(second); set.add(first*10 ); set.add(5 *10 + second); set.add(first * 10 + 3 ); if (first + second >= 5 ) { set.add(5 * 10 + (first + second) - 5 ); } else { set.add((first + second) * 10 ); } if (first + second >= 3 ) { set.add((first + second - 3 ) * 10 + 3 ); } else { set.add(first + second); } return new ArrayList<>(set); } public static void main (String[] args) WaterPuzzle waterPuzzle = new WaterPuzzle(); for (int r: waterPuzzle.waterPuzzle()) { System.out.print((r >= 10 ? r : "0" + r) + " " ); } } }
输出为
题目介绍 在一个 2 x 3 的板上（board）有 5 块砖瓦，用数字 1~5 来表示, 以及一块空缺用 0 来表示。一次移动定义为选择 0 与一个相邻的数字（上下左右）进行交换。最终当板 board 的结果是 [[1,2,3],[4,5,0]] 谜板被解开。
给出一个谜板的初始状态，返回最少可以通过多少次移动解开谜板，如果不能解开谜板，则返回 -1 。
解题思路 我们将谜板上的一个组合看做是一个状态，一个状态就是图上的一个节点，如果一个状态能够转变到另一个状态，我们就说这两个状态节点之间有一条边连接。我们使用字符串来表示一个状态，例如 [[1, 4, 5], [0, 2, 3]] 这个状态表示为 "145023"，现在我们的目标是寻找一条从初始状态到 "123450" 这个状态的最短路径，使用 BFS 算法即可
import java.util.*;import java.util.stream.Collectors;public class Solution private HashMap<String, Integer> visited = new HashMap<>(); private int rows; private int columns; public int slidingPuzzle (int [][] board) this .rows = board.length; this .columns = board[0 ].length; String initState = boardToString(board); if (initState.equals("123450" )) { return 0 ; } Queue<String> queue = new LinkedList(); queue.add(initState); visited.put(initState, 0 ); while (!queue.isEmpty()) { String state = queue.remove(); for (String nextState: adj(state)) { if (!visited.containsKey(nextState)) { queue.add(nextState); visited.put(nextState, visited.get(state) + 1 ); if ("123450" .equals(nextState)) { return visited.get(nextState); } } } } return -1 ; } private String boardToString (int [][] board) StringBuilder stringBuilder = new StringBuilder(); for (int i = 0 ; i < rows; i++) { for (int j = 0 ; j < columns; j++) { stringBuilder.append(board[i][j]); } } return stringBuilder.toString(); } private Iterable<String> adj (String state) ArrayList<String> result = new ArrayList<>(); char [] chars = state.toCharArray(); int index = state.indexOf("0" ); int row = index / columns; int column = index % columns; int [][] dirs = {{0 , 1 }, {0 , -1 }, {1 , 0 }, {-1 , 0 }}; List<Integer> locations = Arrays.stream(dirs) .map(dir -> new int []{dir[0 ] + row, dir[1 ] + column}) .filter(item -> item[0 ] < rows && item[0 ] >= 0 && item[1 ] < columns && item[1 ] >= 0 ) .map(item -> item[0 ] * columns + item[1 ]) .collect(Collectors.toList()); for (int i: locations) { String res = swap(chars, index, i); result.add(res); swap(chars, i, index); } return result; } private String swap (char [] chars, int i, int j) char temp = chars[i]; chars[i] = chars[j]; chars[j] = temp; return new String(chars); } }
微信
支付宝
