DSA in Java: Graphs — BFS & DFS Explained (Beginner Guide)

Graphs are the data structure behind some of the most important systems you use every day: social networks ("people you may know"), maps and GPS routing, the web itself, recommendation engines. They can feel intimidating, but the core idea is simple, and the two traversal techniques — BFS and DFS — reuse the queues and recursion you already know. Let's make graphs click.

What is a graph?

A graph is just a set of nodes (also called vertices) connected by edges (the links between them). That's it. A social network is a graph: people are nodes, friendships are edges. A map is a graph: cities are nodes, roads are edges.

A couple of quick vocabulary notes: edges can be directed (one-way, like "A follows B" on Twitter) or undirected (mutual, like Facebook friendship). Edges can also carry weights (e.g. the distance of a road). For this beginner lesson we'll keep it simple.

Representing a graph in code

The most common way is an adjacency list: a map from each node to the list of its neighbours. It's compact and easy to work with:

// each node maps to a list of its neighbours
Map<String, List<String>> graph = new HashMap<>();
graph.put("A", List.of("B", "C"));
graph.put("B", List.of("A", "C", "D"));
graph.put("C", List.of("A", "B", "D"));
graph.put("D", List.of("B", "C"));

The two ways to explore: BFS and DFS

Most graph problems come down to visiting nodes in some order. There are two fundamental strategies, and knowing both is essential.

BFS — Breadth-First Search (explore level by level)

BFS explores like ripples spreading in a pond: all immediate neighbours first, then their neighbours, and so on. It uses a queue (FIFO). BFS is perfect for finding the shortest path in an unweighted graph, because it reaches closer nodes before farther ones:

void bfs(Map<String,List<String>> graph, String start) {
    Queue<String> queue = new LinkedList<>();
    Set<String> visited = new HashSet<>();  // avoid revisiting!
    queue.offer(start);
    visited.add(start);
    while (!queue.isEmpty()) {
        String node = queue.poll();          // take from the front
        System.out.println(node);
        for (String next : graph.get(node)) {
            if (!visited.contains(next)) {
                visited.add(next);
                queue.offer(next);           // add neighbours to the back
            }
        }
    }
}

DFS — Depth-First Search (go deep, then backtrack)

DFS explores like walking a maze: follow one path as far as it goes, then back up and try another. It naturally uses recursion (or a stack). DFS is great for problems like "is there any path?", detecting cycles, and exploring all connected pieces:

void dfs(Map<String,List<String>> graph, String node, Set<String> visited) {
    if (visited.contains(node)) return;   // already seen — stop
    visited.add(node);
    System.out.println(node);
    for (String next : graph.get(node)) {
        dfs(graph, next, visited);           // recurse deeper
    }
}

BFS vs DFS — which to use?

Both visit every node and edge once, so both are O(V + E) (vertices plus edges). Pick BFS when distance/shortest-path matters; pick DFS when you just need to explore or go deep.

Graphs felt like the "final boss" of DSA to me — until I realised they're mostly just the earlier structures combined. A graph is nodes-and-pointers (like linked lists), BFS is a queue plus a HashSet, and DFS is recursion. Nearly every graph problem is a variation of "traverse with BFS or DFS and track visited nodes." Memorise those two templates cold — they're the backbone of the entire topic — and the scary reputation of graphs melts away. From routing to social networks, this is genuinely some of the most applicable DSA you'll ever learn.

Key takeaways

• A graph is nodes connected by edges; represent it with an adjacency list (map of node → neighbours).
• BFS uses a queue, explores level by level, and finds shortest paths in unweighted graphs.
• DFS uses recursion/stack, goes deep, and suits path-existence, cycles, and connectivity.
• Always track a visited set to avoid infinite loops on cycles. Both traversals are O(V + E).

← Previous: DSA Lesson 11 — Heaps & Priority Queues
Next: DSA Lesson 13 — Dynamic Programming →
↑ Back to the DSA roadmap