Graph Algorithms You Need for Coding Interviews (Java)

1public int shortestPath(int[][] grid, int[] start, int[] end) {
2    int rows = grid.length, cols = grid[0].length;
3    Queue<int[]> queue = new LinkedList<>();
4    boolean[][] visited = new boolean[rows][cols];
5    int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
6
7    queue.offer(new int[]{start[0], start[1], 0}); // row, col, distance
8    visited[start[0]][start[1]] = true;
9
10    while (!queue.isEmpty()) {
11        int[] curr = queue.poll();
12        if (curr[0] == end[0] && curr[1] == end[1]) return curr[2];
13        for (int[] d : dirs) {
14            int nr = curr[0] + d[0], nc = curr[1] + d[1];
15            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
16                    && !visited[nr][nc] && grid[nr][nc] == 0) {
17                visited[nr][nc] = true;
18                queue.offer(new int[]{nr, nc, curr[2] + 1});
19            }
20        }
21    }
22    return -1;
23}

1class UnionFind {
2    int[] parent, rank;
3
4    UnionFind(int n) {
5        parent = new int[n];
6        rank   = new int[n];
7        for (int i = 0; i < n; i++) parent[i] = i;
8    }
9
10    int find(int x) {
11        if (parent[x] != x) parent[x] = find(parent[x]); // path compression
12        return parent[x];
13    }
14
15    boolean union(int x, int y) {
16        int px = find(x), py = find(y);
17        if (px == py) return false; // already connected
18        if (rank[px] < rank[py]) { int t = px; px = py; py = t; }
19        parent[py] = px;
20        if (rank[px] == rank[py]) rank[px]++;
21        return true;
22    }
23}

1public int[] findOrder(int n, int[][] prerequisites) {
2    int[] indegree = new int[n];
3    List<List<Integer>> adj = new ArrayList<>();
4    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
5
6    for (int[] pre : prerequisites) {
7        adj.get(pre[1]).add(pre[0]);
8        indegree[pre[0]]++;
9    }
10
11    Queue<Integer> queue = new LinkedList<>();
12    for (int i = 0; i < n; i++) if (indegree[i] == 0) queue.offer(i);
13
14    int[] order = new int[n];
15    int idx = 0;
16    while (!queue.isEmpty()) {
17        int course = queue.poll();
18        order[idx++] = course;
19        for (int next : adj.get(course))
20            if (--indegree[next] == 0) queue.offer(next);
21    }
22    return idx == n ? order : new int[]{};
23}

1public int[] dijkstra(int n, int[][] edges, int src) {
2    List<int[]>[] adj = new List[n];
3    for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
4    for (int[] e : edges) {
5        adj[e[0]].add(new int[]{e[1], e[2]});
6        adj[e[1]].add(new int[]{e[0], e[2]});
7    }
8
9    int[] dist = new int[n];
10    Arrays.fill(dist, Integer.MAX_VALUE);
11    dist[src] = 0;
12
13    // Min-heap: [distance, node]
14    PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
15    pq.offer(new int[]{0, src});
16
17    while (!pq.isEmpty()) {
18        int[] curr = pq.poll();
19        int d = curr[0], u = curr[1];
20        if (d > dist[u]) continue; // stale entry
21
22        for (int[] neighbor : adj[u]) {
23            int v = neighbor[0], w = neighbor[1];
24            if (dist[u] + w < dist[v]) {
25                dist[v] = dist[u] + w;
26                pq.offer(new int[]{dist[v], v});
27            }
28        }
29    }
30    return dist;
31}

1public int numIslands(char[][] grid) {
2    int count = 0;
3    for (int r = 0; r < grid.length; r++)
4        for (int c = 0; c < grid[0].length; c++)
5            if (grid[r][c] == '1') { dfs(grid, r, c); count++; }
6    return count;
7}
8
9private void dfs(char[][] grid, int r, int c) {
10    if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length
11            || grid[r][c] != '1') return;
12    grid[r][c] = '0'; // mark visited by mutating input
13    dfs(grid, r+1, c); dfs(grid, r-1, c);
14    dfs(grid, r, c+1); dfs(grid, r, c-1);
15}