Breadth First Search

Posted by Faushine on June 30, 2019

Minimum Height Trees

class Solution {

  public List<Integer> findMinHeightTrees(int n, int[][] edges) {
    List<Integer> result = new ArrayList<>();
    if (n == 0) {
      return result;
    }
    if (n == 1) {
      result.add(0);
      return result;
    }
    // 1 - convert array to graph structure
    // copy nodes
    Map<Integer, Set<Integer>> nodes = new HashMap<>();
    for (int i = 0; i < n; i++) {
      nodes.put(i, new HashSet<>());
    }
    // copy edges
    for (int i = 0; i < edges.length; i++) {
      int u = edges[i][0];
      int v = edges[i][1];
      nodes.get(u).add(v);
      nodes.get(v).add(u);
    }

    // 2 - BFS
    // 1) add all leaves (nodes have only one neighbors) into queue
    Queue<Integer> queue = new LinkedList<>();
    Set<Integer> hash = new HashSet<>();
    nodes.forEach((key, value) -> {
      if (value.size() == 1) {
          queue.offer(key);
          hash.add(key);
      }
    });
    int mount = n;
    // 3 - get 1 or 2 nodes in the rest
    while (mount>2){
      int size = queue.size();
      mount = mount-size;
      for (int i = 0; i < size; i++){
        int curNode = queue.poll();
        for (int neighbor:nodes.get(curNode)){
            // 2) remove leaves from their neibors's neibors set
          nodes.get(neighbor).remove(curNode);
          if (!hash.contains(neighbor) && nodes.get(neighbor).size()==1){
            queue.offer(neighbor);
            hash.add(neighbor);
          }
        }
      }
    }
    int size = queue.size();
    for (int i = 0; i < size; i++){
      result.add(queue.poll());
    }
    return result;
  }
}

Shortest Path in Binary Matrix

class Solution {

  public int shortestPathBinaryMatrix(int[][] grid) {
     // the first and the last node should not be 1
    if (grid == null || grid[0][0]==1 || grid[grid.length-1][grid.length-1]==1) {
      return -1;
    }
    Point start = new Point(0, 0);
    return bfs(start, grid);
  }

  public int bfs(Point start, int[][] grid) {
    int endX = grid.length - 1;
    int endY = grid[0].length - 1;
    Queue<Point> queue = new LinkedList<>();
    queue.offer(start);
    grid[start.x][start.y] = -1;
    // direction
    int[] deltaX = {0, 1, 1, 1, 0, -1, -1, -1};
    int[] deltaY = {1, 1, 0, -1, -1, -1, 0, -1};
    int step = 0;
    while (!queue.isEmpty()) {
      int size = queue.size();
      for (int t = 0; t < size; t++) {
        Point node = queue.poll();
        if (node.x == endX && node.y == endY) {
          return step+1;
        }
        // search in 8 directions
        for (int i = 0; i < deltaX.length; i++) {
          for (int j = 0; j < deltaY.length; j++) {
            int x = node.x + deltaX[i];
            int y = node.y + deltaY[j];
            if (!inbound(x, y, grid)) {
              continue;
            }
            if (grid[x][y] == 0 && grid[x][y] != -1) {
              queue.offer(new Point(x, y));
              grid[x][y] = -1;
            }
          }
        }
      }
      step++;
    }
    return -1;
  }

  public boolean inbound(int x, int y, int[][] grid) {
    int N = grid.length;
    return x >= 0 && x < N && y >= 0 && y < N;
  }

}

Word Ladder

class Solution {
     public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        if(!wordList.contains(endWord)){
            return 0;
        }
        wordList.add(beginWord);
        // 1. init undirected graph
        Map<String, Set<String>> mapNodes = initGraph(wordList);
        if(mapNodes.get(beginWord).size()==0||mapNodes.get(endWord).size()==0){
            return 0;
        }
        // 2. BFS with level
        Queue<String> queue = new LinkedList<>();
        Set<String> hash = new HashSet<>();
        queue.offer(beginWord);
        hash.add(beginWord);
        // init level as 1 for beginWord
        int level = 1;
        while(!queue.isEmpty()){
            // neighbors of the node should be processed in one step
            int size = queue.size();
            for (int i = 0; i<size; i++){
                String node = queue.poll();
                for(String neighbor: mapNodes.get(node)) {
                    if (neighbor.equals(endWord)) {
                        // count the level for endWord
                        return level+1;
                    }
                    if (!neighbor.equals(endWord) && !hash.contains(neighbor)) {
                        queue.offer(neighbor);
                        hash.add(neighbor);
                    }
                }
            }
            level++;
        }
        return 0;
    }
    public Map<String,Set<String>> initGraph(List<String> wordList){
        Map<String, Set<String>> map = new HashMap<>();
        // find all nodes
        for (String word:wordList){
            map.put(word,new HashSet<>());
        }
        // find all neighbors
        for (String word1:wordList){
            char[] char1 = word1.toCharArray();
            for (String word2: wordList){
                char[] char2 = word2.toCharArray();
                int count = 0;
                for (int i = 0; i < char2.length; i++) {
                    if(char1[i] != char2[i]){
                        count++;
                    }
                }
                if(count==1){
                    map.get(word1).add(word2);
                }
            }
        }
        return map;
    }
} 

Number of Islands

class Solution {
     public int numIslands(char[][] grid) {
        if(grid.length==0){
            return 0;
        }
        int islands = 0;
        int row = grid.length;
        int colmn = grid[0].length;
        // 1. search grid in matrix:
        for(int i = 0; i<row; i++){
            for(int j = 0; j<colmn; j++){
                // 2. if the val is '1' => bfs => set '0' => islands++
                if(grid[i][j]=='1'){
                    markBFS(new Point(i,j), grid);
                    islands++;
                }
            }
        }
        return islands;
    }
    public void markBFS(Point point, char[][] grid){
        // direction
        int[] deltaX = {1,0,-1,0};
        int[] deltaY = {0,1,0,-1};
        // bfs
        Queue<Point> queue = new LinkedList<>();
        queue.offer(point);
        // when adding a node to queue, this node should be marked as 0
        // it couldn't be added again
        grid[point.x][point.y]='0';
        while(!queue.isEmpty()){
            Point node = queue.poll();
            for(int i = 0; i<4; i++){
                int x = node.x+deltaX[i];
                int y = node.y+deltaY[i];
                if(!inbound(x,y,grid)){
                    continue;
                }
                if(grid[x][y]=='1'){
                    queue.offer(new Point(x,y));
                    grid[x][y]='0';
                }
            }
        }
    }
    public boolean inbound(int x, int y, char[][] grid){
        int row = grid.length;
        int colmn = grid[0].length;
        return x>=0 && y>=0 && x<row && y<colmn;
    }
}

class Point {
    int x, y;
    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

Topological Sorting

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) {
        if(graph==null){
            return null;
        }
        HashMap<DirectedGraphNode,Integer> indegree = new HashMap<>();
        // 1. count indegree of nodes
        for(DirectedGraphNode node:graph){
            ArrayList<DirectedGraphNode> neighbors = node.neighbors;
            for(DirectedGraphNode nei:neighbors){
                if(indegree.containsKey(nei)){
                    indegree.put(nei,indegree.get(nei)+1);
                }else{
                    indegree.put(nei,1);
                }
            }
        }
        
        // 2. find all nodes which have 0 indegree
        if(indegree.size()==graph.size()){
            return null;
        }
        ArrayList<DirectedGraphNode> startNodes = new ArrayList<>();
        for(DirectedGraphNode node:graph){
            if(!indegree.containsKey(node)){
                startNodes.add(node);
            }
        }
        
        // 3. bfs
        ArrayList<DirectedGraphNode> topOrder = new ArrayList<>();
        Queue<DirectedGraphNode> queue = new LinkedList<>();
        // add all startnode to queue
        for(DirectedGraphNode node: startNodes){
            queue.offer(node);
            // add node to topOrder only if its indegree is 0
            // which means this node has no prev-node
            topOrder.add(node);
        }
        while(!queue.isEmpty()){
            DirectedGraphNode node = queue.poll();
            for(DirectedGraphNode nei: node.neighbors){
                indegree.put(nei,indegree.get(nei)-1);
                if(indegree.get(nei)==0){
                    // add node to topOrder only if its indegree is 0
                    // which means this node has no prev-node
                    queue.offer(nei);
                    topOrder.add(nei);
                }
            }
        }
        return topOrder;
    }
}

Clone Graph

class Solution {
    public Node cloneGraph(Node node) {
        List<Node> nodes = new ArrayList<>();
        int start = node.val;
        // 1. get all nodes
        Queue<Node> queue = new LinkedList<>();
        Set<Integer> hash = new HashSet<>();
        queue.offer(node);
        hash.add(node.val);
        while(!queue.isEmpty()){
            Node n = queue.poll();
            List<Node> neighbors = n.neighbors;
            nodes.add(n);
            for(Node nei: neighbors){
                if(!hash.contains(nei.val)){
                    queue.offer(nei);
                    hash.add(nei.val);
                }
            }
        }
        // 2. clone nodes
        Map<Integer, Node> newNodes = new HashMap<>();
        for(Node n: nodes){
            if(!newNodes.containsKey(n.val)){
                Node newNode = new Node(n.val, new ArrayList<>());
                newNodes.put(n.val,newNode);
            }
        }
        // 3. copy edges
        for(Node n: nodes){
            List<Node> neighbors = n.neighbors;
            Node newNode = newNodes.get(n.val);
            List<Node> newNei = new ArrayList<>();
            for(Node nei:neighbors){
                newNei.add(newNodes.get(nei.val));
            }
            newNode.neighbors = newNei;
        }
        return newNodes.get(start);
    }
    
}

Binary Tree Level Order Traversal

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List result = new ArrayList<>();
        if(root == null){
            return result;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            ArrayList<Integer>  level = new ArrayList<Integer>();
            for(int i = 0; i < size; i++){
                TreeNode node = queue.poll();
                level.add(node.val);
                if(node.left!=null){
                    queue.offer(node.left);
                }
                 if(node.right!=null){
                    queue.offer(node.right);
                }
            }
            result.add(level);
        }
            return result;
    }
}

Graph Valid Tree

public class Solution {
    /**
     * @param n: An integer
     * @param edges: a list of undirected edges
     * @return: true if it's a valid tree, or false
     */
    public boolean validTree(int n, int[][] edges) {
        // a graph should have n vertex and n-1 edges
        if (edges.length != n-1){
            return false;
        }
        Map<Integer, Set<Integer>> graph = createGraph (n, edges);
        Queue<Integer> queue = new LinkedList<>();
        // if the item has been added to the queue, it cannot be added again
        Set<Integer> hash = new HashSet<>();
        // 1. add start node to the queue
        queue.offer(0);
        hash.add(0);

        // 2. BFS
        while(!queue.isEmpty()){
            int node = queue.poll();
            for (Integer neighbor: graph.get(node)){
                if(hash.contains(neighbor)){
                    continue;
                }
                hash.add(neighbor);
                queue.offer(neighbor);
            }
        }
        return (hash.size()==n);
    }
    private  Map<Integer, Set<Integer>> createGraph(int n, int[][] edges){
        Map<Integer, Set<Integer>> graph = new HashMap<>();
        // add all nodes to the graph
        for(int i = 0; i<n; i++){
            graph.put(i,new HashSet<Integer>());
        }
        // set neighbors for all nodes
        for(int i = 0; i<edges.length; i++){
            // get v and u
            int u = edges[i][0];
            int v = edges[i][1];
            // add u to v; add v to u
            graph.get(u).add(v);
            graph.get(v).add(u);
        }
        return graph;
    }
}