Breadth First Search | Practise 2

In this article we talk about Breadth-first search.

The main difference between BFS and DFS is solving approach. BFS uses Queue to solve problem while DFS uses Stack. BFS grows equally by processing closest points while DFS go deep as much as possible on each iteration. We can get that by using Queue and Stack.

Let’s look at problem:

You are given an m x n grid where each cell can have one of three values:

  • 0 representing an empty cell,
  • 1 representing a fresh orange, or
  • 2 representing a rotten orange.

Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.

Problem can be found here.

To solve this problem we can use BFS:

  1. Create Queue that will hold rotten oranges. Add all rotten oranges to this queue
  2. Iterate in cylce while queue is not empty and do next:
    1. Poll rotten orange from queue
    2. Check sorrounding oranges for fresh one. If there is then rotten orange and add to queue
  3. Check if all fresh oranges become rotten

Solution: 

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
class Solution {
    public int orangesRotting(int[][] grid) {
        Queue<Pair<Integer, Integer>> queue = new LinkedList<>();
        int m = grid.length, n = grid[0].length;
        int fresh = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 2) {
                    queue.offer(new Pair(i, j));
                } else if (grid[i][j] == 1) {
                    ++fresh;
                }
            }
        }
        int [] dirs = new int [] {1,0, -1,0, 0,1, 0,-1};
        int time = 0;
        while(!queue.isEmpty()) {
            int s = queue.size();
            for (int k = 0; k < s; ++k) {
                Pair<Integer, Integer> p = queue.poll();
                int currRow = p.getKey(), currCol = p.getValue();
                for (int j = 0; j < 8; j+=2) {
                    int r = currRow + dirs[j], c = currCol + dirs[j+1];
                    if (r < 0 || c < 0 || r == m || c == n || 
                       grid[r][c] != 1) {
                        continue;
                    }
                    queue.offer(new Pair(r, c));
                    grid[r][c] = 2;
                    --fresh;
                }
            }
            ++time;
        }
        if (fresh == 0) return Math.max(0, time - 1);
        return -1;
    }
}

Another example:

There is an undirected graph with n nodes, where each node is numbered between 0 and n - 1. You are given a 2D array graph, where graph[u] is an array of nodes that node u is adjacent to. More formally, for each v in graph[u], there is an undirected edge between node u and node v. The graph has the following properties:

  • There are no self-edges (graph[u] does not contain u).
  • There are no parallel edges (graph[u] does not contain duplicate values).
  • If v is in graph[u], then u is in graph[v] (the graph is undirected).
  • The graph may not be connected, meaning there may be two nodes u and v such that there is no path between them.

A graph is bipartite if the nodes can be partitioned into two independent sets A and B such that every edge in the graph connects a node in set A and a node in set B.

Return true if and only if it is bipartite.

Problem can be found here.

Algorithms will be next:

  1. Create integer colors array(0 = not colored vertex, 1 - first group vertex, -1 - second group vertex)
  2. Iterate through graph:
    1. If vertex was colored, it means we have already checked all its’ adjacent vertices, just continue iteration
    2. Color vertex and create a queue
    3. Add vertex to queue and start cycle while queue is not empty
      1. Poll vertex from queue and check all its’ adjacent vertices
        1. If adjacent vertex is colored with same color then it’s not bipartite graph
        2. If vertex is not colored yet, color it with opposite color and add current vertex to queue

Why we need to iterate through all graph in second step?

Graph could be not connected, that is why we need to check all its’ components

Solution: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public boolean isBipartite(int[][] graph) {
        int n = graph.length;
        int[] colors = new int[n];
        for (int i = 0; i < n; ++i) {
            if (colors[i] != 0) continue;
            Queue<Integer> queue = new LinkedList<>();
            queue.offer(i);
            colors[i] = 1;
            while (!queue.isEmpty()) {
                int v = queue.poll();
                for (int u : graph[v]) {
                    if (colors[u] == colors[v]) return false;
                    if (colors[u] == 0) {
                        colors[u] = -colors[v];
                        queue.offer(u);
                    }
                }
            }
        }
        return true;
    }
}