Graphs: vertices, edges, DFS and BFS

← Back to the section

Many real-world tasks are about connections: cities and roads, people and acquaintances, tasks and their dependencies. The structure that models connections directly is called a graph. Unlike trees (which, by the way, are a special case of a graph), a graph has no root and no hierarchy.

Vertices and edges

A graph consists of vertices (nodes) and edges — links between pairs of vertices. Two pairs of definitions set the type of a graph:

• undirected / directed. In an undirected graph an edge goes both ways (friendship is mutual); in a directed one it goes one way, with an arrow (task A must be done before B).
• unweighted / weighted. An edge may carry a weight — a number: road length, cost, time (a separate article covers that); here an edge either exists or not.

How a graph is stored

There are two ways to represent a graph.

An adjacency matrix is a square table of size "vertices × vertices", where the cell at the intersection of i and j says whether there is an edge between vertices i and j. Checking a link between two vertices is instant, but memory grows as the square of the vertex count, even when there are few edges.

An adjacency list stores, for every vertex, a list of its neighbours. That is frugal when edges are few (a sparse graph), and most graphs are sparse — this is the common choice.

Two ways to traverse a graph

The main operation on a graph is a traversal: visiting every vertex in an orderly way, moving along edges. There are two ways to do it.

Depth-first search (DFS). Go along one path as far as possible until you hit a dead end (a vertex with no unvisited neighbours), then step back and try another path. This behaviour is naturally expressed by a stack or by recursion — like walking a maze with the "keep one hand on the wall" rule.

Breadth-first search (BFS). The opposite: explore the graph in layers — first the neighbours of the start vertex, then the neighbours of those, and so on in waves; this is a queue. BFS reaches vertices in order of distance from the start, which is why it is used to find the shortest path by number of edges in an unweighted graph.

The difference between the traversals is not in the logic but in which end the next vertex is taken from: the very same code takes from the head of the queue and spreads in waves, or from the tail (that is, a stack) and dives deep.

live example

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

class GraphWalk {
    static final Map<String, List<String>> GRAPH = Map.of(
            "A", List.of("B", "C"), "B", List.of("D", "E"), "C", List.of("E", "F"),
            "D", List.of(), "E", List.of(), "F", List.of());

    static List<String> walk(String start, boolean depthFirst) {
        List<String> order = new ArrayList<>();
        Set<String> seen = new HashSet<>();
        Deque<String> pending = new ArrayDeque<>();
        pending.add(start);
        while (!pending.isEmpty()) {
            String node = depthFirst ? pending.pollLast() : pending.pollFirst();
            if (!seen.add(node)) continue;
            order.add(node);
            pending.addAll(GRAPH.get(node));
        }
        return order;
    }

    public static void main(String[] args) {
        System.out.println("breadth-first: " + walk("A", false));
        System.out.println("depth-first:   " + walk("A", true));
    }
}

Breadth-first gives A, B, C, D, E, F — exactly the levels from the picture. Depth-first gives A, C, F, E, B, D: a stack hands back the neighbour added last, so the traversal runs down the C branch to its end and only then comes back for B. The seen.add check is needed by both: without it a cycle in the graph would spin the traversal forever.

What traversals give you

A lot is built on traversals:

• connectivity. A traversal from a vertex visits everything reachable from it — that is how you check whether a graph is connected and into which components it falls apart.
• spanning tree. The edges the traversal went along form a tree that connects every vertex without cycles — the "skeleton" of the graph.
• topological sort. In a directed graph without cycles (say, "task A before task B") the vertices can be laid out in a linear order where every dependency comes before the thing that depends on it. That is how schedulers decide the order of a build or of a batch of tasks.

How it is done in Java

Every other structure in this course has a ready-made class in the standard library. A graph is the exception: there is no Graph class in Java, so you assemble one yourself. Not from scratch, but from existing collections — and which ones you pick decides the real cost of a traversal.

An adjacency list is a Map from a vertex to the list of its neighbours; computeIfAbsent creates the list for a new vertex. HashMap finds the neighbour list in O(1) on average, and the ArrayList inside is a dense array that a loop walks without cache misses. If vertices are numbered consecutively (0…N−1), no Map is needed at all: an array of lists is taken, and finding neighbours becomes an index lookup. An adjacency matrix is a boolean[][]; every cell takes a byte, so at a hundred thousand vertices the matrix asks for about ten gigabytes. Hence the rule: a matrix only for small dense graphs.

Both traversals rest on ArrayDeque: breadth-first it is a queue (addLast at the tail, pollFirst at the head), depth-first the same class used as a stack (push and pop). Inside it is a circular array, and both operations are amortized O(1). LinkedList formally does the same, but pays a separate node object per element. Stack is not used at all: it wraps a synchronized Vector from the earliest versions of Java. Visited vertices are kept in a HashSet (O(1) on average), or in a boolean[] when vertices are numbered — faster and without wrapper objects.

There is one trap here, and it is a nasty one. If a vertex is your own class without equals and hashCode, HashMap compares vertices by reference. Two "identical" vertices become different keys, the graph quietly falls apart, and the traversal finds less than it should — with no exception, just a wrong answer. A smaller detail from the same root: neighbours keep their insertion order, while the vertices themselves come out of a Map iteration in bucket order — when a reproducible traversal matters, the keys are kept in a LinkedHashMap.

In short

• A graph is vertices and edges between them; it models connections (networks, routes, dependencies). It can be directed or undirected, weighted or unweighted.
• Two ways to store it: an adjacency matrix (instant answer about a link, but memory ~vertices²) and an adjacency list (frugal for sparse graphs).
• Depth-first search (DFS) dives deep and backs out — a stack or recursion.
• Breadth-first search (BFS) spreads in waves — a queue; it finds the shortest path by number of edges.
• Traversals give you connectivity checks, the spanning tree and the topological sort of dependencies.
• Java has no Graph class: the adjacency list is built on HashMap, the traversal on ArrayDeque, visited vertices in a HashSet. A vertex key without equals and hashCode silently tears the graph apart.

What to read next

• Weighted graphs — when edges carry a weight: the minimum spanning tree and Dijkstra's shortest path.
• Stacks and queues — why traversals rest on ArrayDeque rather than on Stack.
• Hash tables — what HashMap does with a vertex key that has no equals and hashCode.
• Choosing a data structure — a cheat sheet of operation costs when a structure has to fit the task.