45-Minute BFS: Adjacency List vs Matrix Memory Mistake

public class AdjacencyMatrix {

    private final int[][] matrix;   // The actual grid storing edge data
    private final int nodeCount;    // Total number of nodes in the graph

    public AdjacencyMatrix(int nodeCount) {
        this.nodeCount = nodeCount;
        // Allocate a nodeCount x nodeCount grid, all initialised to 0 (no edges)
        this.matrix = new int[nodeCount][nodeCount];
    }

    // Add an undirected edge between two nodes (both directions matter)
    public void addEdge(int fromNode, int toNode) {\n        // Validate to avoid silent index-out-of-bounds bugs in production\n        if (fromNode < 0 || toNode < 0 || fromNode >= nodeCount || toNode >= nodeCount) {\n            throw new IllegalArgumentException(\n                \"Node index out of range: \" + fromNode + \", \" + toNode\n            );\n        }\n        matrix[fromNode][toNode] = 1;  // Mark edge in one direction\n        matrix[toNode][fromNode] = 1;  // Mark edge in the other (undirected)\n    }\n\n    // O(1) check — this is the matrix's superpower\n    public boolean hasEdge(int fromNode, int toNode) {\n        return matrix[fromNode][toNode] == 1;\n    }\n\n    // Print the full grid so we can visualise the structure\n    public void printMatrix() {\n        System.out.print(\"    \");\n        for (int col = 0; col < nodeCount; col++) {\n            System.out.printf(\"%3d\", col);  // Column headers\n        }\n        System.out.println();\n\n        for (int row = 0; row < nodeCount; row++) {\n            System.out.printf(\"%3d |\", row);  // Row header\n            for (int col = 0; col < nodeCount; col++) {\n                System.out.printf(\"%3d\", matrix[row][col]);\n            }\n            System.out.println();\n        }\n    }\n\n    public static void main(String[] args) {\n        // Modelling a small city road network with 5 intersections (nodes 0-4)\n        AdjacencyMatrix cityRoads = new AdjacencyMatrix(5);\n\n        cityRoads.addEdge(0, 1);  // Road between intersection 0 and 1\n        cityRoads.addEdge(0, 4);  // Road between intersection 0 and 4\n        cityRoads.addEdge(1, 2);  // Road between intersection 1 and 2\n        cityRoads.addEdge(1, 3);  // Road between intersection 1 and 3\n        cityRoads.addEdge(3, 4);  // Road between intersection 3 and 4\n\n        cityRoads.printMatrix();\n\n        System.out.println();\n        // O(1) lookup — is there a direct road from 0 to 3?\n        System.out.println(\"Direct road from 0 to 3? \" + cityRoads.hasEdge(0, 3));\n        System.out.println(\"Direct road from 1 to 3? \" + cityRoads.hasEdge(1, 3));\n    }\n}",
        "output": "      0  1  2  3  4\n  0 |  0  1  0  0  1\n  1 |  1  0  1  1  0\n  2 |  0  1  0  0  0\n  3 |  0  1  0  0  1\n  4 |  1  0  0  1  0\n\nDirect road from 0 to 3? false\nDirect road from 1 to 3? true"
      }

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class AdjacencyList {

    // Each node maps to a list of its direct neighbours
    // Using a Map allows nodes to have any label (String, Integer, etc.)
    private final Map<Integer, List<Integer>> adjacencyList;

    public AdjacencyList() {
        this.adjacencyList = new HashMap<>();
    }

    // Register a node so it exists in the graph even with no edges
    public void addNode(int node) {
        adjacencyList.putIfAbsent(node, new ArrayList<>());
    }

    // Add an undirected edge — each side adds the other to its neighbour list
    public void addEdge(int fromNode, int toNode) {\n        addNode(fromNode);  // Ensure both nodes exist before adding edges\n        addNode(toNode);\n\n        adjacencyList.get(fromNode).add(toNode);  // fromNode now knows about toNode\n        adjacencyList.get(toNode).add(fromNode);  // toNode now knows about fromNode\n    }

    // O(degree) check — scan the neighbour list of fromNode
    public boolean hasEdge(int fromNode, int toNode) {\n        List<Integer> neighbours = adjacencyList.getOrDefault(fromNode, new ArrayList<>());\n        return neighbours.contains(toNode);\n    }

    // Get all direct neighbours — this is the operation BFS/DFS uses constantly
    public List<Integer> getNeighbours(int node) {
        return adjacencyList.getOrDefault(node, new ArrayList<>());
    }

    // Print each node alongside its neighbour list
    public void printList() {
        for (Map.Entry<Integer, List<Integer>> entry : adjacencyList.entrySet()) {
            System.out.println("Node " + entry.getKey() + " --> " + entry.getValue());
        }
    }

    public static void main(String[] args) {
        // Modelling a simplified version of a flight route network
        AdjacencyList flightRoutes = new AdjacencyList();

        flightRoutes.addEdge(0, 1);  // London -- Paris
        flightRoutes.addEdge(0, 4);  // London -- Dubai
        flightRoutes.addEdge(1, 2);  // Paris -- New York
        flightRoutes.addEdge(1, 3);  // Paris -- Tokyo
        flightRoutes.addEdge(3, 4);  // Tokyo -- Dubai

        System.out.println("=== Flight Route Adjacency List ===");
        flightRoutes.printList();

        System.out.println();
        System.out.println("Neighbours of node 1 (Paris): " + flightRoutes.getNeighbours(1));
        System.out.println("Direct flight from 0 to 3? " + flightRoutes.hasEdge(0, 3));
        System.out.println("Direct flight from 1 to 4? " + flightRoutes.hasEdge(1, 4));
    }
}

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class DirectedWeightedGraph {

    // Inner class representing a directed edge with a weight (travel cost)
    static class Edge {
        int destination;  // Where this edge points TO
        int weight;       // The cost to traverse this edge (e.g. distance in km)

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

        @Override
        public String toString() {
            return "->" + destination + "(cost:" + weight + ")";
        }
    }

    // Each node has a list of outgoing weighted edges
    private final Map<Integer, List<Edge>> graph;

    public DirectedWeightedGraph() {
        this.graph = new HashMap<>();
    }

    public void addNode(int node) {
        graph.putIfAbsent(node, new ArrayList<>());
    }

    // Directed: ONLY adds toNode to fromNode's list, not the reverse
    public void addDirectedEdge(int fromNode, int toNode, int weight) {
        addNode(fromNode);
        addNode(toNode);
        graph.get(fromNode).add(new Edge(toNode, weight));
        // Notice: we do NOT add fromNode to toNode's list here
    }

    public List<Edge> getOutgoingEdges(int node) {
        return graph.getOrDefault(node, new ArrayList<>());
    }

    public void printGraph() {
        for (Map.Entry<Integer, List<Edge>> entry : graph.entrySet()) {
            System.out.print("Node " + entry.getKey() + " : ");
            for (Edge edge : entry.getValue()) {
                System.out.print(edge + "  ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        // Modelling a package delivery network where roads are one-directional
        // and weight represents delivery time in minutes
        DirectedWeightedGraph deliveryNetwork = new DirectedWeightedGraph();

        deliveryNetwork.addDirectedEdge(0, 1, 10);  // Warehouse -> Depot A (10 mins)
        deliveryNetwork.addDirectedEdge(0, 2, 30);  // Warehouse -> Depot B (30 mins)
        deliveryNetwork.addDirectedEdge(1, 3, 15);  // Depot A   -> Customer X (15 mins)
        deliveryNetwork.addDirectedEdge(2, 3, 5);   // Depot B   -> Customer X (5 mins)
        deliveryNetwork.addDirectedEdge(1, 2, 8);   // Depot A   -> Depot B (8 mins)

        System.out.println("=== Delivery Network (Directed + Weighted) ===");
        deliveryNetwork.printGraph();

        System.out.println();
        System.out.println("Routes out of Depot A (node 1): "
            + deliveryNetwork.getOutgoingEdges(1));

        // Customer X (node 3) has no outgoing edges — it's a terminal node
        System.out.println("Routes out of Customer X (node 3): "
            + deliveryNetwork.getOutgoingEdges(3));
    }
}

// Snippet: Time to find all neighbors of every node
// Matrix approach
long start = System.nanoTime();
for (int i = 0; i < V; i++) {
    List<Integer> neighbors = new ArrayList<>();
    for (int j = 0; j < V; j++) {
        if (matrix[i][j] != 0) neighbors.add(j);
    }
}
long matrixTime = System.nanoTime() - start;

// List approach
start = System.nanoTime();
for (int i = 0; i < V; i++) {
    List<Integer> neighbors = adjList.get(i);  // O(1)
}
long listTime = System.nanoTime() - start;

System.out.println("Matrix neighbor collection: " + matrixTime + " ns");
System.out.println("List neighbor collection: " + listTime + " ns");