Graph Representation (Java)

The simplest way to represent a graph in code is with a two-dimensional grid. Picture a spreadsheet where both the row headers and column headers are vertex numbers (0, 1, 2, … V−1). Each cell answers one binary question: "Is there an edge from vertex i to vertex j?"

If the answer is yes, we write 1 (or the edge weight) in that cell. If not, the cell stays 0.

Think of a seating arrangement at a dinner party. You make a chart with all guest names along the top and down the side. If two guests know each other, you check the box where their row and column meet. This chart is your adjacency matrix.

For a graph with V vertices, we create a V × V two-dimensional integer array:

int[][] adj = new int[V][V];

In Java, new int[V][V] automatically initializes every cell to 0 — no manual initialization needed (unlike some other languages). For each edge (u, v):

• Undirected: Set adj[u][v] = 1 AND adj[v][u] = 1
• Directed: Set only adj[u][v] = 1
• Weighted: Store the weight: adj[u][v] = weight

This representation makes checking if a specific edge exists extremely fast — it is a direct array access at adj[u][v], which takes constant O(1) time.

Let's build the adjacency matrix for Example 1: V = 3, edges = [(0,1), (0,2), (1,2)], undirected.

Step 1: Declare int[][] adj = new int[3][3];. Java initializes all cells to 0.

adj = [[0, 0, 0],
       [0, 0, 0],
       [0, 0, 0]]

Step 2: Process edge (0,1). Set adj[0][1] = 1.

adj = [[0, 1, 0],
       [0, 0, 0],
       [0, 0, 0]]

Step 3: Undirected mirror: set adj[1][0] = 1.

adj = [[0, 1, 0],
       [1, 0, 0],
       [0, 0, 0]]

Step 4: Process edge (0,2). Set adj[0][2] = 1.

adj = [[0, 1, 1],
       [1, 0, 0],
       [0, 0, 0]]

Step 5: Mirror: set adj[2][0] = 1.

adj = [[0, 1, 1],
       [1, 0, 0],
       [1, 0, 0]]

Step 6: Process edge (1,2). Set adj[1][2] = 1.

adj = [[0, 1, 1],
       [1, 0, 1],
       [1, 0, 0]]

Step 7: Mirror: set adj[2][1] = 1.

adj = [[0, 1, 1],
       [1, 0, 1],
       [1, 1, 0]]

Step 8: All 3 edges have been processed. The adjacency matrix is complete. The matrix is symmetric along the main diagonal (because the graph is undirected), and the diagonal is all zeros (no self-loops).

1. Read the number of vertices V and edges E.
2. Create a V × V integer array: int[][] adj = new int[V][V]; (auto-initialized to 0 in Java).
3. For each edge (u, v) read from input:
   • Set adj[u][v] = 1 (or the weight for weighted graphs).
   • If the graph is undirected, also set adj[v][u] = 1.
   • If directed, set only adj[u][v].
4. To check if an edge exists from i to j: read adj[i][j] — returns 1 if edge exists, 0 otherwise.
5. To find all neighbors of vertex i: loop through column index j from 0 to V−1, collecting every j where adj[i][j] != 0.

Time Complexity:

• Building the matrix: O(V² + E)

  • new int[V][V] in Java allocates and zero-fills V² cells → O(V²).
  • Processing each of the E edges takes O(1) per edge → O(E).
  • Total: O(V²) dominates.

• Checking if edge (u, v) exists: O(1) — direct array access adj[u][v].

• Finding all neighbors of vertex u: O(V) — must scan all V cells in row u to find non-zero entries.

Space Complexity: O(V²)

The 2D array always uses V² integer cells regardless of edge count. For a graph with 10,000 vertices and only 100 edges, we allocate 100,000,000 cells — 99.999% are wasted zeros. In Java, each int is 4 bytes, so a 10,000 × 10,000 matrix uses ~400 MB of memory.

Instead of pre-allocating space for every possible connection, what if each vertex only stored the neighbors it actually has?

Imagine you maintain a contact list on your phone. You do not have an entry for every human on Earth — you only store the numbers of people you actually know. If you have 50 contacts, your list has 50 entries. If your friend has 200 contacts, their list has 200 entries.

The adjacency list works exactly like this. We create an array of V lists — one list per vertex. Each list holds only the actual neighbors of that vertex:

ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
for (int i = 0; i < V; i++) {
    adj.add(new ArrayList<>());
}

For each edge (u, v):

• adj.get(u).add(v); — add v to u's neighbor list
• For undirected: adj.get(v).add(u); — add u to v's list as well

For weighted graphs, we store pairs of (neighbor, weight). In Java, a clean approach is:

ArrayList<ArrayList<int[]>> adj = new ArrayList<>();
// Each int[] is {neighbor, weight}
adj.get(u).add(new int[]{v, weight});

Or you can create a Pair class or use ArrayList<ArrayList<int[]>>.

This is the standard representation used in virtually all graph algorithm implementations in Java — BFS, DFS, Dijkstra, Kruskal, topological sort, and more all expect adjacency lists.

Let's build the adjacency list for Example 1: V = 3, edges = [(0,1), (0,2), (1,2)], undirected.

Step 1: Create 3 empty ArrayLists, one per vertex.

adj.get(0) = []
adj.get(1) = []
adj.get(2) = []

Step 2: Process edge (0,1). Call adj.get(0).add(1) — add vertex 1 to vertex 0's list.

adj.get(0) = [1]
adj.get(1) = []
adj.get(2) = []

Step 3: Undirected mirror: call adj.get(1).add(0) — add vertex 0 to vertex 1's list.

adj.get(0) = [1]
adj.get(1) = [0]
adj.get(2) = []

Step 4: Process edge (0,2). Call adj.get(0).add(2).

adj.get(0) = [1, 2]
adj.get(1) = [0]
adj.get(2) = []

Step 5: Mirror: call adj.get(2).add(0).

adj.get(0) = [1, 2]
adj.get(1) = [0]
adj.get(2) = [0]

Step 6: Process edge (1,2). Call adj.get(1).add(2).

adj.get(0) = [1, 2]
adj.get(1) = [0, 2]
adj.get(2) = [0]

Step 7: Mirror: call adj.get(2).add(1).

adj.get(0) = [1, 2]
adj.get(1) = [0, 2]
adj.get(2) = [0, 1]

Step 8: All edges processed. The adjacency list is complete. Each vertex stores only its actual neighbors. Total entries: 6 (two per undirected edge). To iterate over vertex 0's neighbors, just loop over adj.get(0) — instant access to [1, 2] without scanning any zeros.

1. Read the number of vertices V and edges E.
2. Create an ArrayList<ArrayList<Integer>> with V empty inner lists:

   ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
   for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
   

3. For each edge (u, v) from input:
   • adj.get(u).add(v); — add v to u's neighbor list.
   • If undirected, also adj.get(v).add(u);.
   • If directed, only add to adj.get(u).
   • For weighted edges with weight w: adj.get(u).add(new int[]{v, w}); (using ArrayList<ArrayList<int[]>>).
4. To iterate over all neighbors of vertex i: for (int neighbor : adj.get(i)) { ... }.
5. To check if edge (u, v) exists: scan adj.get(u) for value v — takes O(degree(u)) time.

Time Complexity:

• Building the list: O(V + E)

  • Creating V empty ArrayLists takes O(V).
  • Each edge is processed in O(1) amortized time (ArrayList add() is amortized O(1) in Java).
  • Total: O(V + E).

• Checking if edge (u, v) exists: O(degree(u))

  • Must scan vertex u's neighbor list. In the worst case, degree can be V−1, but for sparse graphs it is typically much smaller.
  • If O(1) edge checking is critical, you can additionally maintain a HashSet per vertex.

• Finding all neighbors of vertex u: O(degree(u))

  • Just iterate over adj.get(u). This visits only actual neighbors, not all V vertices.

Space Complexity: O(V + E)

• V ArrayList objects (one per vertex) → O(V).
• For undirected graphs, each edge appears in two lists → 2E total entries → O(E).
• For directed graphs, each edge appears once → E entries → O(E).
• Total: O(V + E).

For sparse graphs (E << V²), this is dramatically more efficient. A graph with V = 10,000 and E = 20,000 uses ~50,000 list entries vs. 100,000,000 matrix cells.

Summary — When to Use Which: