Graph DFS & BFS Traversal

3 minute read

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