Graphs

A graph is vertices connected by edges. That is the most general structure in this track — a tree is just a graph with no cycles and one path between any two nodes, and a linked list is a graph where everything has one neighbour.

Vocabulary

Those first three properties are the ones to establish before writing any graph code — they decide which algorithms are even applicable. Dijkstra needs weights and non-negative ones; cycle detection differs entirely between directed and undirected graphs.

Where graphs actually are

• Social networks — people as vertices, friendships as undirected edges. "Following" is directed.
• Maps — intersections and roads, weighted by distance or time.
• Dependencies — Maven, npm, or a build. Directed, and a cycle is an error you must detect.
• The web — pages and links. Directed; PageRank is a graph algorithm.
• State machines — states and transitions.

Two representations

Adjacency matrix — a V × V grid where matrix[a][b] says whether an edge exists.

Adjacency list — a map from each vertex to its neighbours.

Real graphs are overwhelmingly sparse: a social network might have a million users averaging a few hundred friends each, not a million each. A matrix would be 10¹² cells, almost all empty. The list stores what exists and nothing else, so it is the default — and traversal only ever iterates neighbours, which is the list's fast operation.

    private final Map<String, Set<String>> adjacency = new HashMap<>();
    private final boolean directed;

Adding edges

    /** LinkedHashSet, so traversal order is insertion order and the tests are deterministic. */
    public void addEdge(String a, String b) {
        addVertex(a);
        addVertex(b);
        adjacency.get(a).add(b);
        if (!directed) {
            adjacency.get(b).add(a);
        }
    }

An undirected edge is stored twice, once in each direction. That is not redundancy to optimise away — it is what makes "who are b's neighbours" answerable without scanning the whole graph.

A Set rather than a List means adding the same edge twice is harmless. LinkedHashSet specifically, because plain HashSet iteration order is unspecified, and a traversal whose output order shifts between runs is untestable:

        Check.isTrue(g.neighbours("b").contains("a"), "undirected edge is symmetric");
        Graph directed = new Graph(true);
        directed.addEdge("x", "y");
        Check.isTrue(directed.neighbours("x").contains("y"), "directed edge forwards");
        Check.isTrue(!directed.neighbours("y").contains("x"), "but not backwards");

neighbours returns Set.of() for an unknown vertex rather than null, so callers can iterate the result without a null check — a small decision that removes a whole class of bug from every traversal built on top.

Traversal is the foundation

Nearly every graph algorithm is a traversal with bookkeeping added. The two traversals are BFS and DFS, and they are the same algorithm with one difference: BFS keeps the frontier in a queue, DFS in a stack.

⚠️ Cycles, and the visited set

The one thing a graph has that a tree does not is cycles — and a traversal without a visited set runs forever on one.

        // A cycle must not loop forever - that is what the visited set is for.
        Graph cyclic = new Graph();
        cyclic.addEdge("p", "q");
        cyclic.addEdge("q", "r");
        cyclic.addEdge("r", "p");
        Check.eq(cyclic.breadthFirst("p").toString(), "[p, q, r]", "BFS terminates on a cycle");
        Check.eq(cyclic.depthFirst("p").toString(), "[p, q, r]", "DFS terminates on a cycle");

Note that an undirected edge is itself a two-cycle — a–b means you can go a→b→a — so this is not an edge case you can defer. Every undirected graph needs the visited set from the first line of code.

Connectivity

    /** Whether a path exists at all - the connectivity question. */
    public boolean connected(String from, String to) {
        return !shortestPath(from, to).isEmpty();
    }

A graph need not be one connected piece. The test graph has an isolated vertex f reachable from nothing, and a traversal from a will never find it:

        Check.eq(g.breadthFirst("f").toString(), "[f]", "isolated vertex");
        Check.isTrue(!g.connected("a", "f"), "not connected");

So "visit every vertex" is not one traversal — it is a traversal started from every not-yet-visited vertex, which is also how you count connected components.

Algorithms worth knowing by name

Two of those are worth flagging. Dijkstra is wrong with negative weights — it is a greedy algorithm, and it commits to the nearest vertex on the assumption that no later path can undercut it, which a negative edge violates. And topological sort only exists for an acyclic graph: a cycle in a dependency graph means there is no valid build order, which is exactly the error a package manager reports.

What to remember

• Vertices and edges; establish directed/weighted/cyclic before choosing an algorithm.
• Adjacency list by default — real graphs are sparse.
• An undirected edge is stored in both directions.
• Always keep a visited set; an undirected edge is already a cycle.
• A graph may be disconnected, so one traversal need not reach everything.
• Dijkstra needs non-negative weights; topological sort needs acyclicity.