Home/Learn/DSA/Graphs

Graphs

Intermediate

Model real-world networks — master BFS, DFS, topological sort, and shortest path algorithms.

Think of it this way

Think of a map of cities connected by roads. Some roads are two-way (undirected), some are one-way (directed). Some have tolls (weighted edges). Finding the fastest route between two cities is exactly what graph algorithms solve. Google Maps, Facebook friend suggestions, and Netflix recommendations all run on graph algorithms.

In code, it looks like thisJava
// Represent the graph as an adjacency list — city → list of neighbours
Map<String, List<String>> graph = new HashMap<>();
graph.put("Mumbai",  List.of("Delhi", "Pune"));
graph.put("Delhi",   List.of("Mumbai", "Jaipur"));
graph.put("Pune",    List.of("Mumbai"));

// Mumbai — Delhi — Jaipur
//   |
// Pune

Overview

A graph is a collection of nodes (vertices) connected by edges. Graphs can be directed or undirected, weighted or unweighted, cyclic or acyclic. They model social networks, maps, dependency systems, and web links. In Java, graphs are typically represented as adjacency lists using Map<Integer, List<Integer>>. Knowing when to use BFS vs DFS vs Dijkstra is the core skill tested in interviews.

Time & Space Complexity

Operation Time Space
BFS traversalO(V + E)O(V)
DFS traversalO(V + E)O(V)
Dijkstra's (shortest path)O((V + E) log V)O(V)
Topological sortO(V + E)O(V)
Cycle detectionO(V + E)O(V)

Java Implementation

Java
import java.util.*;

public class GraphAlgorithms {

    // DFS — iterative using stack, O(V + E)
    public static void dfs(Map<Integer, List<Integer>> graph, int start) {
        Set<Integer> visited = new HashSet<>();
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(start);
        while (!stack.isEmpty()) {
            int node = stack.pop();
            if (visited.contains(node)) continue;
            visited.add(node);
            System.out.print(node + " ");
            for (int neighbor : graph.getOrDefault(node, List.of())) {
                if (!visited.contains(neighbor)) stack.push(neighbor);
            }
        }
    }

    // Topological sort using Kahn's algorithm (BFS) — O(V + E)
    public static List<Integer> topologicalSort(int n, int[][] edges) {
        int[] inDegree = new int[n];
        Map<Integer, List<Integer>> adj = new HashMap<>();
        for (int[] e : edges) {
            adj.computeIfAbsent(e[0], k -> new ArrayList<>()).add(e[1]);
            inDegree[e[1]]++;
        }
        Queue<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < n; i++) if (inDegree[i] == 0) queue.offer(i);
        List<Integer> order = new ArrayList<>();
        while (!queue.isEmpty()) {
            int node = queue.poll();
            order.add(node);
            for (int neighbor : adj.getOrDefault(node, List.of())) {
                if (--inDegree[neighbor] == 0) queue.offer(neighbor);
            }
        }
        return order.size() == n ? order : List.of(); // empty = cycle detected
    }

    // Number of islands — DFS on grid, O(m * n)
    public static int numIslands(char[][] grid) {
        int count = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') { sink(grid, i, j); count++; }
            }
        }
        return count;
    }

    private static void sink(char[][] grid, int i, int j) {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] != '1') return;
        grid[i][j] = '0';
        sink(grid, i + 1, j); sink(grid, i - 1, j);
        sink(grid, i, j + 1); sink(grid, i, j - 1);
    }
}

Key Points to Remember

  • BFS finds shortest path in unweighted graphs; Dijkstra handles weighted graphs
    // BFS — use a Queue; Dijkstra — use a PriorityQueue (min-heap on distance)
Queue<Integer> bfs = new ArrayDeque<>();
PriorityQueue<int[]> dijkstra = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
  • DFS is better for cycle detection, topological sort, and exploring all paths
    void dfs(int node, boolean[] visited) {
    visited[node] = true;
    for (int nb : graph.get(node))
        if (!visited[nb]) dfs(nb, visited);
}
  • Union-Find (Disjoint Set Union) efficiently answers "are these two nodes connected?"
    int find(int x) { return parent[x] == x ? x : (parent[x] = find(parent[x])); }
void union(int a, int b) { parent[find(a)] = find(b); }
  • Topological sort only works on DAGs (Directed Acyclic Graphs) — cycles break it
  • For grid problems, treat each cell as a node with 4 neighbours
    int[][] dirs = {{1,0}, {-1,0}, {0,1}, {0,-1}}; // down, up, right, left
for (int[] d : dirs) {
    int nr = row + d[0], nc = col + d[1];
    if (nr >= 0 && nr < rows && nc >= 0 && nc < cols) // in-bounds check
        queue.offer(new int[]{nr, nc});
}

Interview Questions

Sign in to ask Aria
1

Number of islands

MediumAmazonSolve it
2

Course schedule — detect cycle in directed graph

MediumFacebookSolve it
3

Shortest path in a binary matrix

MediumGoogleSolve it
4

Clone a graph

MediumFacebookSolve it
5

Word ladder — shortest transformation sequence

HardGoogleSolve it

Ask Aria about Graphs

Your personal AI tutor — ask anything about this concept

Previous
Trees & Binary Search Trees
Next
Sorting Algorithms