Graphs 101

Nodes, edges, and the three big distinctions

A graph is a set of nodes (also called vertices) plus a set of edges, where each edge connects two nodes. That is the whole definition. Everything else is a variation on it, and three variations matter most.

First, undirected versus directed. In an undirected graph, edges are two-way streets: if Alice and Bob are friends, the friendship works in both directions. In a directed graph, each edge is an arrow: Twitter follows, course prerequisites, and web links all point one way, and an edge from A to B says nothing about B to A.

Second, unweighted versus weighted. Sometimes an edge just exists; other times it carries a number called a weight. The distance of a road, the cost of a flight, the strength of a connection. Weights change which algorithms apply, since the shortest path now means cheapest, not fewest hops.

Third, unlike a tree, a graph may contain cycles (paths that loop back to their start) and it may even be disconnected, splitting into separate islands with no edges between them. No root, no parent-child direction, no guarantees. Every graph algorithm has to cope with that freedom, which is why the visited set shows up in the next lesson.

Adjacency list vs adjacency matrix

A tree node carries references to its children, but graph problems usually hand you nodes as plain numbers 0 through n - 1 and a list of edges. You must choose how to store who connects to whom, and there are two standard answers.

An adjacency matrix is an n by n grid of booleans (or weights) where cell [u][v] is true if an edge runs from u to v. Checking whether two specific nodes are connected is O(1), which is lovely, but the grid takes O(n squared) memory regardless of how many edges exist, and just listing one node's neighbors means scanning a full row of n entries.

An adjacency list stores, for each node, a list of only its actual neighbors, like each person keeping their own contact list rather than a table of everyone-by-everyone. Memory is O(n + e) for e edges, and iterating a node's neighbors touches only real neighbors. Since real-world graphs are usually sparse (a million users, but each with a few hundred friends, nowhere near a million) the adjacency list wins almost every time and is the default in interviews. Reach for a matrix only when the graph is tiny or genuinely dense.

Building an adjacency list in Java

The standard Java representation is a List<List<Integer>>: the outer list is indexed by node number, and the inner list at index u holds u's neighbors. Given n nodes and an edge array like [[0,1],[1,2],[2,0]], you create n empty inner lists, then record each edge.

The one detail that trips people up is direction. For an undirected graph, a single edge between u and v must be recorded twice (v goes into u's list and u goes into v's list) because either endpoint can be the starting point of a walk. For a directed graph, record it once, from source to destination. Forgetting the second add on an undirected graph is one of the most common silent bugs in graph solutions.

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

Variations you will meet

A few adjustments cover nearly every problem. For a weighted graph, store neighbor-weight pairs. Commonly a small int array per edge, so adj.get(u) holds arrays like [v, w] meaning an edge to v with weight w. For graphs whose nodes are strings or arbitrary labels rather than 0 to n - 1, use a Map<String, List<String>> instead of an outer list.

And remember that many graphs arrive in disguise. A 2D grid of cells is a graph where each cell neighbors the cells up, down, left, and right, no adjacency list needed, since neighbors are computed from coordinates on the fly. Prerequisite lists, word-transformation puzzles, and state-machine problems are all graphs the moment you ask what are the nodes, and what are the edges? Training yourself to ask that question is half of graph problem-solving.

Representing a graph is the setup; the payoff is traversal. Next comes BFS and DFS. The two fundamental ways to explore a graph, and the engines inside the majority of graph interview problems.

List<List<int[]>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) {
    adj.add(new ArrayList<>());
}
adj.get(0).add(new int[]{1, 5});
adj.get(1).add(new int[]{0, 5});

Frequently asked