Graphs: Representations, BFS, and DFS

Open a map app. Your location, a bus stop, a station and your friend's house are all points, and the roads between them are connections. A social network is the same shape: people and friendships. A set of tasks where "B can only start after A finishes" is the same shape again. The pages of a website, linked to each other, are too.

The structure that captures all of these is the graph: a collection of vertices (also called nodes) joined by edges. Graphs are probably the most general data structure in this course, and a trees chapter was only the warm-up. Many interview problems that look unrelated (word ladders, maze paths, counting islands, dependency order, finding clusters) are graph problems in disguise, and two simple algorithms, breadth-first search and depth-first search, solve most of them.

• Graph vocabulary: directed, undirected, weighted, degree, path, cycle, component.
• Two representations, and how to choose between them.
• BFS and DFS, and how to avoid processing a vertex twice.
• Connected components, and a grid treated as a graph.
• Cycle detection in undirected and directed graphs.
• How to state running time in terms of V (vertices) and E (edges).

A tree is a connected undirected graph with no cycles. With V vertices it has exactly V - 1 edges. Graphs generalise trees by allowing cycles, several components, and any number of connections per vertex.

In this article, V means the number of vertices and E the number of edges. We label vertices 0 to V - 1. If a problem labels them from 1, subtract 1 when you read the input.

A V × V table where matrix[i][j] is true (or the weight) if there is an edge from i to j. Checking whether an edge exists is O(1). But it always uses O(V^2) space, even if the graph has few edges, and listing a vertex's neighbours means scanning a whole row, O(V).

For each vertex, a list of its neighbours. In Java, a List<List<Integer>>: adj.get(v) is the list of vertices adjacent to v. The space is O(V + E), and listing the neighbours of v takes time proportional to its degree.

Real graphs are usually sparse: a social network with a million people does not have a trillion friendships. A matrix for a million vertices would need a trillion cells, so adjacency lists are the default. For an undirected edge, add each endpoint to the other's list. For a directed edge u -> v, add only v to u's list.

static List<List<Integer>> buildGraph(int n, int[][] edges, boolean directed) {    List<List<Integer>> adj = new ArrayList<>();    for (int i = 0; i < n; i++) {        adj.add(new ArrayList<>());    }    for (int[] e : edges) {        adj.get(e[0]).add(e[1]);        if (!directed) {            adj.get(e[1]).add(e[0]);        }    }    return adj;}

We will use this helper in every program in this article.

BFS explores a graph in layers. Start at a source vertex: that is layer 0. Then visit all its neighbours (layer 1), then all their unvisited neighbours (layer 2), and so on. It is the level-order traversal of a tree, adapted for graphs.

It uses a queue: take a vertex from the front, and add its unvisited neighbours to the back. Because the queue is first-in-first-out, closer vertices are always processed before farther ones.

The one new ingredient compared with a tree is the visited record. A graph can have cycles, or several paths to the same vertex, so without it we could loop forever or process a vertex many times. Mark a vertex visited at the moment you put it in the queue, not when you take it out. Otherwise the same vertex can be added to the queue several times before its first turn comes.

bfs(source):    visited[source] = true    queue.add(source)    while queue is not empty:        u = queue.remove()        for each neighbour v of u:            if not visited[v]:                visited[v] = true                queue.add(v)

Because BFS reaches vertices in order of the number of edges from the source, the first time it reaches a vertex is by a path with the fewest edges. So we can compute the distance to every vertex: when we discover v from u, dist[v] = dist[u] + 1. To recover the actual path, remember each vertex's parent (the vertex we discovered it from), and walk back from the target to the source.

This only holds when all edges count the same. If edges have different weights, BFS is not enough, and you need Dijkstra's algorithm, covered in Shortest Paths and Topological Sorting.

Consider this undirected graph with 8 vertices:

0 --- 1        5 --- 6        7|     |2 --- 3 --- 4

Its edges are 0-1, 0-2, 1-3, 2-3, 3-4, 5-6. Vertex 7 has no edges. There are three components.

BFS from vertex 0:

The order is 0, 1, 2, 3, 4. Distances from 0: vertices 1 and 2 are at distance 1, vertex 3 at 2, vertex 4 at 3. Vertices 5, 6 and 7 are never reached, so their distance stays at -1.

Complexity. Each vertex is enqueued at most once, and each edge is examined at most once (twice for an undirected graph, once from each end). So BFS takes O(V + E) time with an adjacency list, and O(V) extra space for the queue and the visited array.

DFS goes as deep as possible along one path before backing up. From a vertex, pick an unvisited neighbour and move to it, and repeat. When you reach a vertex with no unvisited neighbours, backtrack to the previous vertex and try its next neighbour. This is the same walk as a tree's preorder traversal, with a visited array added.

The natural implementation is recursive. The call stack remembers the path back.

dfs(u):    visited[u] = true    for each neighbour v of u:        if not visited[v]:            dfs(v)

For a graph with a long path of, say, 100,000 vertices, recursion could overflow the stack. The fix is an iterative DFS with your own stack. Push the source. While the stack is not empty, pop a vertex; if it is unvisited, mark it and push its unvisited neighbours. Pushing neighbours in reverse order makes the visiting order match the recursive version.

For our example graph, DFS from 0 visits 0, 1, 3, 2, 4: from 0 go to 1, from 1 go to 3, from 3 go to 2 (its first unvisited neighbour), then back up, and finally 4.

DFS has the same cost as BFS, O(V + E) time and O(V) space (the recursion stack or the explicit stack can hold up to V vertices).

The program below builds the example graph and runs BFS (order, distances, path), recursive and iterative DFS, and a component count.

// File: Main.javaimport java.util.ArrayDeque;import java.util.ArrayList;import java.util.Arrays;import java.util.Collections;import java.util.Deque;import java.util.List;import java.util.Queue;public class Main {    static List<List<Integer>> buildGraph(int n, int[][] edges, boolean directed) {        List<List<Integer>> adj = new ArrayList<>();        for (int i = 0; i < n; i++) {            adj.add(new ArrayList<>());        }        for (int[] e : edges) {            adj.get(e[0]).add(e[1]);            if (!directed) {                adj.get(e[1]).add(e[0]);            }        }        return adj;    }    static List<Integer> bfsOrder(List<List<Integer>> adj, int source) {        List<Integer> order = new ArrayList<>();        boolean[] visited = new boolean[adj.size()];        Queue<Integer> queue = new ArrayDeque<>();        visited[source] = true;                         // mark when enqueued        queue.offer(source);        while (!queue.isEmpty()) {            int u = queue.poll();            order.add(u);            for (int v : adj.get(u)) {                if (!visited[v]) {                    visited[v] = true;                    queue.offer(v);                }            }        }        return order;    }    // distance[v] = fewest edges from source to v, or -1 if unreachable. parent[] lets us rebuild paths.    static int[] bfsDistances(List<List<Integer>> adj, int source, int[] parent) {        int[] distance = new int[adj.size()];        Arrays.fill(distance, -1);        Arrays.fill(parent, -1);        Queue<Integer> queue = new ArrayDeque<>();        distance[source] = 0;        queue.offer(source);        while (!queue.isEmpty()) {            int u = queue.poll();            for (int v : adj.get(u)) {                if (distance[v] == -1) {                // unvisited                    distance[v] = distance[u] + 1;                    parent[v] = u;                    queue.offer(v);                }            }        }        return distance;    }    static List<Integer> pathTo(int target, int[] parent, int[] distance) {        List<Integer> path = new ArrayList<>();        if (distance[target] == -1) {            return path;                                // unreachable: empty path        }        for (int v = target; v != -1; v = parent[v]) {            path.add(v);        }        Collections.reverse(path);        return path;    }    static void dfsRecursive(List<List<Integer>> adj, int u, boolean[] visited, List<Integer> order) {        visited[u] = true;        order.add(u);        for (int v : adj.get(u)) {            if (!visited[v]) {                dfsRecursive(adj, v, visited, order);            }        }    }    static List<Integer> dfsIterative(List<List<Integer>> adj, int source) {        List<Integer> order = new ArrayList<>();        boolean[] visited = new boolean[adj.size()];        Deque<Integer> stack = new ArrayDeque<>();        stack.push(source);        while (!stack.isEmpty()) {            int u = stack.pop();            if (visited[u]) {                continue;                               // may have been pushed more than once            }            visited[u] = true;            order.add(u);            List<Integer> neighbours = adj.get(u);            for (int i = neighbours.size() - 1; i >= 0; i--) {   // reverse, so the first neighbour is popped first                if (!visited[neighbours.get(i)]) {                    stack.push(neighbours.get(i));                }            }        }        return order;    }    static int countComponents(List<List<Integer>> adj) {        boolean[] visited = new boolean[adj.size()];        int components = 0;        for (int start = 0; start < adj.size(); start++) {            if (!visited[start]) {                components++;                dfsRecursive(adj, start, visited, new ArrayList<>());    // visits the whole component            }        }        return components;    }    public static void main(String[] args) {        int[][] edges = {{0, 1}, {0, 2}, {1, 3}, {2, 3}, {3, 4}, {5, 6}};        List<List<Integer>> adj = buildGraph(8, edges, false);        System.out.println(adj);        System.out.println("bfs from 0:  " + bfsOrder(adj, 0));        int[] parent = new int[8];        int[] distance = bfsDistances(adj, 0, parent);        System.out.println("distances:   " + Arrays.toString(distance));        System.out.println("path 0 to 4: " + pathTo(4, parent, distance) + ", path 0 to 6: " + pathTo(6, parent, distance));        List<Integer> recursiveOrder = new ArrayList<>();        dfsRecursive(adj, 0, new boolean[8], recursiveOrder);        System.out.println("dfs recursive: " + recursiveOrder + ", iterative: " + dfsIterative(adj, 0));        System.out.println("components: " + countComponents(adj));    }}

[[1, 2], [0, 3], [0, 3], [1, 2, 4], [3], [6], [5], []]bfs from 0:  [0, 1, 2, 3, 4]distances:   [0, 1, 1, 2, 3, -1, -1, -1]path 0 to 4: [0, 1, 3, 4], path 0 to 6: []dfs recursive: [0, 1, 3, 2, 4], iterative: [0, 1, 3, 2, 4]components: 3

The path from 0 to 4 is 0, 1, 3, 4. There is also the path 0, 2, 3, 4, of the same length. BFS returns the one it discovered first, because 1 was queued before 2. Both have 3 edges, and either answers "fewest edges". The -1 entries in the distance array are the unreachable vertices, and asking for a path to an unreachable vertex gives an empty list.

A connected component is a maximal group of vertices that can reach each other. To count them, loop over all vertices. Whenever you find one that is not yet visited, you have found a new component: increase the counter and run a BFS or DFS from it, which marks the whole component as visited. Total cost is O(V + E), because each vertex and edge is processed once across all the searches.

In our example the components are {0, 1, 2, 3, 4}, {5, 6} and {7}, so the answer is 3. A single isolated vertex counts as a component.

A very common interview shape: a 2D grid where you move up, down, left and right. Treat every cell as a vertex, and every pair of neighbouring cells as an edge. You do not need to build an adjacency list. You compute neighbours on the fly with two small arrays of direction offsets:

int[] dr = {-1, 1, 0, 0};   // row change: up, down, left, rightint[] dc = {0, 0, -1, 1};   // column change

For a cell (r, c), its neighbour in direction d is (r + dr[d], c + dc[d]), valid if it lies inside the grid. If the problem allows diagonal moves, add four more offsets.

Problem (number of islands). A grid contains '1' (land) and '0' (water). An island is a group of land cells connected horizontally or vertically. Count the islands.

This is "count components" on a grid. For each land cell not yet visited, count a new island and flood-fill it with BFS or DFS, marking every connected land cell. To avoid a separate visited array, we overwrite visited land with '0'. (That changes the input, which is fine here, but mention it, or copy the grid first if the caller needs it.)

We use an explicit stack so that a big island does not cause a deep recursion.

// File: Main.javaimport java.util.ArrayDeque;import java.util.Deque;public class Main {    static int countIslands(char[][] grid) {        if (grid.length == 0) {            return 0;        }        int rows = grid.length;        int cols = grid[0].length;        int[] dr = {-1, 1, 0, 0};        int[] dc = {0, 0, -1, 1};        int islands = 0;        for (int r = 0; r < rows; r++) {            for (int c = 0; c < cols; c++) {                if (grid[r][c] != '1') {                    continue;                }                islands++;                Deque<int[]> stack = new ArrayDeque<>();                stack.push(new int[] {r, c});                grid[r][c] = '0';                               // mark visited by sinking the land                while (!stack.isEmpty()) {                    int[] cell = stack.pop();                    for (int d = 0; d < 4; d++) {                        int nr = cell[0] + dr[d];                        int nc = cell[1] + dc[d];                        if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == '1') {                            grid[nr][nc] = '0';                            stack.push(new int[] {nr, nc});                        }                    }                }            }        }        return islands;    }    public static void main(String[] args) {        char[][] grid = {            "11000".toCharArray(),            "11000".toCharArray(),            "00100".toCharArray(),            "00011".toCharArray()        };        System.out.println(countIslands(grid));        System.out.println(countIslands(new char[][] {"111".toCharArray(), "010".toCharArray()}));        System.out.println(countIslands(new char[][] {"000".toCharArray()}));        System.out.println(countIslands(new char[0][]));        System.out.println(countIslands(new char[][] {"101".toCharArray(), "010".toCharArray(), "101".toCharArray()}));    }}

31005

The first grid has three islands: the 2×2 block at the top left, the single cell in the middle, and the pair at the bottom right. In the last grid, the five land cells touch only diagonally, so with 4-direction moves each is its own island, which is why the answer is 5. Whether diagonals count is a detail you must clarify.

Time is O(rows × cols): each cell is pushed at most once, and each has four neighbours to check. Extra space is O(rows × cols) for the stack in the worst case.

Run DFS and carry the parent of the current vertex. If you meet an already-visited neighbour that is not the vertex you just came from, you have found a different route back to a visited vertex, so there is a cycle. We skip the parent, because in an undirected graph every edge appears in both directions, and the edge back to the parent is not a cycle.

(This version assumes a simple graph, with no repeated edges between the same pair of vertices. Two parallel edges form a cycle of length 2, and the parent trick would miss it.)

For a directed graph, "already visited" is not enough. A vertex can be reached by two different paths without any cycle (a diamond shape), so reaching a visited vertex does not prove a cycle. What we need is a vertex that is on the current DFS path. So each vertex has three states:

• Unvisited (white).
• In progress (grey): on the current recursion path.
• Done (black): fully explored, and no cycle found through it.

If DFS follows an edge to a grey vertex, that edge points back to an ancestor on the current path, which closes a cycle.

// File: Main.javaimport java.util.ArrayList;import java.util.List;public class Main {    static List<List<Integer>> buildGraph(int n, int[][] edges, boolean directed) {        List<List<Integer>> adj = new ArrayList<>();        for (int i = 0; i < n; i++) {            adj.add(new ArrayList<>());        }        for (int[] e : edges) {            adj.get(e[0]).add(e[1]);            if (!directed) {                adj.get(e[1]).add(e[0]);            }        }        return adj;    }    // Undirected, simple graph.    static boolean hasCycleUndirected(List<List<Integer>> adj) {        boolean[] visited = new boolean[adj.size()];        for (int start = 0; start < adj.size(); start++) {            if (!visited[start] && dfsUndirected(adj, start, -1, visited)) {                return true;            }        }        return false;    }    private static boolean dfsUndirected(List<List<Integer>> adj, int u, int parent, boolean[] visited) {        visited[u] = true;        for (int v : adj.get(u)) {            if (v == parent) {                continue;                          // the edge we came along is not a cycle            }            if (visited[v] || dfsUndirected(adj, v, u, visited)) {                return true;                       // reached a visited vertex by a different route            }        }        return false;    }    // Directed graph with three states: 0 unvisited, 1 on the current path, 2 finished.    static boolean hasCycleDirected(List<List<Integer>> adj) {        int[] state = new int[adj.size()];        for (int start = 0; start < adj.size(); start++) {            if (state[start] == 0 && dfsDirected(adj, start, state)) {                return true;            }        }        return false;    }    private static boolean dfsDirected(List<List<Integer>> adj, int u, int[] state) {        state[u] = 1;        for (int v : adj.get(u)) {            if (state[v] == 1) {                return true;                       // an edge back to the current path            }            if (state[v] == 0 && dfsDirected(adj, v, state)) {                return true;            }        }        state[u] = 2;        return false;    }    public static void main(String[] args) {        System.out.println(hasCycleUndirected(buildGraph(3, new int[][] {{0, 1}, {1, 2}}, false)));        System.out.println(hasCycleUndirected(buildGraph(3, new int[][] {{0, 1}, {1, 2}, {2, 0}}, false)));        System.out.println(hasCycleUndirected(buildGraph(6, new int[][] {{0, 1}, {3, 4}, {4, 5}, {5, 3}}, false)));        System.out.println(hasCycleUndirected(buildGraph(0, new int[][] {}, false)));        System.out.println(hasCycleDirected(buildGraph(3, new int[][] {{0, 1}, {1, 2}}, true)));        System.out.println(hasCycleDirected(buildGraph(3, new int[][] {{0, 1}, {1, 2}, {2, 0}}, true)));        System.out.println(hasCycleDirected(buildGraph(4, new int[][] {{0, 1}, {0, 2}, {1, 3}, {2, 3}}, true)));        System.out.println(hasCycleDirected(buildGraph(1, new int[][] {{0, 0}}, true)));    }}

falsetruetruefalsefalsetruefalsetrue

The third directed test is the diamond: vertex 3 is reached by two paths (0 -> 1 -> 3 and 0 -> 2 -> 3), but there is no cycle. A simple "visited" flag would wrongly report one, and the three-state version correctly says false. The last test is a self-loop, which counts as a directed cycle.

Complexity of both detectors: O(V + E) time, O(V) space (visited array plus recursion). Cycle detection in directed graphs is the foundation for topological sorting, in the next article.

Write complexities in V and E. Do not say "O(n)" for a graph without saying what n is. For a dense graph, E can be as large as V^2, in which case O(V + E) is O(V^2).

• Forgetting the visited check, which causes infinite loops on cyclic graphs.
• Marking visited when dequeuing instead of when enqueuing in BFS. The vertex is enqueued repeatedly, and the queue can grow far beyond V entries.
• Disconnected graphs. A single BFS or DFS reaches only one component. Loop over all vertices if you need everything.
• Directed vs undirected edges. Add both directions for undirected graphs. Adding only one silently turns the graph into a directed one.
• 1-based labels from the problem. Convert to 0-based, or allocate V + 1 slots.
• Recursion depth. Use an explicit stack when paths can be tens of thousands of vertices long.
• Grid bounds. Check 0 <= r < rows and 0 <= c < cols before reading the cell. Check whether the grid can be empty.
• Modifying the input grid when the caller needs it afterwards. Copy it or use a visited array.
• Using the undirected cycle trick on a directed graph, or a two-state visited flag in a directed one.
• Using a matrix for a huge sparse graph. It needs V^2 memory.
• Not clarifying whether diagonals count, whether self-loops or repeated edges can exist, and whether the graph can be empty.

static boolean dfs(List<List<Integer>> adj, int u, boolean[] visited) {    visited[u] = true;    for (int v : adj.get(u)) {        if (visited[v] || dfs(adj, v, visited)) {            return true;        }    }    return false;}

// File: Main.javaimport java.util.ArrayDeque;import java.util.ArrayList;import java.util.Arrays;import java.util.List;import java.util.Queue;public class Main {    static void dfs(List<List<Integer>> adj, int u, boolean[] visited, List<Integer> order) {        visited[u] = true;        order.add(u);        for (int v : adj.get(u)) {            if (!visited[v]) {                dfs(adj, v, visited, order);            }        }    }    public static void main(String[] args) {        int n = 6;        int[][] edges = {{0, 1}, {0, 2}, {1, 3}, {2, 3}, {3, 4}, {4, 5}};        List<List<Integer>> adj = new ArrayList<>();        for (int i = 0; i < n; i++) {            adj.add(new ArrayList<>());        }        for (int[] e : edges) {            adj.get(e[0]).add(e[1]);            adj.get(e[1]).add(e[0]);        }        int[] distance = new int[n];        Arrays.fill(distance, -1);        List<Integer> bfsOrder = new ArrayList<>();        Queue<Integer> queue = new ArrayDeque<>();        distance[0] = 0;        queue.offer(0);        while (!queue.isEmpty()) {            int u = queue.poll();            bfsOrder.add(u);            for (int v : adj.get(u)) {                if (distance[v] == -1) {                    distance[v] = distance[u] + 1;                    queue.offer(v);                }            }        }        List<Integer> dfsOrder = new ArrayList<>();        dfs(adj, 0, new boolean[n], dfsOrder);        System.out.println("bfs " + bfsOrder + " dfs " + dfsOrder + " dist " + Arrays.toString(distance));    }}

bfs [0, 1, 2, 3, 4, 5] dfs [0, 1, 3, 2, 4, 5] dist [0, 1, 1, 2, 3, 4]

// File: Main.javaimport java.util.ArrayDeque;import java.util.Queue;public class Main {    static int shortestPath(String[] maze) {        int rows = maze.length;        if (rows == 0) {            return -1;        }        int cols = maze[0].length();        if (maze[0].charAt(0) == '#' || maze[rows - 1].charAt(cols - 1) == '#') {            return -1;        }        int[][] distance = new int[rows][cols];        for (int[] row : distance) {            java.util.Arrays.fill(row, -1);        }        int[] dr = {-1, 1, 0, 0};        int[] dc = {0, 0, -1, 1};        Queue<int[]> queue = new ArrayDeque<>();        distance[0][0] = 0;        queue.offer(new int[] {0, 0});        while (!queue.isEmpty()) {            int[] cell = queue.poll();            if (cell[0] == rows - 1 && cell[1] == cols - 1) {                return distance[cell[0]][cell[1]];            }            for (int d = 0; d < 4; d++) {                int nr = cell[0] + dr[d];                int nc = cell[1] + dc[d];                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && maze[nr].charAt(nc) == '.' && distance[nr][nc] == -1) {                    distance[nr][nc] = distance[cell[0]][cell[1]] + 1;                    queue.offer(new int[] {nr, nc});                }            }        }        return -1;    }    public static void main(String[] args) {        System.out.println(shortestPath(new String[] {            "..#.",            ".##.",            "...."}));        System.out.println(shortestPath(new String[] {            ".#.",            "#..",            "..."}));        System.out.println(shortestPath(new String[] {"."}));        System.out.println(shortestPath(new String[] {"#"}));        System.out.println(shortestPath(new String[] {"...", "###", "..."}));    }}

5-10-1-1

// File: Main.javapublic class Main {    static int findProvinces(int[][] isConnected) {        int n = isConnected.length;        boolean[] visited = new boolean[n];        int provinces = 0;        for (int city = 0; city < n; city++) {            if (!visited[city]) {                provinces++;                dfs(isConnected, city, visited);            }        }        return provinces;    }    private static void dfs(int[][] isConnected, int city, boolean[] visited) {        visited[city] = true;        for (int other = 0; other < isConnected.length; other++) {            if (isConnected[city][other] == 1 && !visited[other]) {                dfs(isConnected, other, visited);            }        }    }    public static void main(String[] args) {        System.out.println(findProvinces(new int[][] {{1, 1, 0}, {1, 1, 0}, {0, 0, 1}}));        System.out.println(findProvinces(new int[][] {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}}));        System.out.println(findProvinces(new int[][] {{1, 1, 1}, {1, 1, 1}, {1, 1, 1}}));        System.out.println(findProvinces(new int[][] {}));    }}

2310

// File: Main.javaimport java.util.ArrayList;import java.util.List;public class Main {    static boolean dfsBuggy(List<List<Integer>> adj, int u, boolean[] visited) {        visited[u] = true;        for (int v : adj.get(u)) {            if (visited[v] || dfsBuggy(adj, v, visited)) {                return true;            }        }        return false;    }    static boolean dfsFixed(List<List<Integer>> adj, int u, int parent, boolean[] visited) {        visited[u] = true;        for (int v : adj.get(u)) {            if (v == parent) {                continue;            }            if (visited[v] || dfsFixed(adj, v, u, visited)) {                return true;            }        }        return false;    }    static List<List<Integer>> path() {        List<List<Integer>> adj = new ArrayList<>();        for (int i = 0; i < 3; i++) {            adj.add(new ArrayList<>());        }        int[][] edges = {{0, 1}, {1, 2}};        for (int[] e : edges) {            adj.get(e[0]).add(e[1]);            adj.get(e[1]).add(e[0]);        }        return adj;    }    public static void main(String[] args) {        System.out.println("buggy says cycle: " + dfsBuggy(path(), 0, new boolean[3]));        System.out.println("fixed says cycle: " + dfsFixed(path(), 0, -1, new boolean[3]));    }}

buggy says cycle: truefixed says cycle: false

// File: Main.javaimport java.util.ArrayDeque;import java.util.ArrayList;import java.util.Arrays;import java.util.List;import java.util.Queue;public class Main {    static boolean isBipartite(int n, int[][] edges) {        List<List<Integer>> adj = new ArrayList<>();        for (int i = 0; i < n; i++) {            adj.add(new ArrayList<>());        }        for (int[] e : edges) {            adj.get(e[0]).add(e[1]);            adj.get(e[1]).add(e[0]);        }        int[] color = new int[n];        Arrays.fill(color, -1);        for (int start = 0; start < n; start++) {            if (color[start] != -1) {                continue;            }            color[start] = 0;            Queue<Integer> queue = new ArrayDeque<>();            queue.offer(start);            while (!queue.isEmpty()) {                int u = queue.poll();                for (int v : adj.get(u)) {                    if (color[v] == -1) {                        color[v] = 1 - color[u];        // the opposite colour                        queue.offer(v);                    } else if (color[v] == color[u]) {                        return false;                   // an edge inside one group                    }                }            }        }        return true;    }    public static void main(String[] args) {        System.out.println(isBipartite(4, new int[][] {{0, 1}, {1, 2}, {2, 3}, {3, 0}}));        System.out.println(isBipartite(3, new int[][] {{0, 1}, {1, 2}, {2, 0}}));        System.out.println(isBipartite(5, new int[][] {{0, 1}, {2, 3}}));        System.out.println(isBipartite(0, new int[][] {}));        System.out.println(isBipartite(2, new int[][] {{0, 0}}));    }}

truefalsetruetruefalse

• Next: Shortest Paths and Topological Sorting handles weighted edges with Dijkstra's algorithm, and orders tasks that depend on each other.
• Related: Range Queries and Disjoint Set Union offers another way to count components and detect cycles when edges arrive one at a time.
• Practice habit: whenever a problem mentions "connected", "reachable", "network", "grid", "dependency" or "shortest steps", draw the vertices and edges first. Decide what a vertex is, and what an edge is, before you write any code.