Overview
Compressed Sparse Row represents each row as a contiguous slice of nonzero values. A row-pointer array marks where each row begins and ends in the value and column-index arrays.
CoreSource checked
Compressed Sparse Row
Stores a sparse matrix by keeping nonzero values, column indices, and row offsets.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Data Structures
- Difficulty
- Intermediate
- Family
- Graph Data Structures
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 0
- Relationships
- 5
- Code example
- Ready
- Visualization
- Ready
Core Concepts
sparse matrix and graph storagegraph data structuresdata structures
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(1)
Average
O(V + E)
Worst
O(V + E)
Space
O(V + E)
When to Use
- Use when row-wise traversal dominates the workload.
- Use when the sparse structure is mostly static after construction.
When Not to Use
- Avoid when frequent insertion and deletion of nonzeros is required.
- Avoid when column-wise traversal dominates and no transpose is stored.
What It Does
- Stores only nonzero matrix entries
- Keeps column indices aligned with values
- Uses row offsets to find each row's slice
Use Cases
- Sparse matrix-vector multiplication
- Graph adjacency storage for static sparse graphs
- Linear algebra workloads with many zero entries
Inputs
- Keys, values, items, or graph records
- Operations such as insert, delete, or query
Outputs
- Stored structure state
- Query result or updated collection
Pseudocode
- 1.Group nonzero entries by row
- 2.Append each nonzero value and its column index
- 3.Record the current nonzero count as each row's start offset
- 4.Append a final sentinel offset after the last row
- 5.Use row_ptr[r] to row_ptr[r + 1] to scan row r
Canonical Example
- Input
- matrix rows [[0, 5, 0], [2, 0, 3]]
- Output
- values [5, 2, 3], columns [1, 0, 2], row_ptr [0, 1, 3]
- Explanation
- Row 0 uses entries 0..1, and row 1 uses entries 1..3 in the value arrays.
Implementation Notes
- Build CSR from coordinate triples by sorting or grouping entries by row.
- Decide how duplicate row-column entries are combined.
- Test empty rows and the final sentinel row pointer.
Common Pitfalls
- Row pointers must have length row_count + 1.
- Column indices and values must stay exactly aligned.
- Unsorted columns can surprise algorithms that expect sorted row slices.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationShow packing row offsets and column indices into contiguous arrays on a small sparse matrix and graph storage example.
Step 1 of 5: Group nonzero entries by row
data-structures-mechanismNotes
CSR is compact and fast for row traversal, but awkward for structural mutation.
Sources (1)
What each reference supports for this entry.
Templates for the Solution of Linear Systems
BookReference for compressed sparse row storage and sparse matrix access patterns.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
AlternativesEdge List Representation
Data Structures · Foundation
CSR stores sparse adjacency more compactly for indexed traversal and numerical-style graph processing.
Compare with thisAlternative toGraph Adjacency Matrix
Data Structures · Core
CSR avoids storing zero entries, unlike dense matrix-style layouts.
Compare with thisOften paired withCuthill-McKee Algorithm
Numerical Methods · Extended
Cuthill-McKee orderings are often used before sparse matrix work stored or processed with compressed sparse formats.
Compare with thisRelationships
View full relationship pageConceptual neighborGraph Adjacency List
CSR can store static sparse graph adjacency lists in compact arrays.
Alternative toGraph Adjacency Matrix
CSR avoids storing zero entries, unlike dense matrix-style layouts.
Related Algorithms
Tags
Data StructureLinear AlgebraGraph