Graph Representation & BFS

Introduction

So far, we have built up complexity step by step:

1. Arrays / Linked Lists: Data in a straight line.
2. Trees: Data expanding downwards hierarchically (Parents & Children).
3. Graphs: Complete freedom. Any piece of data can connect to any other piece of data.

Think of your social media network: you follow Alice, Alice follows Bob, and Bob follows you back. There is no clear “Root” or “Parent”. It is just a web of connections. A Graph is perfect for representing this social network, city roads, internet routers, or airline flight paths.

Anatomy of a Graph

A Graph consists of two things:

1. Vertices (Nodes): The actual entities (Cities, People, Routers).
2. Edges (Connections): The links between the vertices (Roads, Friendships, Cables).

Key Graph Terminology

• Undirected vs Directed: In the graph above, the edges are undirected (a two-way road). If they had arrows, they would be directed (a one-way road).
• Weighted vs Unweighted: If an edge has a numerical value (like distance or cost), it is weighted.
• Cyclic vs Acyclic: If you can start at node A, follow a path, and end up back at A (e.g. A $\rightarrow$ B $\rightarrow$ C $\rightarrow$ A), the graph has a cycle.

Representing a Graph in Java

How do we actually write code to represent the graph drawn above? There are two main ways: Adjacency Matrix and Adjacency List.

1. Adjacency Matrix

A 2D array where matrix[i][j] is 1 if there is an edge between vertex i and vertex j (or the weight of the edge), and 0 otherwise.

   A  B  C  D  E
A [0, 1, 1, 0, 0]
B [1, 0, 1, 1, 0]
C [1, 1, 0, 1, 1]
D [0, 1, 1, 0, 0]
E [0, 0, 1, 0, 0]

Pros: Instant $O(1)$ check if an edge exists. Extremely simple to code. Cons: Uses $O(V^2)$ memory. If a social network has a billion users, a $10^9 \times 10^9$ matrix will crash your computer instantly — even if most users only have 10 friends (a “sparse” graph).

2. Adjacency List (The Standard)

An array (or Map) of Lists. Each vertex simply holds a list of the vertices it is directly connected to.

A -> [B, C]
B -> [A, C, D]
C -> [A, B, D, E]
D -> [B, C]
E -> [C]

Pros: Uses $O(V + E)$ memory. Highly efficient for almost all real-world (sparse) graphs. Cons: Finding if A is connected to D specifically takes $O(k)$ time where $k$ is A’s friend count.

Java Adjacency List Boilerplate:

import java.util.*;

public class Graph {
    // Map of a node to a list of its neighbours
    Map<String, List<String>> adjList = new HashMap<>();

    public void addVertex(String label) {
        adjList.putIfAbsent(label, new ArrayList<>());
    }

    public void addEdge(String src, String dest) {
        // For an undirected graph, add connection to both sides
        adjList.get(src).add(dest);
        adjList.get(dest).add(src);
    }
}

Breadth-First Search (BFS)

Now that we have built a graph, how do we explore it? The most important traversal method is Breadth-First Search (BFS).

Imagine dropping a stone in a pond. The ripples expand outwards in rings. BFS explores a graph exactly like this:

1. Start at a source node (Distance 0).
2. Explore all immediate neighbours (Distance 1).
3. Explore all neighbours of those neighbours (Distance 2).
4. Continue until the whole graph is explored.

Because of this ripple effect, BFS is guaranteed to find the shortest path between two nodes in an unweighted graph!

The BFS Implementation

To implement BFS, we need two tools:

1. A Queue: To keep track of which nodes to visit next (First In, First Out enforces the ripple effect).
2. A visited Set: Unlike Trees, Graphs can have cycles. If A connects to B, and B connects to A, our code will loop forever unless we explicitly mark nodes as “visited”.

import java.util.*;

public void bfs(String startNode) {
    if (!adjList.containsKey(startNode)) return;

    Queue<String> queue = new LinkedList<>();
    Set<String> visited = new HashSet<>();

    // 1. Initialise the first node
    queue.offer(startNode);
    visited.add(startNode);

    // 2. Loop until the queue is empty
    while (!queue.isEmpty()) {
        String current = queue.poll();
        System.out.print(current + " "); // Process the node

        // 3. Look at all neighbours
        for (String neighbour : adjList.get(current)) {
            // Only add unvisited neighbours to the queue
            if (!visited.contains(neighbour)) {
                visited.add(neighbour); // Mark visited IMMEDIATELY when added to queue
                queue.offer(neighbour);
            }
        }
    }
}

Walkthrough of our Graph Starting at ‘A’

1. Queue: [A], Visited: {A}
2. Pop A. Neighbours: B, C. Neither visited. Add both. Queue: [B, C], Visited: {A, B, C}
3. Pop B. Neighbours: A, C, D. A & C are visited. Add D. Queue: [C, D], Visited: {A, B, C, D}
4. Pop C. Neighbours: A, B, D, E. Only E is unvisited. Add E. Queue: [D, E], Visited: {A, B, C, D, E}
5. Pop D. (No unvisited neighbours). Queue: [E]
6. Pop E. (No unvisited neighbours). Queue: []
7. Queue is empty. Finished!

BFS Output Order: A, B, C, D, E

BFS Complexity

When to Use BFS

Practice Problems

Graph problems often disguise themselves as matrices/grids. A 2D grid is just a graph where each cell is a vertex and connects to its 4 neighbours (up, down, left, right).

1. Number of Islands – LeetCode #200 — The definitive grid graph problem.
2. Shortest Path in Binary Matrix – LeetCode #1091 — An excellent practical application of BFS.
3. Rotting Oranges – LeetCode #994 — A multi-source BFS problem. Very popular in technical interviews!

What’s Next?

Breadth-First Search ripples out perfectly, but it uses a lot of memory. What if, instead of exploring broadly, we dive as deep into the graph as possible, hoping to hit our target, and only turn back when we hit a dead end?

This technique is called Depth-First Search (DFS) & Applications. We will cover it in the next post.