Graphs: BFS, DFS and Shortest Paths

Graphs look scary until you notice that most interview problems are one of five shapes: traverse everything, find connected parts, detect a cycle, order tasks, or find the shortest path. Recognise the shape and the algorithm follows. Grids count as graphs too — each cell is a node with up to four neighbours.

1. How do you represent a graph?

An adjacency list (a list of neighbours for every node) uses O(V + E) space and suits sparse graphs — almost every interview problem. An adjacency matrix uses O(V²) space but answers “is there an edge?” in O(1); good for dense graphs.

List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
for (int[] e : edges) {           // undirected
    graph.get(e[0]).add(e[1]);
    graph.get(e[1]).add(e[0]);
}

2. BFS vs DFS — when do you use each?

BFS explores level by level with a queue and finds the shortest path in an unweighted graph. DFS goes deep with recursion or a stack and is natural for connectivity, cycle detection, topological sort and backtracking. Both run in O(V + E).

int[] shortestHops(List<List<Integer>> g, int src) {
    int[] dist = new int[g.size()];
    Arrays.fill(dist, -1);
    Deque<Integer> q = new ArrayDeque<>(List.of(src));
    dist[src] = 0;
    while (!q.isEmpty()) {
        int u = q.poll();
        for (int v : g.get(u)) if (dist[v] == -1) { dist[v] = dist[u] + 1; q.add(v); }
    }
    return dist;
}

3. Count the number of islands in a grid.

Scan the grid; every time you find unvisited land, count an island and flood-fill all connected land with DFS so it is not counted again.

int islands(char[][] grid) {
    int count = 0;
    for (int r = 0; r < grid.length; r++)
        for (int c = 0; c < grid[0].length; c++)
            if (grid[r][c] == '1') { count++; sink(grid, r, c); }
    return count;
}
void sink(char[][] g, int r, int c) {
    if (r < 0 || c < 0 || r >= g.length || c >= g[0].length || g[r][c] != '1') return;
    g[r][c] = '0';
    sink(g, r + 1, c); sink(g, r - 1, c); sink(g, r, c + 1); sink(g, r, c - 1);
}

4. How do you detect a cycle in a directed graph?

DFS with three colours: unvisited, in the current path, and finished. Reaching a node that is still “in the current path” means a back edge — a cycle. (For undirected graphs, track the parent, or use union-find.)

5. What is topological sort? Where is it used?

An ordering of a directed acyclic graph where every edge goes from earlier to later — course prerequisites, build systems, task schedulers. Kahn's algorithm repeatedly takes nodes with in-degree zero; if some nodes are never taken, the graph has a cycle.

List<Integer> topo(int n, List<List<Integer>> g) {
    int[] indeg = new int[n];
    for (List<Integer> out : g) for (int v : out) indeg[v]++;
    Deque<Integer> q = new ArrayDeque<>();
    for (int i = 0; i < n; i++) if (indeg[i] == 0) q.add(i);
    List<Integer> order = new ArrayList<>();
    while (!q.isEmpty()) {
        int u = q.poll();
        order.add(u);
        for (int v : g.get(u)) if (--indeg[v] == 0) q.add(v);
    }
    return order.size() == n ? order : List.of();   // empty → cycle
}

6. Explain Dijkstra's algorithm.

It finds shortest paths from one source in a graph with non-negative weights. Keep a min-heap of (distance, node); repeatedly take the closest unfinished node and relax its edges. Time O((V + E) log V). With negative weights use Bellman-Ford instead.

7. What is union-find (disjoint set union)?

A structure that tracks which elements belong to the same group. find returns a group's representative; union merges two groups. With path compression and union by rank, both are nearly O(1). Use it for connected components, cycle detection in undirected graphs and Kruskal's minimum spanning tree.

int find(int[] parent, int x) {
    if (parent[x] != x) parent[x] = find(parent, parent[x]);   // path compression
    return parent[x];
}

8. How do you recognise that a problem is a graph problem?

Look for relationships: friends, flights, prerequisites, dependencies, grid cells, word ladders, network links. If items connect to other items and you need reachability, ordering or distance, model it as nodes and edges first, then pick BFS, DFS, topological sort or Dijkstra.