Adjacency Matrix
Adjacency Matrix
When you study graphs, you’ll often hear people say things like “We need to store the connections between nodes.”
A graph is basically a collection of points (called vertices) and lines between those points (called edges).
Now the question is:
How do we store this graph inside a computer in a neat and organized way?
One popular method is called the Adjacency Matrix.
Let’s understand it slowly and comfortably.
🌿 What Is an Adjacency Matrix?
Imagine you have a small group of friends: A, B, C, and D.
Sometimes you want to know who is connected to whom.
An adjacency matrix is like a friendship chart.
- It has a row for each vertex.
- It has a column for each vertex.
- Every cell tells whether two vertices share a connection.
We normally write:
- 1 → if there is an edge
- 0 → if there is no edge
It’s that simple.
It’s like marking Yes or No, but using numbers.
🎨 A Small Graph Example
Let’s take a tiny graph with 4 vertices:
(A) ----- (B)
| |
| |
(C) (D)Connections:
- A ↔ B
- A ↔ C
- B ↔ D
- C and D are not connected
🧾 Adjacency Matrix for This Graph
We list the vertices in order: A, B, C, D
Now create a 4×4 grid:
A B C D
A 0 1 1 0
B 1 0 0 1
C 1 0 0 0
D 0 1 0 0Why does A–A, B–B, C–C, D–D show 0?
Because a vertex usually doesn’t connect to itself.
Why does A–B show 1 and B–A also show 1?
Because this is an undirected graph, and connections work both ways.
If you go from A to B, you can also come back from B to A.
💡 A Simple Analogy: Bus Routes
Think of each vertex as a bus stop.
The adjacency matrix is like a table telling which stops have direct buses between them.
- If there is a direct bus → put 1
- If not → put 0
This makes it easy to check connections quickly.
⚡ Why Is the Adjacency Matrix Useful?
✔ Super fast checks
Want to know if C connects to A?
Just look at the cell (C, A).
In one step, you get the answer.
✔ Easy for computers
Computers love tables.
They can jump to any cell instantly.
✔ Great for dense graphs
If your graph has a lot of edges, the matrix becomes very helpful.
🌩 When Is It Not So Great?
Every graph with n vertices needs an n × n matrix.
So if you have 1,000 vertices, you get a giant 1000×1000 table.
Most of those cells may be zeros.
So adjacency matrices aren’t ideal for sparse graphs (graphs with few edges).
Also:
- Adding a new vertex means rebuilding the whole matrix.
- It uses a lot of memory when the graph is large.
About the Author
