BFS
何时应用BFS
图的遍历
层级遍历 ---- level order traversal
由点及面 ---- clone graph, number of islands
拓扑排序 --- alien dictionary
简单图最短路径
word ladder
clone graph
word ladder
number of islands
Clone Graph
实际写的时候思路还是不够清晰，基本功需要多练
BFS遍历每个Cur的neighbors
同时用一个Map来存node和CloneNode
对每个Cur.neighbor看是否在map里，如果在了就说明已经遍历过，不需要放到queue里
如果不在的话就需要新建一个cloneNeighbor并放到map里
最后把cloneNeighbor加入到cloneCur的neighbors
public Node cloneGraph(Node node) {
if (node == null) return null;
Queue<Node> nodes = new LinkedList<>();
nodes.add(node);
Map<Node, Node> map = new HashMap<>(); //key is node, val is cloneNode
map.put(node, new Node(node.val, new ArrayList<Node>()));
while (!nodes.isEmpty()) {
Node cur = nodes.poll();
for (Node neighbor : cur.neighbors) {
if (!map.containsKey(neighbor)) {
//add neighbor into map
map.put(neighbor, new Node(neighbor.val, new ArrayList<Node>()));
nodes.offer(neighbor);
}
//add cloneNeighbor into cloneCur
map.get(cur).neighbors.add(map.get(neighbor));
}
}
return map.get(node);
}DFS 解法
class Solution {
public Node cloneGraph(Node node) {
if (node == null) return null;
Map<Node, Node> map = new HashMap<>();
return cloneNode(node, map);
}
private Node cloneNode(Node node, Map<Node, Node> map) {
if (map.containsKey(node)) {
return map.get(node);
}
Node cloneNode = new Node(node.val, new ArrayList<Node>());
map.put(node, cloneNode);
for (Node neighbor : node.neighbors) {
Node cloneNeighbor = cloneNode(neighbor, map);
map.put(neighbor, cloneNeighbor);
cloneNode.neighbors.add(cloneNeighbor);
}
return cloneNode;
}
}Word Ladder
先想简单的BFS解法，寻找隐式图最短路径
optimize: Bi-BFS
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
HashSet<String> visited = new HashSet<>();
HashSet<String> dict = new HashSet<>();
for(int i = 0; i< wordList.size(); i++){
dict.add(wordList.get(i));
}
if (!dict.contains(endWord)) return 0;
Queue<String> q = new LinkedList<>();
q.add(beginWord); //assume beginWord and endWord are not the same.
visited.add(beginWord);
int level =1;
while(!q.isEmpty()){
level++;
int size = q.size();
for(int j=0; j< size; j++){
String str = q.poll();
for(int k = 0; k<str.length();k++){
char [] chars = str.toCharArray();
for(char c = 'a'; c <= 'z'; c++){
chars [k] = c;
String word = new String(chars);
if(word.equals(endWord)&& dict.contains(word)){
return level;
}
if(dict.contains(word) && !visited.contains(word)){
q.add(word);
visited.add(word);
}
}
}
}
}
return 0;
}
}Number of island
矩阵类BFS的基础题，由点及面BFS
构建deltaX[ ] = {-1, 0, 0, 1}, deltaY = {0, -1, 1, 0}
BFS Queue存什么？可以是tuple{x, y}, 也可以是val = x * cols + y。 x = val / cols, y = val % cols
还可以DFS, union find解
BFS解法
class Solution {
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
}
//坐标变换数组
//x = [-1, 0 , 0 , 1]
//y = [0, 1, -1, 0]
int rows = grid.length;
int cols = grid[0].length;
int[][] visited = new int[rows][cols];
int num = 0;
for (int row = 0; row < rows; row++) {
for (int col = 0; col < cols; col++) {
if (grid[row][col] == '1' && visited[row][col] == 0) {
bfs(grid, row, col, visited);
num++;
}
}
}
return num;
}
private void bfs(char[][] grid, int row, int col, int[][] visited) {
//what to store into a queue? either a tuple object or x * rows + y
Queue<Integer> queue = new LinkedList<>();
int rows = grid.length;
int cols = grid[0].length;
queue.offer(row * cols + col);
visited[row][col] = 1;
int[] deltaX = {-1, 0 , 0 , 1};
int[] deltaY = {0, 1, -1, 0};
while (!queue.isEmpty()) {
int cur = queue.poll();
int x = cur / cols;
int y = cur % cols;
for (int i = 0; i < 4; i++) {
int nextX = x + deltaX[i];
int nextY = y + deltaY[i];
if (isValid(grid, nextX, nextY, visited)) {
queue.offer(nextX * cols + nextY);
visited[nextX][nextY] = 1;
}
}
}
}
private boolean isValid(char[][] grid, int row, int col, int[][] visited) {
int rows = grid.length;
int cols = grid[0].length;
return 0 <= row && row < rows && 0<= col && col < cols && grid[row][col] == '1'&& visited[row][col] != 1;
}
}DFS解法
class Solution {
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
int rows = grid.length;
int cols = grid[0].length;
int[][] visited = new int[rows][cols];
int num = 0;
for (int row = 0; row < rows; row++) {
for(int col = 0; col < cols; col++) {
if (grid[row][col] == '1' && visited[row][col] == 0) {
dfs(grid, row, col, visited);
num++;
}
}
}
return num;
}
private void dfs(char[][] grid, int x, int y, int[][] visited) {
if (isValid(grid, x, y, visited)) {
visited[x][y] = 1;
dfs(grid, x - 1, y, visited);
dfs(grid, x + 1, y, visited);
dfs(grid, x, y - 1, visited);
dfs(grid, x, y + 1, visited);
}
}
private boolean isValid(char[][] grid, int x, int y, int[][] visited) {
int rows = grid.length;
int cols = grid[0].length;
return 0 <= x && x < rows && 0<= y && y < cols && grid[x][y] == '1' && visited[x][y] == 0;
}
}Flood Filling Distance Matrix
Walls and Gates
Multi-end BFS
先找0
然后bfs
每次查看pop出来的坐标的邻居，如果还有INF,就更新距离
public void wallsAndGates(int[][] rooms) {
if(rooms == null || rooms.length == 0 || rooms[0].length == 0) return;
int rows = rooms.length;
int cols = rooms[0].length;
Queue<Integer> gates = new LinkedList<>();
for(int i = 0; i < rows; i++){
for(int j = 0; j< cols; j++){
if(rooms[i][j] == 0){
gates.offer(i * cols + j);//no need to store Tuple
}
}
}
int[] dir = {0,1,0,-1,0};//little trick
while(!gates.isEmpty()){
int gate = gates.poll();
int x = gate / cols;//extract x and y
int y = gate % cols;
for(int i = 0; i < 4; i++){
int xx = x + dir[i];
int yy = y + dir[i + 1];
if(xx >= 0 && xx < rows && yy >= 0 && yy < cols && rooms[xx][yy] == Integer.MAX_VALUE){
rooms[xx][yy] = rooms[x][y] + 1;
gates.offer(xx * cols + yy);
}
}
}
}给一个2D matrix， 0表示路，1表示墙，给个start point和end point，求最短路径。(Twitter)
最经典的BFS
public class Solution{
public static class Point{
int x;
int y;
public Point(int x, int y){
this.x = x;
this.y = y;
}
}
public static int getDistance(int[][] matrix, Point src, Point dst){
int rows = matrix.length;
int cols = matrix[0].length;
boolean[][] visited = new boolean[rows][cols];
int[][] res = new int[rows][cols];
//4 directions
int[] x_ways = {0,0,1,-1};
int[] y_ways = {1,-1,0,0};
Queue<Point> queue = new LinkedList<>();
queue.offer(src);
while(!queue.isEmpty()){
Point cur = queue.poll();
visited[cur.x][cur.y] = true;
if(cur.x == dst.x && cur.y == dst.y){
break;//find the dst Point
}
for(int i = 0; i < 4; i++){
int x_next = cur.x + x_ways[i];
int y_next = cur.y + y_ways[i];
if(x_next >= 0 && x_next < rows && y_next >= 0 && y_next < cols && matrix[x_next][y_next] == 1 && !visited[x_next][y_next]){
queue.offer(new Point(x_next, y_next));
res[x_next][y_next] = res[cur.x][cur.y] + 1;//distance + 1
}
}
}
if(res[dst.x][dst.y] == 0){
return -1;//no path to dst Point
}
return res[dst.x][dst.y];
}
public static void main(String[] args){
int[][] matrix = {{1,1,1,1,1},
{0,0,1,1,1},
{1,1,1,1,1}
};
int distance = getDistance(matrix, new Point(0,0), new Point(2, 4));
System.out.println("shortest distance between A and B is: " + distance);
}
}Last updated
Was this helpful?