Adjacency Matrix

An alternate way to represent adjacent edges. It is also more space expensive.

Drawing 2025-03-12 11.45.37.excalidraw

⚠ Switch to EXCALIDRAW VIEW in the MORE OPTIONS menu of this document. ⚠

Text Elements

A

B

C

D

E

F

A

B

C

D

E

F

G

0

1

2

3

5

4

6

N

N

0

1

1

0

0

0

1

0

1

1

0

0

Link to original

Undirected Graph

• Matrix would be symmetrical
• Diagonals would be 0

Directed Graph

• Matrix is not symmetrical
• Diagonals do not necessarily need to be 0

Graph Operations

• Adding an edge ($i,j$)
  • Worst case : $O(1)$
• Remove edge ($i,j$)
  • Worst case: $O(1)$
• Edge Query
  • Worst case: $O(1)$
• Adding a node
  • Worst case: $O(n^2)$
• Deleting a node
  • Worst case: $O(n)$