Graphs

Java has no graph type. You build one out of the collections you already have, and which ones you choose is the first real decision in any graph problem — because the two obvious representations differ by a factor of sixty on an ordinary social graph.

#The representation decision, in numbers

A hundred thousand people, about eight friends each:

###   adjacency MATRIX: 100000 x 100000 = 10,000,000,000 cells -> 1,192 MB at 1 bit each
###   adjacency LIST:   400,000 edges -> about 19 MB
###   density: 400,000 edges out of 5,000,000,000 possible = 0.00800%

1,192 MB against 19 MB — and the matrix figure is the best possible case, one bit per cell. In Java a boolean[][] uses a byte per element, so the honest number is closer to ten gigabytes.

The last line is why. The graph uses eight thousandths of one percent of the possible edges, and a matrix reserves space for all of them. That is what "sparse" means, and almost every real graph is sparse: social networks, road maps, dependency graphs, the web.

#The two representations

Adjacency list — for each vertex, the vertices it points to:

Map<String, List<String>> graph = new HashMap<>();
graph.computeIfAbsent("ana", k -> new ArrayList<>()).add("bo");

• Space O(V + E). You pay for edges that exist.
• "Who are ana's neighbours?" O(degree) — walk her list.
• "Is ana connected to zoe?" O(degree) — scan it.

Adjacency matrix — a V × V grid, true where an edge exists:

boolean[][] edge = new boolean[n][n];
edge[ana][bo] = true;

• Space O(V²), whether or not the edges exist.
• "Is ana connected to zoe?" O(1) — one array read.
• "Who are ana's neighbours?" O(V) — you must scan the whole row, including all the false cells.

So the rule: lists unless the graph is dense or you need constant-time edge lookup. In practice that means lists, with the exception of small graphs, and of algorithms whose inner loop is "is there an edge here" — some shortest-path and matrix-multiplication formulations genuinely want the matrix.

A third option worth knowing: an edge list, just List<Edge>. Useless for traversal and exactly right for algorithms that sort edges — Kruskal's minimum spanning tree being the standard case.

#The vocabulary, and why each word changes the code

• Directed or undirected. "Follows" is directed; "is friends with" is not. In an adjacency list an undirected edge is stored twice, once in each vertex's list — which is why the measurement above counted 400,000 entries for 200,000 friendships. Forgetting the second insert is the most common graph bug, and it presents as a traversal that mysteriously does not reach half the graph.
• Weighted or not. A weight turns List<String> into List<Edge> with a cost on it, and it changes which algorithm is correct — breadth-first search finds the shortest path only when every edge costs the same.
• Cyclic or acyclic. A cycle is why every traversal needs a visited set. A directed acyclic graph is a special case worth recognising, because it admits a topological sort — which is what a build tool does with your modules and what Spring does with your beans.
• Connected or not. A graph can be several islands. An algorithm that starts at one vertex only ever sees that vertex's island, which is why "count the connected components" means starting again from every unvisited vertex.

#Modelling, which is the part that is actually hard

The algorithms are standard. Recognising that you have a graph is not, and this is where the skill is:

Two of those are worth pausing on because they are this course's own subject matter. A dependency cycle in a build is a cycle in a directed graph, and the error a build tool gives you is a cycle detection reporting its findings. So is BeanCurrentlyInCreationException — the Spring course's circular dependency is the same algorithm on a different graph.

#Building one, without a library

class Graph {
    private final Map<String, List<String>> adjacency = new HashMap<>();
 
    void addEdge(String from, String to) {
        adjacency.computeIfAbsent(from, k -> new ArrayList<>()).add(to);
        adjacency.computeIfAbsent(to, k -> new ArrayList<>());   // so it exists as a vertex
    }
 
    List<String> neighbours(String v) {
        return adjacency.getOrDefault(v, List.of());
    }
}

Two details in those seven lines carry most of the bugs:

• The second computeIfAbsent. Without it, a vertex with no outgoing edges is not in the map, and a traversal that reaches it gets null rather than an empty list. getOrDefault is the other half of the same defence.
• List or Set for the neighbours. A List allows duplicate edges and preserves insertion order; a Set prevents duplicates and costs more per vertex. Which you want depends on whether "ana follows bo twice" is meaningful, and deciding it explicitly beats discovering it.

For anything substantial, use a library — JGraphT is the usual Java answer — for the same reason you do not write your own HashMap. Building one by hand is for understanding it and for interviews.