Graph DFS & BFS Traversal

3 minute read

Memory Complexity

For a tree like structure, for the purpose of understanding

For a balanced tree with n nodes, there will n/2 leaf nodes due to which the memory complexity of BFS will on O(n)

For DFS, the max memory will the height of the tree which in logN, and that is why the memory complexity is O(logN)

Create Graph from List of Edges List

if edges array edges = [[0,1],[1,2],[2,0]] is given, first create a graph before applying DFS or BFS

If graph consists of integer nodes beginning 0 or 1, simply use an array and take advantage of the indices of the list

Visited Array

Can use a set of type node HashSet<Node> for both 1D and 2D arrays

  • A HashSet<Node> visited can be used used to keep track of visited node
    • use visited.add(r+""+c) for 2D grids
    • use visited.contains(r+""+c)

Can simply use boolean array

// For 1D Array
boolean visited[] = new boolean[V];//Initialized with False
for(Integer i : adj.get(currentVertex)){
  //If neighbor is not visited, add in the Queue or recurse for DFS and make it visited
  if(!visited[i]){
      stack.push(i);
      //q.add(i);
      visited[i] = true;
  }
  
//For grid
int[][] visit = new int[ROWS][COLS];

If you are allowed to change the grid, the simple change the value to a negative scenario

Navigating along the grid

I find it a bit complicated

Use the direction array with ints

Depth First Search (DFS)

  • Traverse all paths between any two vertices in a “graph”.
  • Traversing all Vertices
  • Traversing all paths between two vertices

Recursion

AdjacencyList

Grid DFS

Tests With Stack (Prefer DFS Recursion instead)

In place of the Stack if a queue is used, then the same algo becomes BFS

Recursive backtracking - DFS

Base case for recursion

//Base cases
if(//Covering the 4 corners
    r < 0 || c < 0 //Math.min(r,c) < 0 //Left & Upper bound
    || r == grid.length //right bound
    || c == grid[0].length //lower bound
    // Blockers as per the problem
    || grid[r][c] == 1 //Blocked
    //Visited check
    || visited.contains(r+""+c) //Already Visited
  ){
    return ...;//Depends if count is needed or a void is returned
}

Terminating conditions, if there is one fixed condition.

//Terminating condition, when the rightmost Bottom corner is reached
if(r == grid.length-1 && c == grid[0].length-1){
    return 1;
}

If all possibilities are to be searched

int count = 0;
HashSet<String> visited = new HashSet<>();
for(int i = 0; i < grid.length; i++){
    for(int j = 0; j < grid[0].length; j++){
        if(grid[i][j] == '1' && !visited.contains(i+""+j)){
            count++;
            gridDFS(grid,i,j,visited);
        }
     }
}

The directions array comes handy with BFS as there are no recursive calls

private static final int[][] directions = {
        {1, 0}, //Next Row → , r-1, Keeping Column constant
        {-1, 0}, //Previous Row ←, r+1
        {0, 1}, //Column above ↑, c+1, Keeping Row constant
        {0, -1}}; //Column above ↓, c-1

//while performing dfs
for (int[] dir : directions) {
    dfs(grid, r + dir[0], c + dir[1]);
}
Using Recursion

Pass the updated visited array so that the other calls have the updated set

//Recursive Backtracking
gridDFS(grid,r,c+1,visited);
gridDFS(grid,r,c-1,visited);
gridDFS(grid,r+1,c,visited);
gridDFS(grid,r-1,c,visited);

Complexity

Time Complexity: $ O(V+E) $

  • 𝑉 represents the number of vertices, and
  • 𝐸 represents the number of edges.
  • We need to check every vertex and traverse through every edge in the graph.

Space Complexity: $ 𝑂(𝑉^2) $

  • created stack or the recursive call stack can store up to V⋅V vertices
  • worst case - each vertex has edges connecting to all other vertices.

Breadth First Search - BFS

  • Finding the shortest path between two vertices in a graph where all edges have equal and positive weights.

  • Visits each node once
  • Running time complexity O(V+E)
  • Space complexity is not good, due to an extra Queue, which is why DFS is preferred
  • Dijkstra’s Algo does a BFS if all the edge weight is equal to 1.
  • In AI(Machine Learning) Robots can discover surroundings more easily from BFS than DFS
  • Important in Maximum Flow - Edmonds-Karp Algorithm

You may also enjoy