Adjacency Matrix

Posted on by

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   0

Why 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.