Skip to content

03.GraphInJava.md

Latest commit

 

History

History
450 lines (324 loc) · 14.7 KB

03.GraphInJava.md

File metadata and controls

450 lines (324 loc) · 14.7 KB

Graph Representation in Java - Adjacency Matrix, Adjacency List & Weighted Graphs 🧠📘

1. Quick problem statement & why representations matter

Problem statement (short): Given nodes and edges, choose a data structure to store the graph so algorithms (BFS, DFS, Dijkstra, MST, etc.) can run efficiently. Different representations change runtime, memory usage, and simplicity of implementation.

Why it matters:

  • Some algorithms iterate neighbors fast - adjacency list is great.
  • Some require O(1) edge-existence checks - adjacency matrix helps.
  • Weighted graphs need to store weights per edge. Picking the right representation is one of the easiest levers to speed your graph code.

2. Overview of common representations 🌉

  1. Adjacency Matrix - 2D matrix mat[u][v] indicates edge (or weight).
  2. Adjacency List - List<List<Integer>> adj where adj.get(u) holds neighbors.
  3. Edge List - List<Edge> with (u, v) or (u, v, w) - useful for Kruskal and offline processing.

Short rule-of-thumb:

  • Use adj list for sparse graphs (E ≈ V or E ≪ V²).
  • Use adj matrix for dense graphs (E ≈ V²) or when you need O(1) edge queries.
  • Use edge list when sorting edges or offline algorithms.

3. Adjacency Matrix - explanation, pros/cons, code 🧾

What it is

An n × n 2D array where mat[u][v] is either true/false for unweighted graphs, or weight (or INF) for weighted graphs.

Use-cases

  • Dense graphs (many edges).
  • When you need O(1) hasEdge(u, v) checks.
  • Simple implementations (education / small problems).

Memory & Complexity

  • Memory: O(n²).
  • Iterate all neighbors of u: O(n) (even if only a few neighbors - costly).
  • Edge existence: O(1).
  • Good when n ≤ ~2–4k depending on memory/time constraints.

Java examples

Unweighted, boolean matrix

boolean[][] mat = new boolean[n][n];
mat[u][v] = true; // directed u -> v
mat[v][u] = true; // undirected
boolean exists = mat[a][b];

Weighted (use large sentinel for no-edge)

static final long INF = Long.MAX_VALUE / 4; // keep margin for addition
long[][] mat = new long[n][n];
for (int i = 0; i < n; i++) {
    Arrays.fill(mat[i], INF);
    mat[i][i] = 0;
}
mat[u][v] = weight; // if edge u->v exists

Pitfalls

  • Memory blow-up for large n.
  • Iterating neighbors requires scanning all n columns - expensive if graph is sparse.

4. Adjacency List - explanation, pros/cons, code 🌿

What it is

A List (size n) where each entry stores the neighbors of that vertex. For weighted graphs the neighbor is usually an object like AdjNode{to, weight}.

Use-cases

  • Most practical algorithms on sparse graphs.
  • When iterating actual neighbors needs to be fast (O(deg(u))).
  • Memory-efficient for sparse graphs.

Memory & Complexity

  • Memory: O(n + m) (n vertices + m edges).
  • Iterate neighbors of u: O(deg(u)).
  • Adding an edge: amortized O(1).

Java examples

Unweighted

List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
adj.get(u).add(v); // directed
adj.get(v).add(u); // undirected

Weighted

static class AdjNode {
    int to;
    long weight;
    AdjNode(int to, long weight) { this.to = to; this.weight = weight; }
}

List<List<AdjNode>> adjW = new ArrayList<>();
for (int i = 0; i < n; i++) adjW.add(new ArrayList<>());
adjW.get(u).add(new AdjNode(v, w));
adjW.get(v).add(new AdjNode(u, w)); // if undirected

Pitfalls

  • hasEdge(u, v) is O(deg(u)) - slower than matrix if many checks are needed.
  • When using ArrayList, reallocation cost exists - use ensureCapacity() when you know degrees approximately.

5. Edge List - short note 🔗

Structure: List<Edge> or List<EdgeWeighted> for weights. Use-case: Kruskal’s MST, offline processing, simple storage, sorting edges by weight. Complexity: O(m) memory. No fast neighbor iteration (you scan all edges).

6. Weighted graphs - how to store & access weights 🪙

  • Adjacency-list weighted: List<List<AdjNode>> - best for Dijkstra/Prim/graph algorithms.
  • Adjacency-matrix weighted: store weight or INF in mat[u][v].
  • Edge list weighted: List<Edge> - used in Bellman-Ford and Kruskal.

Important detail: For integer weights consider using long if sums/weights may exceed int. Use INF = Long.MAX_VALUE / 4 to avoid overflow when adding.

7. Typical operations & cost table 📊

Operation Adjacency List Adjacency Matrix Edge List
Memory O(n + m) O(n²) O(m)
Iterate neighbors of u O(deg(u)) O(n) O(m)
Check hasEdge(u,v) O(deg(u)) O(1) O(m)
Add edge O(1) O(1) O(1)
Remove edge O(deg(u)) O(1) O(m)

Bold = fastest for that operation.

8. Conversion helpers (matrix ⇄ list) - code snippets 🔁

Matrix → List (unweighted)

static List<List<Integer>> matToList(boolean[][] mat) {
    int n = mat.length;
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    for (int u = 0; u < n; u++) {
        for (int v = 0; v < n; v++) {
            if (mat[u][v]) adj.get(u).add(v);
        }
    }
    return adj;
}

List → Matrix (unweighted)

static boolean[][] listToMat(List<List<Integer>> adj) {
    int n = adj.size();
    boolean[][] mat = new boolean[n][n];
    for (int u = 0; u < n; u++) {
        for (int v : adj.get(u)) mat[u][v] = true;
    }
    return mat;
}

For weighted conversions use long[][] and INF appropriately.

9. Test cases - verify correctness ✅

A. Small undirected unweighted

  • n = 4, edges: (0,1), (1,2), (2,3)
  • Adj list: adj.get(1) should contain [0,2]
  • Adj matrix: mat[0][1] == true, mat[3][0] == false

B. Weighted undirected

  • n = 3, edges: (0,1,5), (1,2,2)
  • Dijkstra from 0: dist[2] = 7

C. Dense graph edge check

  • n = 1000, random dense edges - hasEdge(u,v) queries should be O(1) using matrix (but memory is heavy).

D. Kruskal edge list

  • edges: (0,1,1), (1,2,2), (0,2,3) → sorted by weight → ensure MST picks 1 and 2 weights.

10. Full single-file Java reference (demonstration) 🧩

// GraphRepresentations.java
import java.util.*;
import java.io.*;

public class GraphRepresentations {
    static final long INF = Long.MAX_VALUE / 4;

    // - Adjacency Matrix (unweighted) -
    static boolean[][] makeAdjMatrixUnweighted(int n) {
        return new boolean[n][n];
    }
    static void addEdgeMatUnweighted(boolean[][] mat, int u, int v, boolean undirected) {
        mat[u][v] = true;
        if (undirected) mat[v][u] = true;
    }

    // - Adjacency Matrix (weighted) -
    static long[][] makeAdjMatrixWeighted(int n) {
        long[][] mat = new long[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(mat[i], INF);
            mat[i][i] = 0;
        }
        return mat;
    }
    static void addEdgeMatWeighted(long[][] mat, int u, int v, long w, boolean undirected) {
        mat[u][v] = w;
        if (undirected) mat[v][u] = w;
    }

    // - Adjacency List (unweighted) -
    static List<List<Integer>> makeAdjListUnweighted(int n) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        return adj;
    }
    static void addEdgeListUnweighted(List<List<Integer>> adj, int u, int v, boolean undirected) {
        adj.get(u).add(v);
        if (undirected) adj.get(v).add(u);
    }

    // - Adjacency List (weighted) -
    static class AdjNode {
        int to;
        long weight;
        AdjNode(int to, long weight) { this.to = to; this.weight = weight; }
    }
    static List<List<AdjNode>> makeAdjListWeighted(int n) {
        List<List<AdjNode>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        return adj;
    }
    static void addEdgeListWeighted(List<List<AdjNode>> adj, int u, int v, long w, boolean undirected) {
        adj.get(u).add(new AdjNode(v, w));
        if (undirected) adj.get(v).add(new AdjNode(u, w));
    }

    // - Edge List (weighted) -
    static class Edge {
        int u, v;
        long w;
        Edge(int u, int v, long w) { this.u = u; this.v = v; this.w = w; }
    }
    static List<Edge> makeEdgeList() { return new ArrayList<>(); }
    static void addEdgeEdgeList(List<Edge> edges, int u, int v, long w) {
        edges.add(new Edge(u, v, w));
    }

    // - Conversions -
    static List<List<Integer>> matToList(boolean[][] mat) {
        int n = mat.length;
        List<List<Integer>> adj = makeAdjListUnweighted(n);
        for (int u = 0; u < n; u++) {
            for (int v = 0; v < n; v++) {
                if (mat[u][v]) adj.get(u).add(v);
            }
        }
        return adj;
    }

    static boolean[][] listToMat(List<List<Integer>> adj) {
        int n = adj.size();
        boolean[][] mat = new boolean[n][n];
        for (int u = 0; u < n; u++) {
            for (int v : adj.get(u)) mat[u][v] = true;
        }
        return mat;
    }

    // - Dijkstra using adjacency list (weighted) -
    static long[] dijkstraList(int src, List<List<AdjNode>> adj) {
        int n = adj.size();
        long[] dist = new long[n];
        Arrays.fill(dist, INF);
        dist[src] = 0;

        PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[0]));
        pq.offer(new long[]{0, src}); // {dist, node}

        while (!pq.isEmpty()) {
            long[] cur = pq.poll();
            long d = cur[0];
            int u = (int) cur[1];
            if (d != dist[u]) continue;
            for (AdjNode edge : adj.get(u)) {
                int v = edge.to;
                long w = edge.weight;
                if (dist[v] > d + w) {
                    dist[v] = d + w;
                    pq.offer(new long[]{dist[v], v});
                }
            }
        }
        return dist;
    }

    // - Simple demos -
    static void demoMatrixVsList() {
        int n = 4;
        boolean[][] mat = makeAdjMatrixUnweighted(n);
        addEdgeMatUnweighted(mat, 0, 1, true);
        addEdgeMatUnweighted(mat, 1, 2, true);

        List<List<Integer>> adj = makeAdjListUnweighted(n);
        addEdgeListUnweighted(adj, 0, 1, true);
        addEdgeListUnweighted(adj, 1, 2, true);

        System.out.print("Matrix neighbors of 1: ");
        for (int v = 0; v < n; v++) if (mat[1][v]) System.out.print(v + " ");
        System.out.println();

        System.out.print("List neighbors of 1: ");
        for (int v : adj.get(1)) System.out.print(v + " ");
        System.out.println();
    }

    static void demoWeightedStructures() {
        int n = 3;
        long[][] matW = makeAdjMatrixWeighted(n);
        addEdgeMatWeighted(matW, 0, 1, 5, true);
        addEdgeMatWeighted(matW, 1, 2, 2, true);

        List<List<AdjNode>> adjW = makeAdjListWeighted(n);
        addEdgeListWeighted(adjW, 0, 1, 5, true);
        addEdgeListWeighted(adjW, 1, 2, 2, true);

        System.out.println("Matrix weight 0->1: " + (matW[0][1] == INF ? -1 : matW[0][1]));
        System.out.print("List weight 0->1: ");
        for (AdjNode node : adjW.get(0)) if (node.to == 1) System.out.println(node.weight);
    }

    public static void main(String[] args) {
        System.out.println("=== Graph representation demos ===\n");
        demoMatrixVsList();
        System.out.println();
        demoWeightedStructures();
        System.out.println();

        // Dijkstra test using adjacency list (weighted)
        List<List<AdjNode>> adj = makeAdjListWeighted(3);
        addEdgeListWeighted(adj, 0, 1, 5, true);
        addEdgeListWeighted(adj, 1, 2, 2, true);
        long[] dist = dijkstraList(0, adj);
        System.out.println("Dijkstra dist 0->2: " + (dist[2] >= INF ? -1 : dist[2]) + " (expect 7)");
    }
}

11. Complexity analysis recap 🔍

  • Adjacency matrix: memory O(n²), neighbor iteration O(n), edge check O(1).
  • Adjacency list: memory O(n + m), neighbor iteration O(deg(u)), edge check O(deg(u)).
  • Edge list: memory O(m), good for global operations (sort by weight) but poor for neighbor queries.

When m (edges) ≪ n², adjacency list almost always wins in memory and iteration efficiency.

12. Tips, tricks & common pitfalls 🛠️

  • If you need fast hasEdge(u,v) and graph is small-ish, matrix is perfect. For large n prefer list.
  • For weighted graphs, avoid int if weights accumulate or are large - prefer long.
  • When using matrix for weighted graphs, initialize mat[u][v] = INF for “no edge”.
  • If you build an adjacency list from edge inputs, prefer adj.get(i).ensureCapacity(approxDegree) if you know approximate degrees to avoid reallocations.
  • For undirected graphs, always add both directions (u->v and v->u) - and watch double-counting when iterating edges.
  • When doing many hasEdge checks on a sparse graph, consider List<Set<Integer>> adjSet (e.g., HashSet) to get near O(1) checks with O(deg(u)) iteration still possible.

13. Variations & extensions ✨

  • Adjacency bitset / boolean matrix with BitSet[] or boolean[][] - memory- and cache-friendly for small N (useful for bitset DP / fast intersection ops).
  • Compressed sparse row (CSR) - memory-compact representation used in heavy-duty graph libraries and numerical methods.
  • Adjacency hashmap (List<Map<Integer, Long>>) - when you need O(1) checks and weights per neighbor, but beware overhead.
  • Dynamic graphs - representations that support fast insert/delete of edges often mix lists + hash maps.

14. FAQs - short & helpful ❓

Q: Which to memorize for interviews? A: Adjacency list. It's the most used and versatile. Know matrix basics too.

Q: When to use matrix in contests? A: Small n or when you need fast edge-existence or algorithms that rely on O(1) lookup.

Q: Weighted adjacency list vs edge list for Dijkstra? A: Use adjacency list for Dijkstra. Edge list is for Bellman-Ford or Kruskal.

Q: How to store directed vs undirected? A: For adjacency list/matrix, add only u->v for directed; add both u->v and v->u for undirected.

Q: What about memory limits? A: If n = 10^5, matrix is impossible (10^10 entries). Lists (O(n+m)) are the only practical option.

15. Final short checklist (before you code) ✅

  • Is the graph dense or sparse? → matrix vs list.
  • Do you need fast edge checks? → matrix / hash-set.
  • Are edges weighted? → use AdjNode / long values in lists or matrix of weights.
  • Could recursion depth be a problem? → use iterative traversals.
  • Will sums overflow int? → use long and big INF.