Graphs: Comprehensive Notes for Interview Preparation (Java-Specific)

1. Introduction to Graphs

What is a Graph?

Graph Representation:

  1. Adjacency Matrix:
  2. Adjacency List:

Applications:


2. Graph Traversals

Types of Traversals:

  1. Depth First Search (DFS):

    void dfs(int node, boolean[] visited, List<List<Integer>> graph) {
        visited[node] = true;
        System.out.print(node + " ");
        for (int neighbor : graph.get(node)) {
            if (!visited[neighbor]) {
                dfs(neighbor, visited, graph);
            }
        }
    }
    
    
  2. Breadth First Search (BFS):

    void bfs(int startNode, List<List<Integer>> graph) {
        boolean[] visited = new boolean[graph.size()];
        Queue<Integer> queue = new LinkedList<>();
        queue.add(startNode);
        visited[startNode] = true;
    
        while (!queue.isEmpty()) {
            int node = queue.poll();
            System.out.print(node + " ");
            for (int neighbor : graph.get(node)) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.add(neighbor);
                }
            }
        }
    }
    
    
  3. Topological Sort:

    void topologicalSort(int node, boolean[] visited, Stack<Integer> stack, List<List<Integer>> graph) {
        visited[node] = true;
        for (int neighbor : graph.get(node)) {
            if (!visited[neighbor]) {
                topologicalSort(neighbor, visited, stack, graph);
            }
        }
        stack.push(node);
    }
    
    
  4. Shortest Path Algorithms: