Graph Representation Explained: Adjacency List vs Matrix (With Code)

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) {
        // Validate to avoid silent index-out-of-bounds bugs in production
        if (fromNode < 0 || toNode < 0 || fromNode >= nodeCount || toNode >= nodeCount) {
            throw new IllegalArgumentException(
                "Node index out of range: " + fromNode + ", " + toNode
            );
        }
        matrix[fromNode][toNode] = 1;  // Mark edge in one direction
        matrix[toNode][fromNode] = 1;  // Mark edge in the other (undirected)
    }

    // O(1) check — this is the matrix's superpower
    public boolean hasEdge(int fromNode, int toNode) {
        return matrix[fromNode][toNode] == 1;
    }

    // Print the full grid so we can visualise the structure
    public void printMatrix() {
        System.out.print("    ");
        for (int col = 0; col < nodeCount; col++) {
            System.out.printf("%3d", col);  // Column headers
        }
        System.out.println();

        for (int row = 0; row < nodeCount; row++) {
            System.out.printf("%3d |", row);  // Row header
            for (int col = 0; col < nodeCount; col++) {
                System.out.printf("%3d", matrix[row][col]);
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        // Modelling a small city road network with 5 intersections (nodes 0-4)
        AdjacencyMatrix cityRoads = new AdjacencyMatrix(5);

        cityRoads.addEdge(0, 1);  // Road between intersection 0 and 1
        cityRoads.addEdge(0, 4);  // Road between intersection 0 and 4
        cityRoads.addEdge(1, 2);  // Road between intersection 1 and 2
        cityRoads.addEdge(1, 3);  // Road between intersection 1 and 3
        cityRoads.addEdge(3, 4);  // Road between intersection 3 and 4

        cityRoads.printMatrix();

        System.out.println();
        // O(1) lookup — is there a direct road from 0 to 3?
        System.out.println("Direct road from 0 to 3? " + cityRoads.hasEdge(0, 3));
        System.out.println("Direct road from 1 to 3? " + cityRoads.hasEdge(1, 3));
    }
}

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) {
        addNode(fromNode);  // Ensure both nodes exist before adding edges
        addNode(toNode);

        adjacencyList.get(fromNode).add(toNode);  // fromNode now knows about toNode
        adjacencyList.get(toNode).add(fromNode);  // toNode now knows about fromNode
    }

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

    // 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) {
            this.destination = destination;
            this.weight = weight;
        }

        @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));
    }
}