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");

// io.thecodeforge — dsa tutorial

import java.util.*;

public class EdgeListBuild {
    static class Edge {
        int src, dest, weight;
        Edge(int s, int d, int w) { src = s; dest = d; weight = w; }
    }

    public static void main(String[] args) {
        // Build from CSV: nodeA,nodeB,weight
        String[] raw = {"2,5,3", "7,1,8", "3,9,2"};
        List edges = new ArrayList<>();
        
        for (String line : raw) {
            String[] parts = line.split(",");
            edges.add(new Edge(
                Integer.parseInt(parts[0]),
                Integer.parseInt(parts[1]),
                Integer.parseInt(parts[2])
            ));
        }

        // Iterate all edges — O(E) and no overhead
        int totalWeight = 0;
        for (Edge e : edges) totalWeight += e.weight;
        
        System.out.println("Edges parsed: " + edges.size());
        System.out.println("Total weight: " + totalWeight);
    }
}

// io.thecodeforge — dsa tutorial

import java.util.*;

public class CSRBuild {
    public static void main(String[] args) {
        // Raw edges: (src, dest)
        int[][] edges = {{0,2}, {1,2}, {1,3}, {2,3}, {4,0}};
        int V = 5, E = edges.length;

        // Determine degree of each vertex
        int[] degree = new int[V];
        for (int[] e : edges) degree[e[0]]++;

        // Build rowIndex from prefix sum of degrees
        int[] rowIndex = new int[V + 1];
        for (int i = 0; i < V; i++)
            rowIndex[i + 1] = rowIndex[i] + degree[i];

        // Fill columnIndex
        int[] columnIndex = new int[E];
        int[] cursor = Arrays.copyOf(rowIndex, V); // temp pointers
        for (int[] e : edges) {
            int src = e[0], dest = e[1];
            columnIndex[cursor[src]++] = dest;
        }

        // Query neighbors of vertex 1
        int start = rowIndex[1], end = rowIndex[2];
        System.out.print("Neighbors of 1: ");
        for (int i = start; i < end; i++)
            System.out.print(columnIndex[i] + " ");
        System.out.println();
        
        long memory = (V + 1 + E) * 4L; // ints = 4 bytes
        System.out.println("CSR memory: " + memory + " bytes");
    }
}

// io.thecodeforge — dsa tutorial

import java.util.*;

public class TopologicalSort {
    public static List<Integer> sort(int n, int[][] edges) {
        List<Integer>[] g = new ArrayList[n];
        int[] indeg = new int[n];
        for (int i = 0; i < n; i++) g[i] = new ArrayList<>();
        for (int[] e : edges) {
            g[e[0]].add(e[1]);
            indeg[e[1]]++;
        }
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < n; i++) if (indeg[i] == 0) q.add(i);
        List<Integer> order = new ArrayList<>();
        while (!q.isEmpty()) {
            int u = q.poll();
            order.add(u);
            for (int v : g[u]) if (--indeg[v] == 0) q.add(v);
        }
        return order.size() == n ? order : List.of(); // cycle
    }

    public static void main(String[] args) {
        int[][] edges = {{5,0},{4,0},{5,2},{2,3},{3,1},{4,1}};
        System.out.println(sort(6, edges));
    }
}

// io.thecodeforge — dsa tutorial

import java.util.*;

public class CycleDetection {
    static boolean hasCycle(int n, int[][] edges) {
        List<Integer>[] g = new ArrayList[n];
        for (int i = 0; i < n; i++) g[i] = new ArrayList<>();
        for (int[] e : edges) g[e[0]].add(e[1]);
        int[] state = new int[n]; // 0=unvisited,1=visiting,2=done
        for (int i = 0; i < n; i++) if (dfs(i, g, state)) return true;
        return false;
    }

    static boolean dfs(int u, List<Integer>[] g, int[] state) {
        if (state[u] == 1) return true;
        if (state[u] == 2) return false;
        state[u] = 1;
        for (int v : g[u]) if (dfs(v, g, state)) return true;
        state[u] = 2;
        return false;
    }

    public static void main(String[] args) {
        int[][] cyclic = {{0,1},{1,2},{2,0}};
        int[][] acyclic = {{0,1},{1,2}};
        System.out.println("Cyclic: " + hasCycle(3, cyclic));
        System.out.println("Acyclic: " + hasCycle(3, acyclic));
    }
}