Graph Representation in Java: Two Ways to Represent

Storing a graph in memory requires translating a visual network of nodes and edges into programmatic data structures. This chapter explores how graphs are delivered via input formats and demonstrates the two primary techniques used in Java to store them: Adjacency Matrices and Adjacency Lists.

1. Why Do We Need Graph Representations?

Graphs are non-linear data structures consisting of vertices (nodes) and edges that connect them. Unlike arrays or trees, which have fixed traversal paths or strict hierarchical parent-child relationships, graphs can have cycles, multiple connections, and complex topologies.

• To run algorithms like Breadth-First Search (BFS) or Depth-First Search (DFS), computers need a deterministic way to look up a node's neighbors.
• The choice of storage dictates both the time complexity of graph operations and the space consumption in memory.

2. Understanding Graph Input Formats

Before storing a graph, you must understand how input data is typically fed into your program from competitive programming platforms or system files.

• Line 1 (N and M): The first line provides two integers:
  • N: The total number of nodes (vertices).
  • M: The total number of edges.
• Next M lines: Each subsequent line specifies a pair of nodes (u, v) representing an edge between them.

Input Example (5 Nodes, 6 Edges):
5 6
1 2
1 3
2 4
3 4
2 5
4 5

Note: The input order of edges can be completely arbitrary (e.g., 2 4 can appear before 1 2). For undirected graphs, an edge given as 1 2 implies travel is possible in both directions (1 -> 2 and 2 -> 1).

3. Core Mental Model: The Two Storage Strategies

When deciding how to house a graph in memory, developers choose between a grid-based approach or a collection-based approach.

4. Approach 1: Adjacency Matrix

An adjacency matrix is a 2D array of size (N + 1) x (N + 1). We use N + 1 (instead of N) to accommodate 1-based indexing, allowing node 5 to map directly to index 5 without index-shift mental overhead.

How It Works:

• If an edge exists between node u and node v, set matrix[u][v] = 1 and matrix[v][u] = 1 (for undirected graphs).
• If no edge exists, the cell contains 0.

Java Implementation (Adjacency Matrix)

import java.util.Scanner;

public class GraphMatrix {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        int n = scanner.nextInt(); // Number of nodes
        int m = scanner.nextInt(); // Number of edges
        
        // Declaring adjacency matrix of size (n + 1) x (n + 1)
        int[][] adjMatrix = new int[n + 1][n + 1];
        
        // Reading all edges
        for (int i = 0; i < m; i++) {
            int u = scanner.nextInt();
            int v = scanner.nextInt();
            
            // Mark connection for undirected graph
            adjMatrix[u][v] = 1;
            adjMatrix[v][u] = 1; 
        }
        
        scanner.close();
    }
}

Space Complexity Analysis:

• The matrix requires $O(N^2)$ space.
• For a graph with 10,000 nodes, a matrix requires $10^4 \times 10^4 = 10^8$ integer elements, which consumes significant memory even if only a fraction of those edges actually exist.

5. Approach 2: Adjacency List

To eliminate the memory waste of matrices, we use an Adjacency List. Instead of reserving slots for non-existent connections, we store only actual neighbors.

Data Structure Architecture in Java:

We define an ArrayList containing nested ArrayList elements:

ArrayList<ArrayList<Integer>> adjList = new ArrayList<>();

Step-by-Step Population Workflow:

1. Initialize an outer ArrayList.
2. Add N + 1 empty inner ArrayList instances to handle 1-based indexing.
3. For every edge (u, v), fetch the list at index u and add v; fetch the list at index v and add u.

Java Implementation (Adjacency List)

import java.util.ArrayList;
import java.util.Scanner;

public class GraphList {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        
        // Step 1: Initialize outer ArrayList
        ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
        
        // Step 2: Add (n + 1) empty inner ArrayLists for 1-based indexing
        for (int i = 0; i <= n; i++) {
            adj.add(new ArrayList<>());
        }
        
        // Step 3: Populate edges
        for (int i = 0; i < m; i++) {
            int u = scanner.nextInt();
            int v = scanner.nextInt();
            
            // For undirected graph, add v to u's list, and u to v's list
            adj.get(u).add(v);
            adj.get(v).add(u);
        }
        
        scanner.close();
    }
}

Space Complexity Analysis:

• Every edge (u, v) is stored twice in an undirected graph (once in node u's list, once in node v's list).
• Total storage equates to $O(2M)$, which simplifies to $O(M)$, making it vastly more efficient for sparse graphs.

6. Adjusting for Directed Graphs

In a directed graph, edges have a strict orientation. If an edge is given as 1 -> 2, you can travel from node 1 to node 2, but not from node 2 to node 1.

• Matrix Adjustment: Only set matrix[u][v] = 1. Do not touch matrix[v][u].
• List Adjustment: Only add v to u's list:
  JAVA

  Copy

  // Directed graph edge: u -> v
  adj.get(u).add(v);
  

7. Handling Weighted Graphs

Real-world networks (like road maps or computer networks) often assign costs, distances, or capacities to edges, known as edge weights (e.g., an edge between node 1 and 2 with a weight of 5).

Matrix Representation with Weights:

Instead of putting a binary 1 at matrix[u][v], store the actual weight value:

int weight = scanner.nextInt();
adjMatrix[u][v] = weight;
adjMatrix[v][u] = weight;

List Representation with Weights:

Because a standard ArrayList<Integer> can only store single values, we must modify our adjacency list to store pairs (neighbor node + edge weight) using a custom class or data structure.

// Conceptual structure: ArrayList containing lists of Pair objects
// Pair structure: { node: int, weight: int }

// For node 4, neighbors are stored as pairs:
// [ (2, weight_1), (3, weight_4), (5, weight_3) ]

8. Summary and Key Takeaways

• Input Parsing: Graphs are typically provided with dimensions N (nodes) and M (edges), followed by M lines representing edge connections.
• 1-Based Indexing: Allocating size N + 1 allows direct mapping of node numbers to array/list indices without offset calculations.
• Adjacency Matrix: Utilizes a 2D grid (N x N) offering $O(1)$ edge lookups, but incurs a heavy space cost of $O(N^2)$.
• Adjacency List: Utilizes an array/list of dynamic collections, scaling efficiently with space complexity $O(2M)$, making it the industry and interview standard.
• Directed Graphs: Require setting unidirectional connections (storing the edge only once from source to destination).
• Weighted Graphs: Extend basic storage by embedding weight values into matrices or storing pairs in adjacency lists.