Graph Representation

In the previous topic, we learned what a graph is: a collection of vertices connected by edges.

But there is an important question:

How do we actually store a graph inside a program?

Consider this graph:

        0
       / \
      1   2
      |   |
      3---4

We can see the graph visually, but Java needs a data structure to store it.

The three most common graph representations are:

1. Adjacency Matrix
2. Adjacency List
3. Edge List

The representation you choose can significantly affect the time and space complexity of your algorithm.

1. Adjacency Matrix

An Adjacency Matrix uses a 2D array to represent connections between vertices.

For this graph:

        0
       / \
      1   2
      |   |
      3---4

The vertices are:

0, 1, 2, 3, 4

We create a matrix:

      0 1 2 3 4
    +-----------
0   | 0 1 1 0 0
1   | 1 0 0 1 0
2   | 1 0 0 0 1
3   | 0 1 0 0 1
4   | 0 0 1 1 0

A 1 means:

There is an edge.

A 0 means:

There is no edge.

For example:

matrix[0][1] = 1

means:

0 ─ 1

And:

matrix[0][3] = 0

means there is no direct edge between 0 and 3.

Creating an Adjacency Matrix in Java

We can create a matrix for five vertices:

int vertices = 5;

int[][] graph =
    new int[vertices][vertices];

Initially:

0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

Now suppose we want to add an edge between 0 and 1.

For an undirected graph:

graph[0][1] = 1;
graph[1][0] = 1;

Similarly:

graph[0][2] = 1;
graph[2][0] = 1;

graph[1][3] = 1;
graph[3][1] = 1;

graph[2][4] = 1;
graph[4][2] = 1;

graph[3][4] = 1;
graph[4][3] = 1;

Why Are Both Positions Updated?

This is because we're using an undirected graph.

If:

0 ─ 1

then:

0 is connected to 1

and:

1 is connected to 0

Therefore:

graph[0][1] = 1
graph[1][0] = 1

The matrix is symmetrical.

Adjacency Matrix for a Directed Graph

Now consider:

0 → 1

This means we can travel from 0 to 1, but not necessarily from 1 to 0.

So:

graph[0][1] = 1;

We don't set:

graph[1][0] = 1;

The matrix might look like:

    0 1
0   0 1
1   0 0

This is an important distinction between directed and undirected graphs.

Weighted Adjacency Matrix

An adjacency matrix doesn't have to contain only 0 and 1.

For a weighted graph:

       5
   0 ----- 1
   |       |
  10       3
   |       |
   2 ----- 3
       7

we can store the edge weights:

     0   1   2   3
0    0   5  10   0
1    5   0   0   3
2   10   0   0   7
3    0   3   7   0

Here:

graph[0][1] = 5

means the edge from 0 to 1 has weight 5.

Advantages of Adjacency Matrix

The biggest advantage is that checking whether two vertices are directly connected is very fast.

For example:

if (graph[2][4] == 1) {
    System.out.println("Edge exists");
}

This takes:

O(1)

We directly access the matrix cell.

It's also simple to understand and implement.

Disadvantages of Adjacency Matrix

The biggest problem is memory usage.

If there are V vertices, we need:

V × V

cells.

Therefore:

Space = O(V²)

This can become expensive for a graph with many vertices but relatively few edges.

For example, suppose we have:

10,000 vertices

The matrix needs:

10,000 × 10,000

cells.

That's:

100,000,000

entries.

Even if only a small number of edges actually exist, the matrix still allocates space for every possible pair.

2. Adjacency List

The second and most commonly used representation is the Adjacency List.

Instead of storing every possible connection, we store only the vertices that are actually connected.

For:

        0
       / \
      1   2
      |   |
      3---4

we can represent it as:

0 → 1, 2
1 → 0, 3
2 → 0, 4
3 → 1, 4
4 → 2, 3

Each vertex stores a list of its neighbors.

Adjacency List in Java

A common implementation uses:

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

Suppose we have:

5 vertices

We create five lists:

int vertices = 5;

for (int i = 0; i < vertices; i++) {
    graph.add(new ArrayList<>());
}

Initially:

0 → []
1 → []
2 → []
3 → []
4 → []

Adding an Undirected Edge

Let's add:

0 ─ 1

Because it's undirected:

graph.get(0).add(1);
graph.get(1).add(0);

Now:

0 → [1]
1 → [0]
2 → []
3 → []
4 → []

Add:

0 ─ 2

graph.get(0).add(2);
graph.get(2).add(0);

Now:

0 → [1, 2]
1 → [0]
2 → [0]
3 → []
4 → []

A Better addEdge() Method

Instead of repeatedly writing the same code, we can create a method:

static void addEdge(
    ArrayList<ArrayList<Integer>> graph,
    int u,
    int v
) {

    graph.get(u).add(v);
    graph.get(v).add(u);
}

Now we can simply write:

addEdge(graph, 0, 1);
addEdge(graph, 0, 2);
addEdge(graph, 1, 3);
addEdge(graph, 2, 4);
addEdge(graph, 3, 4);

This creates:

0 → [1, 2]
1 → [0, 3]
2 → [0, 4]
3 → [1, 4]
4 → [2, 3]

Adjacency List for a Directed Graph

For a directed graph:

0 → 1
0 → 2
2 → 3

we only add the outgoing connection:

graph.get(0).add(1);
graph.get(0).add(2);
graph.get(2).add(3);

The representation becomes:

0 → [1, 2]
1 → []
2 → [3]
3 → []

We don't add the reverse edges.

Weighted Adjacency List

What if edges have weights?

Consider:

       5
   0 ----- 1
   |       |
  10       3
   |       |
   2 ----- 3
       7

Now each neighbor needs two pieces of information:

Neighbor
Weight

We can create a class:

class Edge {

    int destination;
    int weight;

    Edge(int destination, int weight) {
        this.destination = destination;
        this.weight = weight;
    }
}

Then:

ArrayList<ArrayList<Edge>> graph =
    new ArrayList<>();

We can add:

graph.get(0).add(
    new Edge(1, 5)
);

This represents:

0 --5--> 1

For an undirected weighted graph, we'd add both directions:

graph.get(0).add(
    new Edge(1, 5)
);

graph.get(1).add(
    new Edge(0, 5)
);

Using Java Records for Edges

If you're using a modern Java version, a record can make a simple edge representation shorter:

record Edge(int destination, int weight) {}

Then:

ArrayList<ArrayList<Edge>> graph =
    new ArrayList<>();

And:

graph.get(0).add(
    new Edge(1, 5)
);

The concept remains exactly the same.

3. Edge List

The third representation is the Edge List.

Instead of storing neighbors for every vertex, we simply store all edges.

For:

0 ─ 1
|   |
2 ─ 3

we could store:

(0, 1)
(0, 2)
(1, 3)
(2, 3)

For weighted edges:

(0, 1, 5)
(0, 2, 10)
(1, 3, 3)
(2, 3, 7)

Each entry represents:

Source
Destination
Weight

Edge List in Java

We can create an Edge class:

class Edge {

    int source;
    int destination;
    int weight;

    Edge(
        int source,
        int destination,
        int weight
    ) {
        this.source = source;
        this.destination = destination;
        this.weight = weight;
    }
}

Then:

ArrayList<Edge> edges =
    new ArrayList<>();

Add edges:

edges.add(
    new Edge(0, 1, 5)
);

edges.add(
    new Edge(0, 2, 10)
);

edges.add(
    new Edge(1, 3, 3)
);

Now the graph is represented as a collection of edges.

Why Use an Edge List?

An edge list is particularly convenient when the algorithm needs to process every edge directly.

For example, Kruskal's Algorithm works by sorting edges based on their weights.

Suppose:

(0, 1, 5)
(0, 2, 10)
(1, 3, 3)
(2, 3, 7)

We can sort them:

(1, 3, 3)
(0, 1, 5)
(2, 3, 7)
(0, 2, 10)

This makes the edge list a natural representation for that algorithm.

Comparing the Three Representations

Suppose:

V = Number of vertices
E = Number of edges

The three representations have different characteristics.

The exact implementation can affect constants, but these are the standard complexity bounds.

Which Representation Should You Use?

This is one of the most important practical questions.

Use Adjacency Matrix When:

The graph is dense.

That means there are many edges compared with the maximum possible number of edges.

It's also useful when you frequently need to ask:

Is there an edge between A and B?

because that can be answered in:

O(1)

Use Adjacency List When:

The graph is sparse.

For example:

100,000 vertices
200,000 edges

There are many vertices but relatively few connections.

An adjacency matrix would require:

100,000²

entries.

An adjacency list stores approximately:

V + E

information instead.

That's why adjacency lists are extremely common in coding interviews and competitive programming.

Use Edge List When:

The algorithm primarily works with edges.

For example:

Kruskal's Algorithm

needs to sort and process edges, making an edge list very convenient.

Adjacency Matrix vs Adjacency List

Let's use:

        0
       / \
      1   2
      |   |
      3---4

Matrix

     0 1 2 3 4
0    0 1 1 0 0
1    1 0 0 1 0
2    1 0 0 0 1
3    0 1 0 0 1
4    0 0 1 1 0

List

0 → 1, 2
1 → 0, 3
2 → 0, 4
3 → 1, 4
4 → 2, 3

The matrix stores every possible pair.

The list stores only actual connections.

Graph Representation and BFS

Adjacency lists work particularly well with BFS.

Suppose:

0 → 1, 2
1 → 3
2 → 4

BFS can simply retrieve the neighbors:

for (int neighbor : graph.get(node)) {

    if (!visited[neighbor]) {

        visited[neighbor] = true;
        queue.add(neighbor);
    }
}

The algorithm doesn't need to scan all possible vertices.

It only looks at actual neighbors.

That's why BFS with an adjacency list runs in:

O(V + E)

Graph Representation and DFS

DFS works in exactly the same way.

for (int neighbor : graph.get(node)) {

    if (!visited[neighbor]) {
        dfs(neighbor, graph, visited);
    }
}

Again, the adjacency list gives us the nodes directly connected to the current node.

Therefore:

DFS + Adjacency List
        ↓
O(V + E)

Complete Java Example

Let's create an undirected graph using an adjacency list:

import java.util.ArrayList;

class Main {

    static void addEdge(
        ArrayList<ArrayList<Integer>> graph,
        int u,
        int v
    ) {

        graph.get(u).add(v);
        graph.get(v).add(u);
    }

    public static void main(String[] args) {

        int vertices = 5;

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

        for (int i = 0; i < vertices; i++) {
            graph.add(new ArrayList<>());
        }

        addEdge(graph, 0, 1);
        addEdge(graph, 0, 2);
        addEdge(graph, 1, 3);
        addEdge(graph, 2, 4);
        addEdge(graph, 3, 4);

        for (int i = 0; i < vertices; i++) {

            System.out.print(i + " → ");

            for (int neighbor : graph.get(i)) {
                System.out.print(
                    neighbor + " "
                );
            }

            System.out.println();
        }
    }
}

Output:

0 → 1 2
1 → 0 3
2 → 0 4
3 → 1 4
4 → 2 3

This is a standard adjacency-list representation.

A Practical Interview Question

Suppose you're given:

V = 6
E = 4

and the graph looks like:

0 ─ 1

2 ─ 3

4 ─ 5

There are only four edges.

Using an adjacency matrix means allocating:

6 × 6 = 36

cells.

An adjacency list stores roughly:

V + E

information.

For a sparse graph, the adjacency list is therefore much more practical.

A Useful Mental Model

Think about the three representations like this:

Adjacency Matrix

Think:

"Is A connected to B?"

You go directly to:

matrix[A][B]

Adjacency List

Think:

"Who is A connected to?"

You look at:

graph[A]

Edge List

Think:

"What are all the edges?"

You iterate through:

edges

This mental model makes it much easier to decide which representation to use.

The Main Idea

A graph can be represented in several ways, but the three most important are:

1. Adjacency Matrix
2. Adjacency List
3. Edge List

Adjacency Matrix

Space → O(V²)
Edge lookup → O(1)

Best when the graph is dense or constant-time edge existence checks are important.

Adjacency List

Space → O(V + E)

Best for most sparse graph problems and commonly used with BFS and DFS.

Edge List

Space → O(E)

Best when algorithms primarily process or sort edges.

The most important comparison to remember is:

Adjacency Matrix
        ↓
Every possible connection

Adjacency List
        ↓
Only actual connections

Edge List
        ↓
Every edge as a separate entry

Choosing the right graph representation is important because it directly affects the memory usage and efficiency of graph algorithms such as BFS, DFS, Dijkstra, Prim, and Kruskal.