How Graphs Are Stored and Traversed in Java (DFS & BFS Explained)

 

How Graphs Are Stored and Traversed in Java (DFS & BFS Explained)

Graphs are everywhere: social networks, maps, workflows, dependencies, and more.
In this post, we’ll see:

  • How to store a graph in Java

  • How to print the graph

  • How DFS (Depth-First Search) and BFS (Breadth-First Search) work

  • A simple implementation with main()

We’ll keep everything very simple and beginner-friendly.

1. The Example Graph

We’ll use this small undirected graph with 5 nodes: 0, 1, 2, 3, 4.

🔹 Visual graph (text-based)

    1
   / \
  0   2
  |
  3

  1
  |
  4

🔹 Edges

We have these connections (edges):

  • 0 — 1

  • 0 — 3

  • 1 — 2

  • 1 — 4

This is an undirected graph, so:

  • If 0 is connected to 1 → 1 is also connected to 0.

2. How We Store the Graph in Java

The most common way to store a graph is using an Adjacency List.

2.1 What is an adjacency list?

For each node, we store a list of its neighbors.

For our graph:

Node 0 → neighbors: 1, 3
Node 1 → neighbors: 0, 2, 4
Node 2 → neighbors: 1
Node 3 → neighbors: 0
Node 4 → neighbors: 1

2.2 Java data structure

We use:

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

  • graph is a list

  • Each element of graph is another list of integers

  • graph.get(i) gives the list of neighbors for node i

So:

graph.get(0) → [1, 3]
graph.get(1) → [0, 2, 4]
graph.get(2) → [1]
graph.get(3) → [0]
graph.get(4) → [1]

2.3 Step-by-step: building the adjacency list

Assume we have n = 5 nodes: 0..4.

Step 1: Create the outer list

int n = 5;
List<List<Integer>> graph = new ArrayList<>();

Now graph is empty:

graph: [ ]

Step 2: Create an empty neighbor list for each node

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

Now we have:

graph[0] = [ ]
graph[1] = [ ]
graph[2] = [ ]
graph[3] = [ ]
graph[4] = [ ]

Step 3: Add edges (undirected)

For undirected edge 0 — 1:

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

For 0 — 3:

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

For 1 — 2:

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

For 1 — 4:

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

Now the adjacency list looks like:

graph[0] = [1, 3]
graph[1] = [0, 2, 4]
graph[2] = [1]
graph[3] = [0]
graph[4] = [1]

3. Printing the Graph

We can print the adjacency list like this:

static void printGraph(List<List<Integer>> graph) {
    for (int i = 0; i < graph.size(); i++) {
        System.out.print("Node " + i + " -> ");
        System.out.println(graph.get(i));
    }
}

Output:

Node 0 -> [1, 3]
Node 1 -> [0, 2, 4]
Node 2 -> [1]
Node 3 -> [0]
Node 4 -> [1]

This gives a clear picture of how the graph is stored in memory.

4. DFS (Depth-First Search) – Step by Step

DFS means: go as deep as possible along one path before backtracking.

We will start DFS from node 0.

4.1 DFS idea in simple words

  1. Start at a node (e.g., 0)

  2. Visit it and mark as visited

  3. For each neighbor:

    • If not visited → go into that neighbor (recursively)

  4. When no unvisited neighbors → go back (backtrack)

4.2 Run DFS on our graph

Adjacency list reminder:

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

Start: DFS(0)

Let’s track:

  • visited[] = keeps track of nodes already seen

  • output = order of printing

Step-by-step DFS from 0

  1. Start at 0

    • Visit 0 → visited[0] = true

    • Output: 0

    • Neighbors: [1, 3]

  2. Go to neighbor 1 (first neighbor of 0)

    • Visit 1 → visited[1] = true

    • Output: 0 1

    • Neighbors of 1: [0, 2, 4]

    • 0 is already visited → skip

    • Next: 2

  3. Go to neighbor 2

    • Visit 2 → visited[2] = true

    • Output: 0 1 2

    • Neighbors of 2: [1] (already visited)

    • No more new neighbors → go back to 1

  4. Back at 1, next neighbor is 4

    • Visit 4 → visited[4] = true

    • Output: 0 1 2 4

    • Neighbors of 4: [1] (already visited)

    • No more new neighbors → go back to 1 → back to 0

  5. Back at 0, next neighbor is 3

    • Visit 3 → visited[3] = true

    • Output: 0 1 2 4 3

    • Neighbors of 3: [0] (already visited)

    • Done

Final DFS order starting from 0:

0 1 2 4 3

4.3 DFS Java code

static void dfs(int node, boolean[] visited, List<List<Integer>> graph) {
    visited[node] = true;                 // Mark current node as visited
    System.out.print(node + " ");         // Print the node

    // Go through all neighbors of this node
    for (int neighbor : graph.get(node)) {
        if (!visited[neighbor]) {         // If neighbor is not visited
            dfs(neighbor, visited, graph); // Recursively visit neighbor
        }
    }
}

5. BFS (Breadth-First Search) – Step by Step

BFS means: visit nodes level by level, like waves going outwards.

We use a queue.

5.1 BFS idea in simple words

  1. Start at a node and push it into a queue

  2. While queue is not empty:

    • Remove (poll) one node

    • Visit it

    • Add all its unvisited neighbors to the queue

5.2 Run BFS from node 0

Adjacency list again:

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

Let’s track:

  • visited[]

  • queue

  • output

Initial:

queue = [0]
visited[0] = true
output = (empty)

Step 1:

  • Take from queue → node = 0

  • Output: 0

  • Neighbors: [1, 3]

    • 1 not visited → mark visited, add to queue

    • 3 not visited → mark visited, add to queue

Now:

queue = [1, 3]
visited = [0,1,0,1,0]
output = 0

Step 2:

  • Take from queue → node = 1

  • Output: 0 1

  • Neighbors of 1: [0, 2, 4]

    • 0 already visited → skip

    • 2 not visited → mark visited, add to queue

    • 4 not visited → mark visited, add to queue

Now:

queue = [3, 2, 4]
visited = [1,1,1,1,1]
output = 0 1

Step 3:

  • Take from queue → node = 3

  • Output: 0 1 3

  • Neighbors of 3: [0] (already visited)

  • Queue: [2, 4]

Step 4:

  • Take from queue → node = 2

  • Output: 0 1 3 2

  • Neighbors of 2: [1] (already visited)

  • Queue: [4]

Step 5:

  • Take from queue → node = 4

  • Output: 0 1 3 2 4

  • Neighbors of 4: [1] (already visited)

  • Queue: [] → done

Final BFS order from 0:

0 1 3 2 4

5.3 BFS Java code

static void bfs(int start, List<List<Integer>> graph) {
    boolean[] visited = new boolean[graph.size()];
    Queue<Integer> q = new LinkedList<>();

    visited[start] = true;  // Mark starting node
    q.add(start);           // Add start node into queue

    while (!q.isEmpty()) {
        int node = q.poll();        // Take one node from queue
        System.out.print(node + " ");

        for (int neighbor : graph.get(node)) {
            if (!visited[neighbor]) {   // If neighbor not visited
                visited[neighbor] = true;
                q.add(neighbor);        // Add neighbor to queue
            }
        }
    }
}

6. Full Simple Java Program (With main)

You can copy-paste this file and run directly.

import java.util.*;

public class GraphDemo {

    // ---------- DFS: Depth-First Search ----------
    static void dfs(int node, boolean[] visited, List<List<Integer>> graph) {
        visited[node] = true;                 // Mark current node as visited
        System.out.print(node + " ");         // Print the node

        // Visit all neighbors
        for (int neighbor : graph.get(node)) {
            if (!visited[neighbor]) {         // Only go to unvisited nodes
                dfs(neighbor, visited, graph);
            }
        }
    }

    // ---------- BFS: Breadth-First Search ----------
    static void bfs(int start, List<List<Integer>> graph) {
        boolean[] visited = new boolean[graph.size()];
        Queue<Integer> q = new LinkedList<>();

        visited[start] = true;   // Start node is visited
        q.add(start);            // Put start node in queue

        while (!q.isEmpty()) {
            int node = q.poll(); // Take from front of queue
            System.out.print(node + " ");

            // Add all unvisited neighbors to queue
            for (int neighbor : graph.get(node)) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    q.add(neighbor);
                }
            }
        }
    }

    // ---------- Print Graph (Adjacency List) ----------
    static void printGraph(List<List<Integer>> graph) {
        System.out.println("Graph adjacency list:");
        for (int i = 0; i < graph.size(); i++) {
            System.out.println("Node " + i + " -> " + graph.get(i));
        }
    }

    public static void main(String[] args) {
        int n = 5;  // Number of nodes: 0,1,2,3,4

        // 1) Create empty graph
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }

        // 2) Add undirected edges: 0-1, 0-3, 1-2, 1-4
        addUndirectedEdge(graph, 0, 1);
        addUndirectedEdge(graph, 0, 3);
        addUndirectedEdge(graph, 1, 2);
        addUndirectedEdge(graph, 1, 4);

        // 3) Print graph
        printGraph(graph);

        // 4) Run DFS from node 0
        System.out.print("\nDFS from node 0: ");
        boolean[] visited = new boolean[n];
        dfs(0, visited, graph);

        // 5) Run BFS from node 0
        System.out.print("\nBFS from node 0: ");
        bfs(0, graph);
    }

    // Helper to add an undirected edge
    static void addUndirectedEdge(List<List<Integer>> graph, int u, int v) {
        graph.get(u).add(v);  // u -> v
        graph.get(v).add(u);  // v -> u
    }
}

Example output:

Graph adjacency list:
Node 0 -> [1, 3]
Node 1 -> [0, 2, 4]
Node 2 -> [1]
Node 3 -> [0]
Node 4 -> [1]

DFS from node 0: 0 1 2 4 3 
BFS from node 0: 0 1 3 2 4
-
Labels:

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)

How Graphs Are Stored and Traversed in Java (DFS & BFS Explained)

  How Graphs Are Stored and Traversed in Java (DFS & BFS Explained) Graphs are everywhere: social networks, maps, workflows, dependenci...

Featured Posts