DSA Revision

Graph

1. DFS

https://www.geeksforgeeks.org/problems/depth-first-traversal-for-a-graph/1

class Solution {
    // Function to return a list containing the DFS traversal of the graph.
    dfsOfGraph(V, adj) {
        // code here
        let visited = new Array(V).fill(0);
        let ans = [];
        this.dfs(V, adj, 0, visited, ans);
        return ans;
        
    }
    dfs(V, adj, node, visited, ans){
        if(!visited[node]){
            ans.push(node);
            visited[node] = 1;
            for(let i = 0; i < adj[node].length; i++){
                this.dfs(V, adj, adj[node][i], visited, ans);
            }
        }
    }
}

2. BFS

https://www.geeksforgeeks.org/problems/bfs-traversal-of-graph/1

Missed: make the child visited just after pushing into the queue because it might be child of other node as well. visited[child] = 1;

class Solution {
    // Function to return Breadth First Traversal of given graph.
    bfsOfGraph(V, adj) {
        // code here
        let ans = [];
        let visited = new Array(V).fill(0);
        let queue = [];
        
        queue.push(0);
       
        while(queue.length > 0){
            let node = queue.shift();
            ans.push(node);
            visited[node] = 1;
             
            for(let child of adj[node]){
                if(!visited[child]){
                    queue.push(child);
                    visited[child] = 1;
                }
                   
            }
        }
        
        return ans;
    }
    
    
}