Graphs in Java

A graph is a set of vertices (nodes) connected by edges. Trees and linked lists are special kinds of graphs. General graphs can have cycles, several paths between two vertices, and parts that aren't connected at all.

graph LR
    0 --> 1
    0 --> 2
    1 --> 3
    2 --> 3
    3 --> 4

Term	Meaning
directed / undirected	an edge goes one way (`0 → 1`) or both ways (`0 — 1`)
weighted	each edge has a cost, such as a distance or a price
neighbors of `v`	the vertices an edge from `v` leads to
degree	the number of edges at a vertex. Directed graphs distinguish in-degree and out-degree
path	a sequence of vertices joined by edges
cycle	a path that starts and ends at the same vertex
connected (undirected)	every vertex can reach every other vertex
DAG	a directed acyclic graph: directed, with no cycles

V is the number of vertices and E the number of edges. A graph can have up to V² edges (dense) or about as many edges as vertices (sparse).

Number the vertices, store the edges as indices

A tree node holds references to its children, and each node has one parent. In a graph, a vertex can be reached from many others, and cycles are allowed. A Node class with a List<Node> neighbors field works in Java, because object references can point anywhere and the garbage collector reclaims unreachable nodes. Such nodes still need a way to be identified, copied, and marked as visited, and a Node needs equals and hashCode to be used as a map key.

The standard approach is to number the vertices 0 to V - 1 and store edges as indices into a list. Indices are plain int values: they can be stored in arrays, queues, sets, and stacks and compared with ==, and a visited flag is one boolean[] slot.

Adjacency list

adj.get(v) is the list of v's neighbors. This is the default representation. It is a List<List<Integer>>: an ArrayList whose elements are ArrayLists of neighbor indices.

Java

import java.util.ArrayList;
import java.util.List;

public class Main {
    static List<List<Integer>> directed(int n, int[][] edges) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) {
            adj.get(e[0]).add(e[1]);
        }
        return adj;
    }

    static List<List<Integer>> undirected(int n, int[][] edges) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) {
            adj.get(e[0]).add(e[1]);
            adj.get(e[1]).add(e[0]); // store the edge in both directions
        }
        return adj;
    }

    public static void main(String[] args) {
        int[][] edges = {{0, 1}, {0, 2}, {1, 3}, {2, 3}, {3, 4}};
        List<List<Integer>> d = directed(5, edges);
        List<List<Integer>> u = undirected(5, edges);
        System.out.println("directed:   " + d);
        System.out.println("undirected: " + u);
        System.out.println("neighbors of 3 (undirected): " + u.get(3));
    }
}

Output

directed:   [[1, 2], [3], [3], [4], []]
undirected: [[1, 2], [0, 3], [0, 3], [1, 2, 4], [3]]
neighbors of 3 (undirected): [1, 2, 4]

For a weighted graph, store (neighbor, weight) pairs, for example as int[]{neighbor, weight} in a List<List<int[]>>.

Adjacency matrix

matrix[u][v] is true if there's an edge from u to v. Checking a specific edge is O(1), but the matrix always uses V² space, and listing a vertex's neighbors means scanning a whole row.

Java

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        int n = 4;
        boolean[][] matrix = new boolean[n][n];
        int[][] edges = {{0, 1}, {0, 2}, {1, 3}, {2, 3}};
        for (int[] e : edges) {
            matrix[e[0]][e[1]] = true;
        }
        System.out.println("edge 0 -> 2? " + matrix[0][2]);
        List<Integer> neighborsOf0 = new ArrayList<>();
        for (int v = 0; v < n; v++) {
            if (matrix[0][v]) neighborsOf0.add(v);
        }
        System.out.println("neighbors of 0: " + neighborsOf0);
    }
}

Output

edge 0 -> 2? true
neighbors of 0: [1, 2]

Edge list

A plain int[][] where each row is {u, v}. It's the usual input format, and some algorithms work on it directly (union-find, Kruskal's algorithm). Most traversals convert it to an adjacency list first.

Comparing the representations

	Adjacency list	Adjacency matrix	Edge list
space	`O(V + E)`	`O(V²)`	`O(E)`
is there an edge `u → v`?	`O(deg u)`	`O(1)`	`O(E)`
list the neighbors of `v`	`O(deg v)`	`O(V)`	`O(E)`
add an edge	`O(1)`	`O(1)`	`O(1)`
best for	most problems (sparse graphs)	dense graphs, many edge checks	union-find, sorting edges by weight

Vertices with names

When vertices are strings or other values, either give each name an index first, or use a HashMap of neighbor lists directly (computeIfAbsent creates the list on the first edge from a name, and putIfAbsent stores a value only when the key is missing):

Java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        String[][] flights = {{"SFO", "JFK"}, {"SFO", "SEA"}, {"SEA", "JFK"}, {"JFK", "LHR"}};

        // Option 1: a HashMap from each name to its neighbors
        Map<String, List<String>> adj = new HashMap<>();
        for (String[] f : flights) {
            adj.computeIfAbsent(f[0], k -> new ArrayList<>()).add(f[1]);
        }
        System.out.println("from SFO: " + adj.get("SFO"));

        // Option 2: map names to indices once, then use a List<List<Integer>>
        Map<String, Integer> id = new HashMap<>();
        for (String[] f : flights) {
            for (String name : f) {
                id.putIfAbsent(name, id.size());
            }
        }
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < id.size(); i++) graph.add(new ArrayList<>());
        for (String[] f : flights) {
            graph.get(id.get(f[0])).add(id.get(f[1]));
        }
        int sfo = id.get("SFO");
        System.out.println(id.size() + " airports, SFO is vertex " + sfo + " with neighbors " + graph.get(sfo));
    }
}

Output

from SFO: [JFK, SEA]
4 airports, SFO is vertex 0 with neighbors [1, 2]

Keeping track of visited vertices

Because graphs can have cycles, every traversal must remember which vertices it has already processed, or it may loop forever. With vertices numbered 0..V, a boolean[n] is simpler and faster than a HashSet. When vertices are not numbered, Set.add marks a value and returns false if it was already in the set:

Java

import java.util.HashSet;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        Set<Integer> seen = new HashSet<>();
        boolean first = !seen.add(1);  // add returns false when the value was already present
        boolean second = !seen.add(1);
        System.out.println(first + " " + second);
    }
}

Output

false true

Which algorithm for which question

Question	Algorithm	Time	Lesson
visit every vertex	BFS or DFS	`O(V + E)`	BFS, DFS
can `a` reach `b`?	BFS or DFS	`O(V + E)`	Path exists
fewest edges from `a` to `b`	BFS	`O(V + E)`	Shortest path
cheapest path, non-negative weights	Dijkstra with a min-heap	`O((V + E) log V)`
does a directed graph have a cycle?	DFS with three states, or topological sort	`O(V + E)`	Detect a cycle
a vertex that reaches all others	DFS, keeping the last root	`O(V + E)`	Mother vertex
is an undirected graph a tree? / connected parts	union-find	about `O(E)`	Graph valid tree
order tasks by their dependencies	topological sort	`O(V + E)`