Overview
An adjacency matrix gives constant-time edge lookup but uses O(V^2) space, making it better for dense graphs.
CoreSource checked
Graph Adjacency Matrix
Represents graph edges with a matrix indexed by source and destination nodes.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Data Structures
- Difficulty
- Beginner
- Family
- Graph Representation
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 1
- Relationships
- 4
- Code example
- Ready
- Visualization
- Ready
Core Concepts
edge matrixdense graphconstant lookupnode index
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(1)
Average
O(1)
Worst
O(1)
Space
O(V^2)
When to Use
- Use when fast lookup needs edge matrix.
- Use when the input matches the assumptions behind graph Representation.
When Not to Use
- Avoid when the operation mix does not benefit from the structure's maintenance cost.
- Avoid when a simpler algorithm gives the required result with less setup.
What It Does
- Represents graph edges with a matrix indexed by source and destination nodes
- Uses edge matrix and dense graph to guide the work.
- Produces stored structure.
Use Cases
- Fast lookup
- Maintaining ordered data
- Representing graphs or spatial data
Inputs
- Items
- Keys or indexes
- Operations to support
Outputs
- Stored structure
- Query results
- Updated state
Key Formulas (1)
Edge lookup
edgeexists = matrix[u][v]
edge_exists = matrix[u][v]Checks whether an edge is present between two indexed nodes.
Pseudocode
- 1.Initialize the storage layout and invariants
- 2.For each update, locate the affected position or node
- 3.Modify pointers, counters, buckets, or summary values
- 4.Repair invariants such as balance, order, or load bounds
- 5.Answer queries from the maintained structure
Canonical Example
- Input
- Graph Adjacency Matrix
- Output
- Stored structure
- Explanation
- Graph Adjacency Matrix applies edge matrix to produce stored structure.
Implementation Notes
- Test insertion, deletion, lookup, and boundary cases separately.
- Keep the edge matrix step separate enough to test independently.
- Test updates and queries as sequences, not only one operation at a time.
Common Pitfalls
- Ignoring update costs can make a structure look faster than it is in practice.
- Test edge cases, not only clean examples.
- Incorrect updates can leave stale pointers, counts, balance metadata, or cached summaries.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationShow the structure layout and how operations move through or update it.
Step 1 of 5: Initialize the storage layout and invariants
data-structures-mechanismNotes
Graph Adjacency Matrix should be used with the assumptions and tradeoffs of graph Representation in mind.
Sources (1)
What each reference supports for this entry.
Introduction to Algorithms (CLRS)
BookReference for Graph Adjacency Matrix matrix graph storage and edge-query tradeoffs.
Explore Next
Good next jumps from the relationship graph, ranked for useful discovery.
AlternativesEdge List Representation
Data Structures · Foundation
Adjacency matrices favor direct edge-existence checks at higher memory cost.
Compare with thisRelationships
View full relationship pageAlternative toGraph Adjacency List
Adjacency matrices trade memory for constant-time edge tests compared with adjacency lists.
Related Algorithms
Tags
Data StructureGraphGraph RepresentationMatrix