Sequential Representation of Graphs

Posted on by

Sequential Representation of Graphs

When you hear the word graph, you might imagine a bunch of points connected with lines — like cities connected by roads, or friends connected in a social network.

In Data Structures, a graph is exactly that:

  • Vertices (nodes) → the points
  • Edges → the connections between the points

Now the big question is:

👉 How do we store a graph inside a computer?

One simple way is to keep everything in sequential form (like arrays).
This is called Sequential Representation.

Let me guide you step by step.

🌿 What Is Sequential Representation?

Think of sequential representation as making a table or grid that shows which vertices are connected.

The most common way to do this is the Adjacency Matrix.

🧊 Adjacency Matrix — Easy Idea

Imagine you list all the vertices both horizontally and vertically.
Then you fill the table:

  • Write 1 when there is a connection
  • Write 0 when there is no connection

It’s like making a friendship table:

| | A | B | C |
| – | – | – | – |
| A | ? | ? | ? |
| B | ? | ? | ? |
| C | ? | ? | ? |

Now fill it with 1s and 0s.

🎨 Simple Diagram

Here’s a small graph with 3 vertices:

   (A) ---- (B)
     \
      \
      (C)

Connections:

  • A is connected to B
  • A is connected to C
  • B is not connected to C

Now the adjacency matrix looks like this:

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

Why 0 on the diagonal?

Because a vertex is usually not considered connected to itself.

💡 How It Works (In Simple Terms)

Imagine each row is saying:

  • Row A: “I know B and C!”
  • Row B: “I only know A!”
  • Row C: “Same here, I only know A.”

You can find whether two nodes are connected in constant time (O(1)), because you just check one cell.

💼 Where Is Sequential Representation Useful?

Sequential representation is great when:

  • The graph is small, or
  • The graph is dense (many edges), or
  • You need fast lookups for connections

Example:
In computer networks, routers may keep a table to quickly check if a direct link exists.

🌱 Advantages (Friendly View)

✔ Very easy to understand
✔ Very easy to find if two vertices are connected
✔ Works well for dense graphs
✔ Good for matrix-based algorithms (like Floyd–Warshall)

🌩 Disadvantages (Honest View)

✘ Uses a lot of memory (especially when connections are few)
✘ Not great for sparse graphs
✘ Adding or removing vertices is slow — because the whole matrix changes