Course contentsShow
← Computer Science
Lesson 670 of 2,87216. Graphs: Representation and Basic ConceptsFree lesson

Adjacency Matrix: Operations and Complexity

Analyze time complexity of edge insertion, deletion, and lookup operations in adjacency matrix representation.

Adjacency Matrix: Operations and Complexity

What You'll Learn

You'll learn how fast (or slow) basic graph operations are when using an adjacency matrix representation.

Core Operations and Their Complexity

An adjacency matrix stores graph edges in a 2D array. Let's analyze how efficiently it handles three fundamental operations for a graph with n vertices.

Edge Insertion

Adding an edge from vertex u to vertex v:

  • Set matrix[u][v] = 1 (or the edge weight)
  • For undirected graphs, also set matrix[v][u] = 1

Time Complexity: O(1) — constant time! You directly access the array position and update it. It's like flipping a light switch; you know exactly where it is.

Edge Deletion

Removing an edge between vertices u and v:

  • Set matrix[u][v] = 0
  • For undirected graphs, also set matrix[v][u] = 0

Time Complexity: O(1) — again, direct array access makes this instant.

Edge Lookup (Query)

Checking if edge (u, v) exists:

  • Return matrix[u][v] (check if it's non-zero)

Time Complexity: O(1) — just read one cell in the matrix.

The Trade-off

While adjacency matrices excel at edge operations, they use O(n²) space regardless of how many edges actually exist. Finding all neighbors of a vertex requires scanning an entire row, taking O(n) time even if the vertex has only one neighbor.

Think of it like a seating chart for n people: checking if two specific people sit together is instant (lookup), adding or removing a seating assignment is instant (insertion/deletion), but listing everyone sitting next to one person means checking all n seats (neighbor enumeration).

Key Takeaway: Adjacency matrices provide O(1) edge insertion, deletion, and lookup, making them ideal for dense graphs where fast edge queries matter, despite their O(n²) space cost.