宽度优先搜索
2018-12-26 本文已影响0人
谢谢水果
Java
Queue<TreeNode> queue = new LinkedList<>();
String[] vals = String.split(" ");
int result = Integer.parseInt(String);
Collections.reverse(List);
new int[]{1,0};
- BFS应用场景
图的遍历 Traversal in Graph
- 层级遍历 Level Order Traversal
- 由点及面 Connected Component
- 拓扑排序 Topological Sorting
最短路径 Shortest Path in Simple Graph
- 仅限简单图求最短路径
- 即，图中每条边长度都是1，或者边长都相等
非递归的方式找所有方案 Iteration solution for all possible results
• 这一点我们将在后面 DFS 的课上提到
- 复杂度
二叉树 时间O(V) 空间：同层节点个数最大值
图 时间O(V+E) 空间：最大深度
优化方案 双向BFS Bidirectional BFS
- 假设单向BFS需要搜索 N 层才能到达终点，每层的判断量为 X，那么总的运算量为 X ^ N 如果换成是双向BFS，前后各自需要搜索 N / 2 层，总运算量为 2 * X ^ (N / 2)
- 无向图; 所有边的长度都为 1 或者长度都一样; 同时给出了起点和终点
- 二叉树上的BFS
102 Binary Tree Level Order Traversal
297 Serialize and Deserialize Binary Tree
- 访问到节点的时候 在结果字符串上添加当前节点信息
- serialize时候空节点也入队 否则无法表示空节点
- 图上的BFS
注意节点不要重复入队就好
133 Clone Graph
*127 Word Ladder
*261 Graph Valid Tree
lt431 Connected Component in Undirected Graph
-
矩阵上的BFS
200 Number of Islands 四个
lt611 Knight Shortest Path 八个
*lt598 Zombie in Matrix
lt573 Build Post Office II -
拓扑排序
算法描述:
统计每个点的入度
将每个入度为 0 的点放入队列(Queue)中作为起始节点
不断从队列中拿出一个点，去掉这个点的所有连边(指向其他点的边)，其他点的相应的入度 - 1
一旦发现新的入度为 0 的点，丢回队列中
求任意一个拓扑排序
lt127 Topological Sorting
210 Course Schedule II
*269 Alien Dictionary 注意可能会有重复的字符对 这种情况下入度不更新
求是否存在拓扑排序
207 Course Schedule
求是否存在且仅存在一个拓扑序 Queue中最多同时只有1个节点
*444 Sequence Reconstruction
注意 重复对不能重复统计入度
求所有的拓扑序 DFS
102 Binary Tree Level Order Traversal
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
public class Solution {
/**
* @param root: A Tree
* @return: Level order a list of lists of integer
*/
public List<List<Integer>> levelOrder(TreeNode root) {
// write your code here
List<List<Integer>> results = new ArrayList<>();
if(root==null)
return results;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
int size = queue.size();
List<Integer> list = new ArrayList<>();
for(int i=0; i<size; i++){
TreeNode node = queue.poll();
if(node.left!=null)
queue.offer(node.left);
if(node.right!=null)
queue.offer(node.right);
list.add(node.val);
}
results.add(list);
}
return results;
}
}
297 Serialize and Deserialize Binary Tree
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
public class Solution {
/**
* This method will be invoked first, you should design your own algorithm
* to serialize a binary tree which denote by a root node to a string which
* can be easily deserialized by your own "deserialize" method later.
*/
public String serialize(TreeNode root) {
// write your code here
StringBuilder sb = new StringBuilder();
if(root==null){
return sb.toString();
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
TreeNode node = queue.poll();
if(node==null){
sb.append("# ");
continue;
}
sb.append(node.val);
sb.append(" ");
queue.offer(node.left);
queue.offer(node.right);
}
return sb.toString();
}
/**
* This method will be invoked second, the argument data is what exactly
* you serialized at method "serialize", that means the data is not given by
* system, it's given by your own serialize method. So the format of data is
* designed by yourself, and deserialize it here as you serialize it in
* "serialize" method.
*/
public TreeNode deserialize(String data) {
// write your code here
if(data==null || data.length()==0)
return null;
String[] vals = data.split(" ");
TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int index = 1;
while(!queue.isEmpty()){
TreeNode node = queue.poll();
if(vals[index].equals("#")){
node.left = null;
}else{
node.left = new TreeNode(Integer.parseInt(vals[index]));
queue.offer(node.left);
}
index++;
if(vals[index].equals("#")){
node.right = null;
}else{
node.right = new TreeNode(Integer.parseInt(vals[index]));
queue.offer(node.right);
}
index++;
}
return root;
}
}
133 Clone Graph
/**
* Definition for undirected graph.
* class UndirectedGraphNode {
* int label;
* ArrayList<UndirectedGraphNode> neighbors;
* UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
* };
*/
public class Solution {
/*
* @param node: A undirected graph node
* @return: A undirected graph node
*/
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
// write your code here
if(node==null)
return null;
UndirectedGraphNode newroot = new UndirectedGraphNode(node.label);
Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();
map.put(node, newroot);
Queue<UndirectedGraphNode> queue = new LinkedList<>();
queue.offer(node);
while(!queue.isEmpty()){
UndirectedGraphNode current = queue.poll();
for(UndirectedGraphNode neighbor: current.neighbors){
UndirectedGraphNode newNeighbor;
if(!map.containsKey(neighbor)){
newNeighbor = new UndirectedGraphNode(neighbor.label);
map.put(neighbor, newNeighbor);
queue.offer(neighbor);
}
newNeighbor = map.get(neighbor);
UndirectedGraphNode newCurrent = map.get(current);
newCurrent.neighbors.add(newNeighbor);
}
}
return newroot;
}
}
127 Word Ladder
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
Set<String> set = new HashSet<>();
for(String str : wordList){
set.add(str);
}
int result = 2;
if(!set.contains(endWord))
return 0;
if(beginWord.equals(endWord))
return 1;
Queue<String> queue = new LinkedList<>();
Set<String> visited = new HashSet<>();
visited.add(beginWord);
queue.offer(beginWord);
while(!queue.isEmpty()){
int size = queue.size();
for(int i=0; i<size; i++){
String current = queue.poll();
for(String next : getNextWords(set, current, visited)){
if(endWord.equals(next))
return result;
queue.offer(next);
}
}
result++;
}
return 0;
}
private List<String> getNextWords(Set<String> set, String str, Set<String> visited){
List<String> result = new ArrayList<>();
char[] chars = str.toCharArray();
for(int i=0; i<chars.length; i++){
for(char c='a'; c<'z'; c++){
char charati = chars[i];
if(c==chars[i])
continue;
chars[i] = c;
String temp = new String(chars);
if(set.contains(temp) && !visited.contains(temp)){
result.add(temp);
visited.add(temp);
}
chars[i] = charati;
}
}
return result;
}
}
261 Graph Valid Tree
class Solution {
public boolean validTree(int n, int[][] edges) {
return bfs(n, edges);
}
private boolean bfs(int n, int[][] edges){
if(edges.length!=n-1)
return false;
Map<Integer, Set<Integer>> graph = new HashMap<>();
for(int[] edge : edges){
int n0 = edge[0];
int n1 = edge[1];
Set<Integer> set0 = graph.getOrDefault(n0, new HashSet<>());
Set<Integer> set1 = graph.getOrDefault(n1, new HashSet<>());
set0.add(n1);
set1.add(n0);
graph.put(n0, set0);
graph.put(n1, set1);
}
Queue<Integer> queue = new LinkedList<>();
Set<Integer> visited = new HashSet<>();
queue.offer(0);
visited.add(0);
int count = 0;
while(!queue.isEmpty()){
int current = queue.poll();
count++;
for(Integer next : graph.getOrDefault(current, new HashSet<>())){
if(visited.contains(next))
return false;
visited.add(next);
Set<Integer> set = graph.get(next);
set.remove(current);
graph.put(next, set);
queue.offer(next);
}
}
System.out.println(count);
return count == n;
}
}
lt431 Connected Component in Undirected Graph
/**
* Definition for Undirected graph.
* class UndirectedGraphNode {
* int label;
* ArrayList<UndirectedGraphNode> neighbors;
* UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
* };
*/
public class Solution {
/*
* @param nodes: a array of Undirected graph node
* @return: a connected set of a Undirected graph
*/
public List<List<Integer>> connectedSet(List<UndirectedGraphNode> nodes) {
// write your code here
if(nodes==null)
return null;
Set<UndirectedGraphNode> set = new HashSet<>();
List<List<Integer>> result = new ArrayList<>();
for(UndirectedGraphNode node: nodes){
if(!set.contains(node)){
set.add(node);
List<Integer> temp = getBFS(nodes, node, set);
result.add(temp);
}
}
return result;
}
private List<Integer> getBFS(List<UndirectedGraphNode> nodes, UndirectedGraphNode node, Set<UndirectedGraphNode> set){
List<Integer> result = new ArrayList<>();
Queue<UndirectedGraphNode> queue = new LinkedList<>();
queue.offer(node);
while(!queue.isEmpty()){
UndirectedGraphNode temp = queue.poll();
result.add(temp.label);
for(UndirectedGraphNode neighbor: temp.neighbors){
if(!set.contains(neighbor)){
queue.offer(neighbor);
set.add(neighbor);
}
}
}
Collections.sort(result);
return result;
}
}
200 Number of Islands
class Solution {
public int numIslands(char[][] grid) {
if(grid==null || grid.length==0 || grid[0]==null || grid[0].length==0)
return 0;
int result = 0;
boolean[][] visited = new boolean[grid.length][grid[0].length];
for(int i=0; i<grid.length; i++){
for(int j=0; j<grid[0].length; j++){
if(grid[i][j]=='1'){
result++;
grid[i][j] = '0';
visited[i][j] = true;
bfs(grid, i, j, visited);
}
}
}
return result;
}
private void bfs(char[][] grid, int i, int j, boolean[][] visited){
int[] dirx = {1, -1, 0, 0};
int[] diry = {0, 0, 1, -1};
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{i, j});
while(!queue.isEmpty()){
int[] current = queue.poll();
for(int k=0; k<4; k++){
int x = current[0]+dirx[k];
int y = current[1]+diry[k];
if(isValid(visited, x, y, grid)){
queue.offer(new int[]{x, y});
grid[x][y] = '0';
visited[x][y] = true;
}
}
}
}
private boolean isValid(boolean[][] visited, int x, int y, char[][] grid){
return x>=0 && x<grid.length && y>=0 && y<grid[0].length && visited[x][y]==false && grid[x][y]=='1';
}
}
lt611 Knight Shortest Path
/**
* Definition for a point.
* class Point {
* int x;
* int y;
* Point() { x = 0; y = 0; }
* Point(int a, int b) { x = a; y = b; }
* }
*/
public class Solution {
/**
* @param grid: a chessboard included 0 (false) and 1 (true)
* @param source: a point
* @param destination: a point
* @return: the shortest path
*/
public int shortestPath(boolean[][] grid, Point source, Point destination) {
// write your code here
if(grid==null || grid.length==0 || grid[0]==null || grid[0].length==0)
return 0;
if(source.x==destination.x && source.y==destination.y)
return 0;
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{source.x, source.y});
int[] dirx = {1, -1, 2, 2, 1, -1, -2, -2};
int[] diry = {2, 2, 1, -1, -2, -2, 1, -1};
boolean[][] visited = new boolean[grid.length][grid[0].length];
visited[source.x][source.y] = true;
int result = 0;
while(!queue.isEmpty()){
result++;
int size = queue.size();
System.out.println(size);
for(int i=0; i<size; i++){
int[] current = queue.poll();
int x = current[0];
int y = current[1];
System.out.println(x+" "+y);
for(int j=0; j<8; j++){
int newx = x+dirx[j];
int newy = y+diry[j];
if(isValid(newx, newy, grid, visited)){
if(newx==destination.x && newy==destination.y)
return result;
queue.offer(new int[]{newx, newy});
visited[newx][newy] = true;
}
}
}
}
return -1;
}
private boolean isValid(int x, int y, boolean[][] grid, boolean[][] visited){
return x>=0 && x<grid.length && y>=0 && y<grid[0].length && grid[x][y]==false && visited[x][y]==false;
}
}
598 Zombie in Matrix
public class Solution {
/**
* @param grid: a 2D integer grid
* @return: an integer
*/
public int zombie(int[][] grid) {
// write your code here
Queue<int[]> queue = new LinkedList<>();
for(int i=0; i<grid.length; i++){
for(int j=0; j<grid[0].length; j++){
if(grid[i][j]==1)
queue.offer(new int[]{i,j});
}
}
int days = 0;
int[] dirx = {1, -1, 0, 0};
int[] diry = {0, 0, 1, -1};
while(!queue.isEmpty()){
int size = queue.size();
days++;
for(int i=0; i<size; i++){
int[] current = queue.poll();
int x = current[0];
int y = current[1];
for(int k=0; k<4; k++){
int newx = x+dirx[k];
int newy = y+diry[k];
if(isValid(grid, newx, newy)){
grid[newx][newy] = 1;
queue.offer(new int[]{newx, newy});
}
}
}
}
for(int i=0; i<grid.length; i++){
for(int j=0; j<grid[0].length; j++){
if(grid[i][j]==0)
return -1;
}
}
return days-1;
}
private boolean isValid(int[][] grid, int x, int y){
return x>=0 && x<grid.length && y>=0 && y<grid[0].length && grid[x][y]==0;
}
}
127 Topological Sorting
/**
* Definition for Directed graph.
* class DirectedGraphNode {
* int label;
* ArrayList<DirectedGraphNode> neighbors;
* DirectedGraphNode(int x) { label = x; neighbors = new ArrayList<DirectedGraphNode>(); }
* };
*/
public class Solution {
/*
* @param graph: A list of Directed graph node
* @return: Any topological order for the given graph.
*/
public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
// write your code here
Map<DirectedGraphNode, Integer> map = new HashMap<>();
for(DirectedGraphNode node : graph){
for(DirectedGraphNode neighbor : node.neighbors){
map.put(neighbor, map.getOrDefault(neighbor, 0)+1);
}
}
Queue<DirectedGraphNode> queue = new LinkedList<>();
for(DirectedGraphNode node : graph){
if(!map.containsKey(node)){
queue.offer(node);
}
}
ArrayList<DirectedGraphNode> result = new ArrayList<>();
while(!queue.isEmpty()){
DirectedGraphNode node = queue.poll();
result.add(node);
for(DirectedGraphNode neighbor : node.neighbors){
map.put(neighbor, map.get(neighbor)-1);
if(map.get(neighbor)==0)
queue.offer(neighbor);
}
}
return result;
}
}
210 Course Schedule II
class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
Map<Integer, Integer> map = new HashMap<>();
Map<Integer, List<Integer>> graph = new HashMap<>();
for(int[] prerequest : prerequisites){
int in = prerequest[0];
int out = prerequest[1];
map.put(in, map.getOrDefault(in,0)+1);
List<Integer> neighbors = graph.getOrDefault(out, new ArrayList<>());
neighbors.add(in);
graph.put(out, neighbors);
}
Queue<Integer> queue = new LinkedList<>();
for(int i=0; i<numCourses; i++){
if(!map.containsKey(i)){
queue.offer(i);
}
}
int count = 0;
int[] result = new int[numCourses];
while(!queue.isEmpty()){
int out = queue.poll();
result[count] = out;
count++;
for(Integer in : graph.getOrDefault(out, new ArrayList<>())){
map.put(in, map.get(in)-1);
if(map.get(in)==0)
queue.offer(in);
}
}
if(count==numCourses)
return result;
return new int[0];
}
}
269 Alien Dictionary
class Solution {
public String alienOrder(String[] words) {
Map<Character, Set<Character>> graph = new HashMap<>();
Map<Character, Integer> indegree = new HashMap<>();
Set<Character> alphabet = new HashSet<>();
for(String word : words){
for(int i=0; i<word.length(); i++){
alphabet.add(word.charAt(i));
}
}
for(int i=1; i<words.length; i++){
String pre = words[i-1];
String next = words[i];
int j=0;
while(j<pre.length() && j<next.length() ){
if(pre.charAt(j)==next.charAt(j)){
j++;
}else{
Set<Character> set = graph.getOrDefault(pre.charAt(j), new HashSet<>());
if(set.add(next.charAt(j))){
graph.put(pre.charAt(j), set);
indegree.put(next.charAt(j), indegree.getOrDefault(next.charAt(j), 0)+1);
}
break;
}
}
}
StringBuilder sb = new StringBuilder();
Queue<Character> queue = new LinkedList<>();
for(Character c : alphabet){
if(!indegree.containsKey(c)){
queue.offer(c);
}
}
while(!queue.isEmpty()){
Character c = queue.poll();
sb.append(c);
for(Character next : graph.getOrDefault(c, new HashSet<>())){
indegree.put(next, indegree.get(next)-1);
if(indegree.get(next)==0)
queue.offer(next);
}
}
if(sb.length()==alphabet.size()){
return sb.toString();
}
return "";
}
}
207 Course Schedule
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
Map<Integer, Integer> map = new HashMap<>();
Map<Integer, List<Integer>> graph = new HashMap<>();
for(int[] prerequest : prerequisites){
int in = prerequest[0];
int out = prerequest[1];
map.put(in, map.getOrDefault(in,0)+1);
List<Integer> neighbors = graph.getOrDefault(out, new ArrayList<>());
neighbors.add(in);
graph.put(out, neighbors);
}
Queue<Integer> queue = new LinkedList<>();
for(int i=0; i<numCourses; i++){
if(!map.containsKey(i)){
queue.offer(i);
}
}
int count = 0;
while(!queue.isEmpty()){
int out = queue.poll();
count++;
for(Integer in : graph.getOrDefault(out, new ArrayList<>())){
map.put(in, map.get(in)-1);
if(map.get(in)==0)
queue.offer(in);
}
}
return count==numCourses;
}
}
444 Sequence Reconstruction
class Solution {
public boolean sequenceReconstruction(int[] org, List<List<Integer>> seqs) {
// write your code here
Map<Integer, Integer> indegree = new HashMap<>();
Map<Integer, Set<Integer>> graph = new HashMap<>();
int index = 0;
for(List<Integer> seq : seqs){
for(int i=1; i<seq.size(); i++){
int in = seq.get(i);
int out = seq.get(i-1);
if(in>org.length || out>org.length)
return false;
if(!graph.containsKey(in)){
graph.put(in, new HashSet<>());
}
Set<Integer> set = graph.getOrDefault(out, new HashSet<>());
if(set.add(in)){
graph.put(out, set);
indegree.put(in, indegree.getOrDefault(in, 0)+1);
}
}
}
System.out.println(indegree.size());
System.out.println(graph.size());
Queue<Integer> queue = new LinkedList<>();
if(indegree.containsKey(org[0]))
return false;
queue.offer(org[0]);
while(!queue.isEmpty()){
Integer current = queue.poll();
if(org[index]!=current)
return false;
index++;
for(Integer next : graph.getOrDefault(current, new HashSet<>())){
indegree.put(next, indegree.get(next)-1);
if(indegree.get(next)==0)
queue.offer(next);
}
if(queue.size()>1)
return false;
}
return index==org.length;
}
}
