46:"/_next/static/chunks/33yus346z0l_n.js" 47:"/_next/static/chunks/1r8ezocsukqp8.js" 48:"/_next/static/chunks/0iv56yrji_20j.js" 49:"/_next/static/chunks/0wa9m1-tphf9u.js" 4a:"/_next/static/chunks/08cuqqn_f60pp.js" 4b:"/_next/static/chunks/3zdsl3f9b0--r.js" 4c:"/_next/static/chunks/2j22cxchii_xx.js" 4d:"/_next/static/chunks/3bgoyiso1rhn7.js" 4e:"/_next/static/chunks/01a-3hvnqu8wl.js" 4f:"/_next/static/chunks/3m1xjj5kw5fie.js" 50:"/_next/static/chunks/0om3fkgfnicab.js" 51:"/_next/static/chunks/0gafyzg9j9yqj.js" 52:"/_next/static/chunks/20w4eaqlekefm.js" 53:"/_next/static/chunks/449--h5z1s6nq.js" 54:"/_next/static/chunks/3k2gyg36fnag_.js" 55:"/_next/static/chunks/18ggtgz2yf759.js" 56:"/_next/static/chunks/0hlb44ca7-4a2.js" 57:"/_next/static/chunks/253gnmj0-cj17.js" 58:"/_next/static/chunks/09nq57stwzkgf.js" 59:"/_next/static/chunks/082jo-0ajazgr.js" 5a:"/_next/static/chunks/2ozcrjb_hh74t.js" 5b:"/_next/static/chunks/05i8en-x14ibi.js" 5c:"/_next/static/chunks/32izpn90gvm22.js" 5d:"/_next/static/chunks/0jbzid2v9xv3h.js" 5e:"/_next/static/chunks/0i3-eynrkvqi7.js" 5f:"/_next/static/chunks/1tn-0fivsxsv1.js" 60:"/_next/static/chunks/34h36hyf_ggow.js" 61:"/_next/static/chunks/20329i6m_04t6.js" 62:"/_next/static/chunks/161uxd62cjny2.js" 63:"/_next/static/chunks/2k8pepwc4pxns.js" 64:I[593304,["$2b","$2c","$2d","$2e","$2f","$30","$46","$47","$48","$49","$4a","$4b","$4c","$4d","$4e","$4f","$50","$51","$52","$53","$54","$55","$56","$57","$58","$59","$5a","$5b","$5c","$5d","$5e","$5f","$60","$61","$62","$63"],"OwnedHydration"] 65:T5c9,/** * Calculate the break-even edge count where matrix and list * consume approximately equal memory. * * @param vertexCount Number of vertices in the graph * @param matrixBytesPerCell Bytes per matrix cell (1 for bool, 4-8 for numbers) * @param listOverheadPerVertex Bytes overhead per vertex list header * @param listBytesPerEdge Bytes per edge entry in the list * @returns The edge count where both representations use similar memory */ function calculateBreakEvenEdges( vertexCount: number, matrixBytesPerCell: number = 1, listOverheadPerVertex: number = 16, listBytesPerEdge: number = 8 ): number { const matrixSpace = matrixBytesPerCell * vertexCount * vertexCount; // Solve: matrixSpace = listOverheadPerVertex * V + listBytesPerEdge * E const breakEvenEdges = (matrixSpace - listOverheadPerVertex * vertexCount) / listBytesPerEdge; return Math.max(0, Math.floor(breakEvenEdges)); } // Examples console.log("Break-even edges for various vertex counts:"); console.log(` 100 vertices: ${calculateBreakEvenEdges(100)} edges`); console.log(` 1,000 vertices: ${calculateBreakEvenEdges(1000)} edges`); console.log(` 10,000 vertices: ${calculateBreakEvenEdges(10000)} edges`); // Output: // Break-even edges for various vertex counts: // 100 vertices: 1,050 edges (vs max 4,950 for undirected) // 1,000 vertices: 123,000 edges (vs max 499,500) // 10,000 vertices: 12,480,000 edges (vs max 49,995,000)66:T4eb,class BitPackedMatrix { private bits: Uint32Array; private vertices: number; constructor(vertexCount: number) { this.vertices = vertexCount; // Each Uint32 holds 32 edges const totalBits = vertexCount * vertexCount; const uint32Count = Math.ceil(totalBits / 32); this.bits = new Uint32Array(uint32Count); } private getIndex(from: number, to: number): { word: number; bit: number } { const flatIndex = from * this.vertices + to; return { word: Math.floor(flatIndex / 32), bit: flatIndex % 32 }; } hasEdge(from: number, to: number): boolean { const { word, bit } = this.getIndex(from, to); return (this.bits[word] & (1 << bit)) !== 0; } setEdge(from: number, to: number, exists: boolean): void { const { word, bit } = this.getIndex(from, to); if (exists) { this.bits[word] |= (1 << bit); } else { this.bits[word] &= ~(1 << bit); } } memoryUsage(): number { return this.bits.byteLength; } } // For 10,000 vertices: // Regular matrix: 100,000,000 bytes = 95.4 MB // Bit-packed: 12,500,000 bytes = 11.9 MB (8× reduction!)67:T6f6,class CSRGraph { // All neighbors stored consecutively private edges: Uint32Array; // offsets[i] = start index of vertex i's neighbors in edges[] // offsets[V] = total number of edge entries (sentinel) private offsets: Uint32Array; constructor(vertexCount: number, edgeList: [number, number][]) { // Count outgoing edges per vertex const outDegree = new Uint32Array(vertexCount); for (const [from, _to] of edgeList) { outDegree[from]++; } // Compute prefix sums for offsets this.offsets = new Uint32Array(vertexCount + 1); for (let i = 0; i < vertexCount; i++) { this.offsets[i + 1] = this.offsets[i] + outDegree[i]; } // Fill edges array this.edges = new Uint32Array(this.offsets[vertexCount]); const currentPos = new Uint32Array(vertexCount); for (const [from, to] of edgeList) { const pos = this.offsets[from] + currentPos[from]; this.edges[pos] = to; currentPos[from]++; } } *neighbors(vertex: number): Generator { const start = this.offsets[vertex]; const end = this.offsets[vertex + 1]; for (let i = start; i < end; i++) { yield this.edges[i]; } } degree(vertex: number): number { return this.offsets[vertex + 1] - this.offsets[vertex]; } memoryUsage(): number { return this.edges.byteLength + this.offsets.byteLength; } } // Memory comparison for 1M vertices, 10M edges: // Array of arrays: ~16MB (vertex overhead) + ~40MB (edges) = ~56MB // CSR format: ~4MB (offsets) + ~40MB (edges) = ~44MB // Plus: Better cache locality, no allocation fragmentation45:["$","$L64",null,{"owner":"anonymous","state":{"mutations":[],"queries":[{"dehydratedAt":1792316023924,"state":{"data":{"json":{"id":"seed_042d35b2d6ffb67c7daf6249fdd1bbec","slug":"graph-representation-tradeoffs","category":"Data Structures & Algorithms","topic":"Graph Representation Trade-offs","title":"Graph Representation Trade-offs","description":"Master the critical decision-making process for choosing between adjacency matrices and adjacency lists. Understand space-time trade-offs, analyze sparse versus dense graphs, and develop expert intuition for selecting the optimal representation for any graph problem.","difficulty":"INTERMEDIATE","estimatedMinutes":60,"pages":[{"id":"seed_e9d8300892280248f73402cf369143b6","title":"Space Comparison — Matrix vs List","order":0,"content":[{"id":"opening-hook","title":"The Memory Footprint of Graph Representations","content":[{"data":{"content":"When you decide to represent a graph in your program, you're not just choosing a data structure—you're committing to a specific memory allocation pattern that will determine how your program scales. The difference between adjacency matrices and adjacency lists isn't merely theoretical; it can mean the difference between a program that runs smoothly on a laptop and one that crashes with an out-of-memory error.\n\n**The core question:** How much memory does each representation actually consume, and when does one become dramatically more efficient than the other?\n\nThis page provides a rigorous, mathematical analysis of space consumption for both representations, arming you with the precise knowledge needed to make informed engineering decisions."},"type":"text"},{"data":{"icon":"Target","title":"What You Will Learn","content":"By the end of this page, you will understand exactly how to calculate memory usage for both adjacency matrices and adjacency lists. You'll master the mathematical formulas, understand the constants behind asymptotic notation, and develop intuition for when each representation becomes prohibitively expensive or surprisingly efficient.","variant":"info"},"type":"callout"}]},{"id":"adjacency-matrix-space","title":"Adjacency Matrix Space Analysis","content":[{"data":{"content":"An **adjacency matrix** represents a graph G = (V, E) as a two-dimensional array M where M[i][j] indicates the presence (and possibly weight) of an edge from vertex i to vertex j. Let's dissect its space requirements with surgical precision.\n\n**The fundamental space requirement:**\n\nFor a graph with |V| vertices, the adjacency matrix requires exactly |V|² cells. This is an inescapable mathematical fact—every pair of vertices needs a cell to record whether an edge exists between them."},"type":"text"},{"data":{"code":"// For an unweighted graph, each cell stores a boolean (or 0/1)\n// For a weighted graph, each cell stores a number (weight) or null/infinity\n\ninterface AdjacencyMatrix {\n // |V| × |V| matrix\n matrix: number[][]; // or boolean[][] for unweighted\n vertexCount: number;\n}\n\n// Example: Graph with 5 vertices\nconst graph: AdjacencyMatrix = {\n vertexCount: 5,\n matrix: [\n // 0 1 2 3 4 (destination vertices)\n [0, 1, 1, 0, 0], // edges from vertex 0\n [1, 0, 0, 1, 1], // edges from vertex 1\n [1, 0, 0, 1, 0], // edges from vertex 2\n [0, 1, 1, 0, 1], // edges from vertex 3\n [0, 1, 0, 1, 0], // edges from vertex 4\n ]\n};","title":"Adjacency Matrix Structure","language":"typescript"},"type":"code"},{"data":{"content":"**Precise memory calculation:**\n\nLet's compute the exact memory consumption, not just the asymptotic complexity:\n\n**For an unweighted graph (boolean entries):**\n- Each cell stores 1 bit (ideally) or 1 byte (in practice)\n- Total bits: |V|² bits\n- Total bytes (naive): |V|² bytes\n- With bit packing: |V|² / 8 bytes ≈ 0.125 × |V|² bytes\n\n**For a weighted graph (numeric entries):**\n- Each cell stores a number (4 bytes for int32, 8 bytes for float64)\n- Total bytes: |V|² × sizeof(number)\n- For 32-bit integers: 4 × |V|² bytes\n- For 64-bit floats: 8 × |V|² bytes"},"type":"text"},{"data":{"rows":[["100","10,000","10 KB","40 KB","80 KB"],["1,000","1,000,000","1 MB","4 MB","8 MB"],["10,000","100,000,000","100 MB","400 MB","800 MB"],["100,000","10,000,000,000","10 GB","40 GB","80 GB"],["1,000,000","1,000,000,000,000","1 TB","4 TB","8 TB"]],"caption":"Adjacency Matrix Memory Consumption by Graph Size","headers":["Vertices (|V|)","Cells (|V|²)","Unweighted (bytes)","Weighted int32 (bytes)","Weighted float64 (bytes)"]},"type":"table"},{"data":{"icon":"AlertCircle","title":"The Quadratic Explosion","content":"Notice how rapidly memory consumption explodes. A graph with just 100,000 vertices requires 10 GB for an unweighted matrix—and this memory is allocated regardless of how many edges exist. A sparse graph with 100,000 vertices and only 200,000 edges would still consume 10 GB, even though the actual edge information could fit in kilobytes.","variant":"warning"},"type":"callout"},{"data":{"content":"**The independence from edge count:**\n\nThis is the defining characteristic of adjacency matrix space complexity:\n\n**Space = O(|V|²)**\n\nThe number of edges |E| does not appear in this formula. Whether your graph has 0 edges or |V|² edges (complete graph), the matrix consumes the same amount of memory. This independence is both the matrix's greatest strength (predictable allocation) and its most significant weakness (wasteful for sparse graphs)."},"type":"text"}],"titleType":"number","titleNumber":1},{"id":"adjacency-list-space","title":"Adjacency List Space Analysis","content":[{"data":{"content":"An **adjacency list** represents a graph G = (V, E) as an array of lists, where the i-th list contains all vertices adjacent to vertex i. This representation is edge-sensitive—its memory consumption directly reflects the graph's structure.\n\n**The fundamental space requirement:**\n\nFor a graph with |V| vertices and |E| edges:\n- The array of lists requires |V| list headers\n- Each edge contributes to one or two lists (directed vs undirected)\n- Total list elements: |E| for directed graphs, 2|E| for undirected graphs"},"type":"text"},{"data":{"code":"// For an unweighted graph\ninterface AdjacencyListUnweighted {\n // Array of |V| lists, each containing neighbor indices\n adjacency: number[][]; // adjacency[v] = list of neighbors of v\n vertexCount: number;\n}\n\n// For a weighted graph\ninterface WeightedEdge {\n to: number;\n weight: number;\n}\n\ninterface AdjacencyListWeighted {\n adjacency: WeightedEdge[][];\n vertexCount: number;\n}\n\n// Example: Same 5-vertex graph as before\nconst graphList: AdjacencyListUnweighted = {\n vertexCount: 5,\n adjacency: [\n [1, 2], // vertex 0 connects to 1, 2\n [0, 3, 4], // vertex 1 connects to 0, 3, 4\n [0, 3], // vertex 2 connects to 0, 3\n [1, 2, 4], // vertex 3 connects to 1, 2, 4\n [1, 3], // vertex 4 connects to 1, 3\n ]\n};\n\n// Total storage: 5 arrays + 12 integers (each edge appears twice)","title":"Adjacency List Structure","language":"typescript"},"type":"code"},{"data":{"content":"**Precise memory calculation:**\n\nThe memory analysis for adjacency lists is more nuanced because it involves both fixed and variable components:\n\n**For an undirected unweighted graph:**\n\n*Fixed overhead (array of pointers):*\n- |V| array/list headers\n- Each header: 8-24 bytes depending on language (pointer + length + capacity)\n- Estimated: 16 × |V| bytes (typical for dynamic arrays)\n\n*Variable storage (edge data):*\n- 2|E| vertex indices (each edge in both endpoint lists)\n- Each index: 4 bytes (int32) or 8 bytes (int64)\n- Estimated: 4 × 2|E| = 8|E| bytes for int32 indices\n\n**Total: 16|V| + 8|E| bytes (approximate)**"},"type":"text"},{"data":{"content":"**For a directed unweighted graph:**\n\n*Fixed overhead:* Same as undirected\n- 16 × |V| bytes\n\n*Variable storage:*\n- |E| vertex indices (each edge in one list only)\n- 4 × |E| = 4|E| bytes for int32 indices\n\n**Total: 16|V| + 4|E| bytes (approximate)**\n\n**For weighted graphs:**\n\nEach edge entry now includes both destination and weight:\n- Destination: 4 bytes\n- Weight: 4-8 bytes\n- Per edge entry: 8-12 bytes\n\n**Total: 16|V| + 8|E| to 16|V| + 24|E| bytes**"},"type":"text"},{"data":{"rows":[["1,000","2,000","0.2% (very sparse)","17.6 KB","49.6 KB"],["1,000","10,000","1% (sparse)","96 KB","256 KB"],["1,000","100,000","10%","816 KB","2.4 MB"],["1,000","499,500","50% (dense)","4 MB","12 MB"],["10,000","20,000","0.02% (sparse)","320 KB","640 KB"],["10,000","5,000,000","5%","40 MB","120 MB"],["100,000","200,000","0.002%","3.2 MB","6.4 MB"],["100,000","10,000,000","0.1%","81.6 MB","241.6 MB"]],"caption":"Adjacency List Memory for Various Graph Configurations","headers":["Vertices","Edges","Edge Density","Unweighted (bytes)","Weighted (bytes)"]},"type":"table"},{"data":{"icon":"Lightbulb","title":"The Edge-Proportional Advantage","content":"The crucial insight is that adjacency list space scales with actual edges, not potential edges. A graph with 100,000 vertices and 200,000 edges uses only 3.2 MB with lists—versus 10 GB with a matrix. That's a 3,000× difference in memory for the same graph!","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":2},{"id":"mathematical-comparison","title":"Mathematical Comparison Framework","content":[{"data":{"content":"Now let's establish a rigorous mathematical framework for comparing these representations. Understanding when one beats the other requires expressing the break-even point precisely.\n\n**Asymptotic space complexity:**"},"type":"text"},{"data":{"rows":[["Adjacency Matrix","O("],["Adjacency List","O("]],"headers":["Representation","Space Complexity"]},"type":"table"},{"data":{"content":"But asymptotic notation hides the constants. Let's derive the exact break-even point."},"type":"text"},{"data":{"content":"**Deriving the break-even point:**\n\nLet's find when the matrix and list consume equal memory.\n\n*Matrix space:* S_matrix = c₁ × |V|²\n*List space:* S_list = c₂ × |V| + c₃ × |E|\n\nFor typical implementations:\n- c₁ ≈ 1 byte (unweighted) or 4-8 bytes (weighted)\n- c₂ ≈ 16 bytes (array header overhead)\n- c₃ ≈ 8-16 bytes per edge entry\n\nSetting S_matrix = S_list:\n\nc₁ × |V|² = c₂ × |V| + c₃ × |E|\n\n*Solving for |E|:*\n\n|E| = (c₁ × |V|² - c₂ × |V|) / c₃\n|E| ≈ (c₁/c₃) × |V|² - (c₂/c₃) × |V|\n\nFor large |V|, the dominant term is:\n|E| ≈ (c₁/c₃) × |V|²"},"type":"text"},{"data":{"code":"$65","title":"Break-Even Point Calculator","language":"typescript"},"type":"code"},{"data":{"icon":"Info","title":"The Density Threshold","content":"The break-even typically occurs around 10-25% edge density for unweighted graphs. For weighted graphs (where matrix cells are larger), the break-even shifts to even lower densities, making adjacency lists even more favorable for most real-world graphs.","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":3},{"id":"edge-density-analysis","title":"Edge Density: The Key Decision Factor","content":[{"data":{"content":"**Edge density** is the ratio of actual edges to maximum possible edges. It's the single most important factor in choosing between representations.\n\n**Definition:**\n\nFor an undirected graph without self-loops:\n- Maximum edges: |V|(|V|-1)/2\n- **Density = |E| / (|V|(|V|-1)/2)** = 2|E| / (|V|(|V|-1))\n\nFor a directed graph:\n- Maximum edges: |V|(|V|-1) (or |V|² with self-loops)\n- **Density = |E| / (|V|(|V|-1))**\n\nDensity ranges from 0 (no edges) to 1 (complete graph)."},"type":"text"},{"data":{"rows":[["0% - 1%","Very Sparse","Social networks, web graphs, road networks","Adjacency List (strongly)"],["1% - 10%","Sparse","Collaboration networks, citation graphs","Adjacency List"],["10% - 25%","Moderate","Some communication networks, smaller graphs","Context-dependent"],["25% - 50%","Semi-Dense","Certain biological networks, correlation matrices","Consider both"],["50% - 100%","Dense","Complete or near-complete graphs, cliques","Adjacency Matrix often better"]],"caption":"Edge Density Categories and Representation Recommendations","headers":["Density Range","Classification","Typical Examples","Recommended Representation"]},"type":"table"},{"data":{"content":"**Real-world graph densities:**\n\nMost real-world graphs are remarkably sparse. Understanding typical densities helps guide default choices:\n\n**Social Networks:**\n- Facebook friendship graph: ~0.00003% density (avg 150 friends / 2.9B users)\n- Twitter following: ~0.0001% density\n- LinkedIn connections: ~0.0001% density\n\n**Infrastructure Networks:**\n- Internet router topology: ~0.001% density\n- US road network: ~0.00001% density\n- Power grid: ~0.001% density\n\n**Information Networks:**\n- Wikipedia link graph: ~0.0002% density\n- Web hyperlink graph: ~0.00001% density\n- Citation networks: ~0.01% density\n\n**Biological Networks:**\n- Protein interaction: ~0.1-1% density\n- Neural networks (brain): ~1-10% density"},"type":"text"},{"data":{"icon":"CheckCircle","title":"The Practical Takeaway","content":"The vast majority of real-world graphs have densities well below 1%. This means adjacency lists are the appropriate default for nearly all practical applications. Adjacency matrices are the exception, not the rule—reserved for dense graphs, small graphs, or algorithms that specifically benefit from O(1) edge lookup.","variant":"success"},"type":"callout"}],"titleType":"number","titleNumber":4},{"id":"memory-layout-cache","title":"Memory Layout and Cache Efficiency","content":[{"data":{"content":"Raw byte counts don't tell the complete story. How data is arranged in memory affects actual performance through cache effects. Modern CPUs rely heavily on cache hierarchies, and memory access patterns dramatically impact real-world speed.\n\n**Adjacency Matrix Memory Layout:**\n\nMatrices are stored as contiguous 2D arrays (typically row-major in C-like languages):\n\n```\nMemory Address: [0,0][0,1][0,2]...[0,V-1][1,0][1,1]...[V-1,V-1]\n |---- Row 0 ----|---- Row 1 ----| ... |\n```\n\n**Cache implications:**\n- Accessing a single row: Excellent spatial locality\n- Accessing a single column: Poor locality (stride = |V| × element_size)\n- Iterating all edges: Mixed—good for row-wise, poor for column-wise"},"type":"text"},{"data":{"code":"// CACHE-FRIENDLY: Row-major access (sequential memory)\nfunction iterateRowMajor(matrix: number[][], V: number): void {\n for (let i = 0; i < V; i++) {\n for (let j = 0; j < V; j++) {\n // Accesses memory sequentially\n // Each cache line (64 bytes) serves 16 consecutive int32 values\n process(matrix[i][j]);\n }\n }\n}\n// Cache behavior: ~V²/16 cache misses (excellent)\n\n// CACHE-HOSTILE: Column-major access (strided memory) \nfunction iterateColumnMajor(matrix: number[][], V: number): void {\n for (let j = 0; j < V; j++) {\n for (let i = 0; i < V; i++) {\n // Jumps V elements between accesses\n // If V > cache_line_size/element_size, every access is a miss\n process(matrix[i][j]);\n }\n }\n}\n// Cache behavior: ~V² cache misses if V > 16 (terrible)","title":"Cache-Friendly vs Cache-Hostile Matrix Access","language":"typescript"},"type":"code"},{"data":{"content":"**Adjacency List Memory Layout:**\n\nAdjacency lists have more fragmented memory:\n\n```\nMain Array: [ptr_0][ptr_1][ptr_2]...[ptr_V-1]\n ↓ ↓ ↓ ↓\nNeighbor Lists: [2,5] [0,3,7,9] [1] ... [0,2,4]\n```\n\n**Cache implications:**\n- Accessing one vertex's neighbors: Good locality (contiguous list)\n- Iterating all edges: Pointer chasing between lists (cache misses)\n- Random vertex access: Poor locality (indirect access)"},"type":"text"},{"data":{"left":[{"data":{"items":["Predictable memory access patterns","Row-wise iteration is cache-optimal","No pointer chasing or indirection","Prefetching works effectively","SIMD operations can process multiple cells"],"title":{"icon":"CheckCircle","text":"Matrix Cache Advantages","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"}],"right":[{"data":{"items":["Only relevant edges in cache","Neighbor iteration is compact","Working set is proportional to edges","Less memory bandwidth for sparse graphs","May fit in cache when matrix wouldn't"],"title":{"icon":"CheckCircle","text":"List Cache Advantages","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"}]},"type":"two-column"},{"data":{"icon":"Lightbulb","title":"The Working Set Insight","content":"For sparse graphs, the adjacency list's working set (active data in cache) is proportional to edges being processed. The matrix must potentially load entire rows even if most entries are zeros. When the graph is sparse enough that the adjacency list fits in L3 cache but the matrix doesn't, the list can be dramatically faster despite pointer indirection.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":5},{"id":"memory-optimization","title":"Practical Memory Optimization Techniques","content":[{"data":{"content":"Both representations admit various optimizations that can significantly reduce memory footprint. Understanding these techniques is essential for production systems.\n\n**Matrix Optimizations:**"},"type":"text"},{"data":{"items":["Store each edge as a single bit instead of a byte","Reduces memory by 8× for unweighted graphs","Pack 64 edges per 64-bit word","Trade-off: Bit manipulation overhead for access","Implementation: Use bitwise operations for get/set"],"title":"Bit Packing for Unweighted Graphs","variant":"accent"},"type":"list"},{"data":{"code":"$66","title":"Bit-Packed Adjacency Matrix","language":"typescript"},"type":"code"},{"data":{"content":"**Symmetric Matrix Optimization:**\n\nFor undirected graphs, the matrix is symmetric (M[i][j] = M[j][i]). We can store only the upper or lower triangle:\n\n- Full matrix: |V|² cells\n- Triangular storage: |V|(|V|+1)/2 cells\n- Savings: Nearly 50% reduction\n\nThe trade-off is slightly more complex indexing, but for large graphs, the memory savings are substantial."},"type":"text"},{"data":{"content":"**Adjacency List Optimizations:**\n\n**1. Compressed Sparse Row (CSR) Format:**\n\nInstead of an array of dynamic arrays, use two static arrays:\n- `edges[]`: All neighbors concatenated\n- `offsets[]`: Starting position of each vertex's neighbors\n\nThis eliminates per-list overhead and improves cache performance."},"type":"text"},{"data":{"code":"$67","title":"Compressed Sparse Row (CSR) Format","language":"typescript"},"type":"code"},{"data":{"icon":"Info","title":"Production Systems","content":"High-performance graph libraries like SNAP, NetworkX (for certain backends), and GraphBLAS use CSR or similar compressed formats. When processing billion-edge graphs, these optimizations can reduce memory usage by 30-50% compared to naive implementations while simultaneously improving cache performance.","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":6},{"id":"summary","title":"Summary: Space Comparison Key Insights","content":[{"data":{"content":"We've conducted a thorough analysis of memory requirements for both graph representations. Let's consolidate the essential takeaways:"},"type":"text"},{"data":{"type":"ordered","items":["**Adjacency Matrix: O(|V|²) space** — Memory is independent of edge count, making it wasteful for sparse graphs but predictable and compact for dense graphs.","**Adjacency List: O(|V| + |E|) space** — Memory scales with actual graph structure, making it dramatically more efficient for typical real-world graphs.","**Break-even density is typically 10-25%** — Below this, lists win; above this, matrices become competitive. Most real graphs are far below this threshold.","**Real-world graphs are overwhelmingly sparse** — Social networks, infrastructure networks, and information networks typically have densities well under 1%.","**Cache effects matter** — Matrix row-wise access is cache-friendly; list access has better working set behavior for sparse graphs.","**Optimization techniques exist for both** — Bit packing and triangular storage for matrices; CSR format for lists. These can provide significant constant-factor improvements."],"title":{"icon":"CheckCircle","text":"Key Takeaways","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"content":"**What's next:**\n\nSpace is only half the story. The next page examines time complexity for common operations—edge lookup, neighbor iteration, and edge insertion/deletion. You'll see how the space-time trade-off plays out in practice, and why the 'best' representation depends not just on the graph, but on which operations your algorithm performs most frequently."},"type":"text"},{"data":{"icon":"CheckCircle","title":"Page Complete","content":"You now have a rigorous understanding of the memory requirements for adjacency matrices and adjacency lists. You can calculate exact memory usage, identify break-even points, and understand why adjacency lists are the default choice for most real-world graphs. Next, we'll analyze the time complexity trade-offs to complete the picture.","variant":"success"},"type":"callout"}],"titleType":"number","titleNumber":7}],"isLocked":false},{"id":"seed_945124270b1b80a5b40bc0aca8081759","title":"Time Comparison for Common Operations","order":1,"content":null,"isLocked":true},{"id":"seed_a628875429f27ca0b40a93de045416d6","title":"Sparse vs Dense Graphs","order":2,"content":null,"isLocked":true},{"id":"seed_1b43d3d34a0cf258f0b15a70287961c3","title":"Choosing the Right Representation","order":3,"content":null,"isLocked":true}]}},"dataUpdateCount":1,"dataUpdatedAt":1792316023840,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["learningContent","getModule"],{"input":{"slug":"graph-representation-tradeoffs"},"type":"query"}],"queryHash":"[[\"learningContent\",\"getModule\"],{\"input\":{\"slug\":\"graph-representation-tradeoffs\"},\"type\":\"query\"}]"},{"dehydratedAt":1792316023925,"state":{"data":{"json":null},"dataUpdateCount":1,"dataUpdatedAt":1792316023921,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["learningContent","getProgress"],{"input":{"moduleId":"seed_042d35b2d6ffb67c7daf6249fdd1bbec"},"type":"query"}],"queryHash":"[[\"learningContent\",\"getProgress\"],{\"input\":{\"moduleId\":\"seed_042d35b2d6ffb67c7daf6249fdd1bbec\"},\"type\":\"query\"}]"},{"dehydratedAt":1792316023925,"state":{"data":{"json":null},"dataUpdateCount":1,"dataUpdatedAt":1792316023923,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["feedback","get"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_945124270b1b80a5b40bc0aca8081759"},"type":"query"}],"queryHash":"[[\"feedback\",\"get\"],{\"input\":{\"contentId\":\"seed_945124270b1b80a5b40bc0aca8081759\",\"contentType\":\"LEARNING_PAGE\"},\"type\":\"query\"}]"},{"dehydratedAt":1792316023925,"state":{"data":{"json":null},"dataUpdateCount":1,"dataUpdatedAt":1792316023923,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["feedback","getUserLike"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_945124270b1b80a5b40bc0aca8081759"},"type":"query"}],"queryHash":"[[\"feedback\",\"getUserLike\"],{\"input\":{\"contentId\":\"seed_945124270b1b80a5b40bc0aca8081759\",\"contentType\":\"LEARNING_PAGE\"},\"type\":\"query\"}]"},{"dehydratedAt":1792316023925,"state":{"data":{"json":[]},"dataUpdateCount":1,"dataUpdatedAt":1792316023923,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["highlights","getHighlights"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_945124270b1b80a5b40bc0aca8081759"},"type":"query"}],"queryHash":"[[\"highlights\",\"getHighlights\"],{\"input\":{\"contentId\":\"seed_945124270b1b80a5b40bc0aca8081759\",\"contentType\":\"LEARNING_PAGE\"},\"type\":\"query\"}]"},{"dehydratedAt":1792316023925,"state":{"data":"$undefined","dataUpdateCount":0,"dataUpdatedAt":0,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"pending","fetchStatus":"fetching"},"queryKey":[["highlights","getPopularHighlights"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_945124270b1b80a5b40bc0aca8081759","minCount":2},"type":"query"}],"queryHash":"[[\"highlights\",\"getPopularHighlights\"],{\"input\":{\"contentId\":\"seed_945124270b1b80a5b40bc0aca8081759\",\"contentType\":\"LEARNING_PAGE\",\"minCount\":2},\"type\":\"query\"}]","promise":"$@68"}]},"children":"$L69"}]