Kamran Mushtaq
Back to AI & LLM
AI & LLM

Graph

Added: August 12, 2026

Definition

A graph is a data structure used to represent entities and the relationships/connections between them.

It consists mainly of:

  • Nodes (vertices) → the entities
  • Edges → the connections/relationships between those entities

Example:

A ─── B │ │ │ │ C ─── D

Here:

  • A, B, C, D = nodes
  • Lines = edges

The Problem That Led to It

An array is good for storing a collection:

[ A, B, C, D ]

A matrix is good for organizing values using rows and columns:

A B C D A ... B ... C ... D ...

But neither one, by itself, directly expresses:

“A is connected to B.”

We need a structure specifically designed to represent relationships between entities.

That's where a graph comes in.

What Problem It Solves

A graph lets us represent things that are connected to or related to each other.

For example:

Road network

City A ─── City B │ │ │ │ City C ─── City D

Nodes → cities/intersections

Edges → roads

Social network

Ali ─── Sara │ │ Ahmed ──┘

Nodes → people

Edges → relationships

Computer network

Server A ─── Router ─── Server B

Nodes → devices

Edges → network connections

Easy Wording

A graph is a way of representing things as nodes and the relationships between those things as edges.

Layman Example

Think about a map.

You have:

Locations = nodes Roads = edges

If Lahore is connected to Islamabad by a road:

Lahore ───────── Islamabad

The graph represents that relationship.

Technical Example

Suppose we have:

A ─── B │ C ─── D

We can describe its edges as:

A → B A → C C → D

So the graph contains:

Nodes = {A, B, C, D}

Edges = {(A,B), (A,C), (C,D)}

This is important because now we can ask computational questions such as:

“Which nodes is A connected to?”

Answer:

B and C

How This Connects to Our Matrix

Here's where everything we've learned starts connecting.

We have a graph:

A ─── B │ C ─── D

We can represent its connections using a matrix:

A B C D A 0 1 1 0 B 1 0 0 0 C 1 0 0 1 D 0 0 1 0

Now:

Graph

→ tells us what is connected to what

Adjacency Matrix

→ puts those connections into rows and columns

And because most possible connections may not exist:

Adjacency Matrix

→ can become a Sparse Matrix

→ which can then be stored efficiently using CSR.

Limitation

Graphs themselves don't dictate one specific way of storing the data.

You can represent a graph using:

  • adjacency matrices
  • adjacency lists
  • edge lists
  • sparse formats such as CSR

The choice depends on what operations and scale you need.