Benchmarks of DFS and BFS


  • 91

    Better view here

    The Solutions

    The Multi End BFS solution used is this

    public static final int[] d = {0, 1, 0, -1, 0};
    
    public void wallsAndGates(int[][] rooms) {
        if (rooms.length == 0) return;
        int m = rooms.length, n = rooms[0].length;
    
        Deque<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                if (rooms[i][j] == 0) queue.offer(i * n + j); // Put gates in the queue
    
        while (!queue.isEmpty()) {
            int x = queue.poll();
            int i = x / n, j = x % n;
            for (int k = 0; k < 4; ++k) {
                int p = i + d[k], q = j + d[k + 1]; // empty room
                if (0 <= p && p < m && 0 <= q && q < n && rooms[p][q] == Integer.MAX_VALUE) {
                    rooms[p][q] = rooms[i][j] + 1;
                    queue.offer(p * n + q);
                }
            }
        }
    }
    

    The Naive BFS solution used is this

    public static final int[] d = {0, 1, 0, -1, 0};
    
    public void wallsAndGates(int[][] rooms) {
        if (rooms.length == 0) return;
        for (int i = 0; i < rooms.length; ++i)
            for (int j = 0; j < rooms[0].length; ++j)
                if (rooms[i][j] == 0) bfs(rooms, i, j);
    }
    
    private void bfs(int[][] rooms, int i, int j) {
        int m = rooms.length, n = rooms[0].length;
        Deque<Integer> queue = new ArrayDeque<>();
        queue.offer(i * n + j); // Put gate in the queue
        while (!queue.isEmpty()) {
            int x = queue.poll();
            i = x / n; j = x % n;
            for (int k = 0; k < 4; ++k) {
                int p = i + d[k], q = j + d[k + 1];
                if (0 <= p && p < m && 0 <= q && q < n && rooms[p][q] > rooms[i][j] + 1) {
                    rooms[p][q] = rooms[i][j] + 1;
                    queue.offer(p * n + q);
                }
            }
        }
    }
    

    And the DFS solution used is this

    private static int[] d = {0, 1, 0, -1, 0};
    
    public void wallsAndGates(int[][] rooms) {
        for (int i = 0; i < rooms.length; i++)
            for (int j = 0; j < rooms[0].length; j++)
                if (rooms[i][j] == 0) dfs(rooms, i, j);
    }
    
    public void dfs(int[][] rooms, int i, int j) {
        for (int k = 0; k < 4; ++k) {
            int p = i + d[k], q = j + d[k + 1];
            if (0<= p && p < rooms.length && 0<= q && q < rooms[0].length && rooms[p][q] > rooms[i][j] + 1) {
                rooms[p][q] = rooms[i][j] + 1;
                dfs(rooms, p, q);
            }
        }
    }
    

    Some benchmark:

    CASE 1: n by n matrix with all empty rooms except one gate at upper left corner.

    The case generator is like this:

    public static int[][] generateSingleGate(int n) {
        int[][] rooms = new int[n][n];
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                rooms[i][j] = Integer.MAX_VALUE;
        rooms[0][0] = 0;
        return rooms;
    }
    

    The results are

     n	MEBFS		NaiveBFS	DFS
     10	0.161 ms	0.157 ms	0.715 ms
     20	0.848 ms	0.482 ms	3.913 ms  
     40	2.672 ms	1.009 ms	25.429 ms
     80	5.974 ms	3.879 ms	241.825 ms
    160	9.282 ms	9.687 ms	StackOverflowError
    

    For this case due to the deep recursion, DFS is much slower than BFS. DFS is repeatedly updating the cell distance. Since there is only one gate in this case, NaiveBFS is expected to perform just like the MultiEndBFS.

    CASE 2: n by n matrix with a lot of gates.

    The case generator is like this

    public static int[][] generateMassiveGates(int n) {
        int[][] rooms = new int[n][n];
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                if (i % 2 != 0 || j % 2 != 0)
                    rooms[i][j] = Integer.MAX_VALUE;
        return rooms;
    }
    

    The results are:

     n	MEBFS		NaiveBFS	DFS
     10	0.244 ms	0.783 ms	0.471 ms
     20	0.611 ms	3.064 ms	1.941 ms
     40	1.616 ms	10.370 ms	7.248 ms
     80	6.220 ms	26.910 ms	68.338 ms
    160	12.291 ms	95.291 ms	stackoverflow/915.517 ms
    320 27.790 ms	435.643 ms	stackoverflow/12719.976 ms
    640	85.793 ms	3502.662 ms
    

    Like expected, the DFS is much slower, and it is again overflowed.
    The Naive BFS out performs DFS starting from n = 80.
    If we change the vm options to -Xss20m, DFS will run in 915 ms for n=160.
    Fitting the time vs n, I found that the MEBFS is O(n^2), NaiveBFS is O(n^3), DFS is O(n^4) for these cases.

    CASE 3: n by n matrix with a lot of gates but rooms are isolated by walls and gates

    The case generator is this:

    public static int[][] generateIsolateRooms(int n) {
        int[][] rooms = new int[n][n];
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                if (i % 2 != 0 && j % 2 != 0)
                    rooms[i][j] = Integer.MAX_VALUE;
        return rooms;
    }
    

    The results are

     n	MEBFS		NaiveBFS	DFS
     10	0.167 ms	0.268 ms	0.049 ms
     20	0.593 ms	0.865 ms	0.196 ms  
     40	2.073 ms	2.096 ms	1.117 ms
     80	7.347 ms	4.471 ms	2.598 ms
    160	7.223 ms	4.232 ms	2.730 ms
    

    Only in this case DFS wins. Since rooms are isolated, there will be limited recalculation and very shallow recursion.
    The currently testcases in the OJ must somewhat in this catergory which results in a bias of DFS solutions.

    Conclusions

    The performances of MultiEnd is very stable and have time complexities of O(n^2) for a n x n square matrix.

    The time complexity for NaiveBFS should be O(n^4) in the worst case. However is not shown in our tests.

    The performance of recursive DFS is very unstable. It is much slower than BFS if the rooms are interconnected. It is only faster than BFS when small groups of rooms are isolated. In the worst case the time complexity is also O(n^4).

    Thus, for this problem we should prefer BFS over DFS. And the best Solution is Multi End BFS.

    And I suggest admin to add more test cases to emphasize this preference.


  • 0
    C

    Hi, why the time complexity of DFS has a worst case time complexity of O(n^4)? Why my following code shouldn't have that vector<vector<bool>> visited(row, vector<bool>(col,false)); to mark all the rooms other than -1 that we have visited? Thanks

    class Solution {
        long INF = 2147483647;
        vector<pair<int,int>> delta{make_pair<int,int>(-1,0), make_pair<int,int>(1,0), make_pair<int,int>(0,1), make_pair<int,int>(0,-1)};
    public:
        void wallsAndGates(vector<vector<int>>& rooms) {
            if (rooms.empty())
               return;
            int row = rooms.size(), col=rooms[0].size();
            
            for (int r=0; r<row; r++)
            for (int c=0; c<col; c++)
            {
                if (rooms[r][c]==0)
                {
                    vector<vector<bool>> visited(row, vector<bool>(col,false));
                    bfsGate(rooms, r,c,row,col, visited);
                }
            }
        }
        
        void bfsGate(vector<vector<int>>& rooms, int r, int c, int row, int col, vector<vector<bool>>& visited)
        {
            if (r<0||r>=row||c<0||c>=col||rooms[r][c]==-1||visited[r][c])
               return;
            
            for (int i=0; i<delta.size(); i++)
            {
                int rn=r+delta[i].first;
                int cn=c+delta[i].second;
                
                if (rn>=0&&rn<row&&cn>=0&&cn<col)
                {
                    visited[rn][cn]=true;
                    if (rooms[rn][cn]>rooms[r][c]+1)
                    {
                        rooms[rn][cn]=rooms[r][c]+1;
                        bfsGate(rooms,rn,cn,row,col,visited);
                    }
                }
            }
            
        }
    
    };

  • 1

    Because in the worst case, we can have O(n^2) gates. For example 1/4n^2.
    For each gate, DFS will need to travel n^2 to 1 rooms, thus total O(n^4).

    A visited matrix is not necessary. Firstly, because rooms matrix contains this information; Secondly, and mainly, because DFS need to revisit a cell even if it is already visited by other gates to update the cell to the minimum distance.

    And that is exactly why the time complexity of DFS in the worst case can be O(n^2).


  • 0
    C

    What does n stand for? The number of columns or the total number of rooms?

    Thanks


  • 0

    in my tests n is the number of columns
    and i made n by n matrix
    room number is O(n^2)


  • 0

    What about the solution that does separate BFS searches, one from each gate? I'd expect it to perform in the middle, and it doesn't get StackOverflowError. Also, I think some people call it DFS and others call it BFS, causing confusion that would be good to clarify.


  • 0

    Cool. I'd expect the same. I am doing the test now.
    I think it should be called naive BFS. It is definitely not DFS.
    The BFS shown above can be called MultiEnd BFS.


  • 0

    Updated. It does fall in between as expected.


  • 0

    Thanks. You're wrong about NaiveBFS being O(n^2), though. It's only O(n^4). For your case 2, it's already only O(n^3).


  • 0

    Yes. Worst case it should be O(n^4). I should correct that.

    I wonder what is the method you used to fit the time data and get the complexity?

    For case 2, Naive BFS, I looked at the time/n^2 it is like this:

    0.00783
    0.00766
    0.00648125
    0.004204688
    0.003722305
    0.004254326
    

    and the time/n^3 is like this:

    0.000783
    0.000383
    0.000162031
    5.25586E-05
    2.32644E-05
    1.32948E-05
    

    I would expect that if it is O(n^3), with suffient large n, the time/n^3 will converge to a constant.

    Also what do you think would be a testcase that NaiveBFS will give O(n^4)?


  • -1

    You are right.
    It is O(n^3) indeed. I added three more points, and it converged at O(n^3).

    time/n^3        n
    0.000783       10
    0.000383       20
    0.000162031       40
    5.25586E-05       80
    2.32644E-05       160
    1.32948E-05       320
    1.46417E-05       480
    1.33616E-05       640
    1.31296E-05       720

  • 5

    To get the O(n^3) and O(n^4), I at first didn't look at the times but just thought about it. Though then I also ran the experiment to "confirm". I ran your second case, doubling n from 10 up to 1280, and printed the time increase factor. It seemed to approach 8, consistent with O(n^3). For my own case, it seemed to approach 16.

    But I like your way as well, might use that in the future.

    My input for O(n^4) looks like this:

    .GGGGGGGGGGGGGGG
    ................
    GGGGGGGGGGGGGGG.
    ................
    .GGGGGGGGGGGGGGG
    ................
    GGGGGGGGGGGGGGG.
    ................
    .GGGGGGGGGGGGGGG
    ................
    GGGGGGGGGGGGGGG.
    ................
    .GGGGGGGGGGGGGGG
    ................
    GGGGGGGGGGGGGGG.
    ................
    

    Code for it:

    public static int[][] generateZigZag(int n) {
        int[][] rooms = new int[n][n];
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                if (i % 2 != 0 || i % 4 == 0 && j == 0 || i % 4 == 2 && j == n - 1)
                    rooms[i][j] = Integer.MAX_VALUE;
        return rooms;
    }
    

  • 0

    Cool ZigZag case!


  • 1
    R

    @dietpepsi Why the first algorithm is called "Multi End" BFS?


  • 0
    C

    I really appreciate your research. Could you help explain why NaiveBFS is O(n^3)? And why does DFS run faster than Multi End BFS in Leetcode OJ.


  • 0
    Z

    This is a really awesome solution. Thank you so much!


  • 0
    K

    What is the space complexity for the dfs solution?


  • 0

    Hi, I have this other BFS, and according to OJ, this one is actually almost as fast as the multi-end BFS, the code I used is the second approach in the editorial article.

    Instead of starting a brand new BFS from each gate from ground up, when I meet a different gate during the BFS starting from one gate, I recurse on this new gate, to start a new BFS. The previous BFS is paused of cause. The new BFS will likely reclaim some entries from the previous BFS, but the overlapping should not be too much. And when this new BFS returns, much more entries will be ignored by the previous BFS;

    I am not able to precisely quantify the speed of this algorithm, since it suffers the kind of fluctuation as the DFS, but I am just posting it here for reference.

    Note that visited only cares about all gates: I have to do this to prevent the gate A discover gate B then B discovers A again ending up in a dead loop.

    class Solution {
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    
        public void wallsAndGates(int[][] rooms) {
            if (rooms.length <= 0 || rooms == null)
                return;
            int H = rooms.length, W = rooms[0].length;
            boolean[][] visited = new boolean[H][W];
            for (int i = 0; i < rooms.length; i++) {
                for (int j = 0; j < rooms[0].length; j++) {
                    if (rooms[i][j] == 0) {
                        bfs(rooms, i, j, visited);
                    }
                }
            }
        }
    
        public void bfs(int[][] grid, int x, int y, boolean[][] visited) {
            visited[x][y] = true;
            Queue<Entry> q = new LinkedList<>();
            q.offer(new Entry(x, y, -2));
            while (!q.isEmpty()) {
                int size = q.size();
                for (int i = 0; i < size; i++) {
                    Entry e = q.poll();
                    int ex = e.x, ey = e.y, d = e.distance;
                    if (grid[ex][ey] == 0 && !visited[ex][ey]) {    //restart when encounter a new 0;
                        bfs(grid, ex, ey, visited);
                    }
                    if (grid[ex][ey] <= d)    //if -1, or 0, or already populated by a closer 0;
                        continue;
                    if (d < 0)
                        d = 0;
                    else
                        grid[ex][ey] = d;
                    for (int[] vector : directions) {
                        int nx = ex + vector[0], ny = ey + vector[1];
                        if (nx < 0 || ny < 0 || nx >= grid.length || ny >= grid[0].length)
                            continue;
                        q.offer(new Entry(nx, ny, d + 1));
                    }
                }
            }
        }
    
        private static class Entry {
            int x, y, distance;
            public Entry(int x, int y, int distance) { this.x = x; this.y = y; this.distance = distance; }
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.