Session 45: Graph 2

Original Session

Date: 23 Feb 2025

Topic: Graph

Concept: DFS traversal 

Using Matrix
void dfs(int[][] matrix, int i, int j) {
	
	if (i == 0 || j == 0 || i >= matrix.length || j >= matrix[0].length || matrix[i][j] == -1) {
		return;
	}
	System.out.println(matrix[i][j]);
	matrix[i][j] = -1;
	dfs(matrix, i, j+1);
	dfs(matrix, i-1, j);
	dfs(matrix, i, j-1);
	dfs(matrix, i+1, j);
}

Programs

  1. DFS of Graph
    1. GFG here 
      Adjacency List

public ArrayList<Integer> dfsOfGraph(ArrayList<ArrayList<Integer>> adj) {
        
        boolean[] visited = new boolean[adj.size()];
        ArrayList<Integer> ans = new ArrayList();
        dfs(adj, ans, visited, 0);
        return ans;
        
    }
    
    void dfs(ArrayList<ArrayList<Integer>> adj,
            ArrayList<Integer> ans,
            boolean[] visited, 
            int source) {
     
        visited[source] = true;
        ans.add(source);
        
        for(int i: adj.get(source)) {
            if (!visited[i]) {
                dfs(adj, ans, visited, i);
            }
        }
    }

  1. 200. Number of Islands
    1. leetcode here 
      class Solution {
    public int numIslands(char[][] grid) {
        
        int n = grid.length;
        int m = grid[0].length;
        int ans = 0;
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {

                if (grid[i][j] == '1') {
                    dfs(grid, i, j);
                    ans++;
                }
            }
        }
        return ans;
    }

    void dfs(char[][] matrix, int i, int j) {
	
        if (i < 0 || j < 0 || i >= matrix.length || j >= matrix[0].length || matrix[i][j] == '0') {
            return;
        }
        matrix[i][j] = '0';
        dfs(matrix, i, j+1);
        dfs(matrix, i-1, j);
        dfs(matrix, i, j-1);
        dfs(matrix, i+1, j);
    }
}

  1. 695. Max Area of Island
    1. leetcode here 
      class Solution {
    int temp=0;
    public int maxAreaOfIsland(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        int ans = 0;
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {

                if (grid[i][j] == 1) {
                    temp = 0;
                    dfs(grid, i, j);
                    ans = Math.max(ans, temp);
                }
            }
        }
        return ans;
    }


    private void dfs(int[][] matrix, int i, int j) {
	
        if (i < 0 || j < 0 || i >= matrix.length || j >= matrix[0].length || matrix[i][j] == 0) {
            return;
        }
        matrix[i][j] = 0;
        temp++;
        dfs(matrix, i, j+1);
        dfs(matrix, i-1, j);
        dfs(matrix, i, j-1);
        dfs(matrix, i+1, j);
    }
}

  1. 463. Island Perimeter
    1. leetcode here 
      public int islandPerimeter(int[][] grid) {
        
        int n = grid.length;
        int m = grid[0].length;
        int ans = 0;
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {

                ans += edges(grid, i, j);
            }
        }
        return ans;
    }

    private int edges(int[][] grid, int i, int j) {

        if (grid[i][j] == 0) {
            return 0;
        }

        int r = grid.length;
        int c = grid[0].length;
        int edge = 0;
        if (i == 0 || grid[i-1][j] == 0) {
            edge ++;
        }
        if (i == r-1 || grid[i+1][j] == 0) {
            edge ++;
        }
        if (j == 0 || grid[i][j-1] == 0) {
            edge ++;
        }
        if (j == c-1 || grid[i][j+1] == 0) {
            edge ++;
        }

        return edge;
    }

  1. 733. Flood Fill
    1. leetcode here 
      public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        
        int oldColor = image[sr][sc];
        dfs(image, sr, sc, oldColor, color);
        return image;
    }

    private void dfs(int[][] image, int i, int j, int oldColor, int newColor) {

        if (i < 0 || j < 0 || i >= image.length || j >= image[0].length || image[i][j] == newColor || image[i][j] != oldColor) {
            return;
        }
        image[i][j] = newColor;
        dfs(image, i, j+1, oldColor, newColor);
        dfs(image, i-1, j, oldColor, newColor);
        dfs(image, i, j-1, oldColor, newColor);
        dfs(image, i+1, j, oldColor, newColor);
    }

  1. 79. Word Search
    1. leetcode here 
      public boolean exist(char[][] board, String word) {
        
        int n = board.length;
        int m = board[0].length;

        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {

                if (board[i][j] == word.charAt(0)
                && dfs(board, i, j, word, 0)) {
                    return true;
                }
            }
        }

        return false;
    }

    private boolean dfs(char[][] board, int i, int j, String word, int index) {

        if (index == word.length()) {
            return true;
        }

        if (i < 0 || j < 0 
            || i >= board.length 
            || j >= board[0].length 
            || board[i][j] != word.charAt(index)) {
            return false;
        }

        char ch = word.charAt(index);
        board[i][j] = '#';
        boolean found = dfs(board, i+1, j, word, index+1) ||
        dfs(board, i-1, j, word, index+1) ||
        dfs(board, i, j+1, word, index+1) ||
        dfs(board, i, j-1, word, index+1);
        
        board[i][j] = ch;
        return found;
    }