Data Structures for Graphs | Adjacency Matrix, List, and Incidence Matrix

Graphs can be represented in multiple ways using different data structures. These structures help us efficiently track how vertices are connected and make graph operations like traversal, searching, and pathfinding faster and easier. The most commonly used graph representations are Adjacency Matrix, Adjacency List, and Incidence Matrix.

In an Adjacency Matrix, connections between vertices are stored in a grid using 1s and 0s. An Adjacency List keeps a list of neighbors for each vertex, making it space-efficient for large or sparse graphs. An Incidence Matrix represents the relationship between vertices and edges. Each method has its own advantages and is chosen based on the type of graph and the operations we need to perform.

Various Data Structures for Graphs

There are three ways to store a graph

1. Adjacency Matrix
2. Adjacency List
3. Incidence Matrix

1. Adjacency Matrix

An Adjacency Matrix is a square table (2D array) used to represent a graph. Each row and column of the matrix represents a vertex, and the values in the table show whether two vertices are connected.

• If there is an edge (connection) between two vertices, we write 1.
• If there is no edge, we write 0.

Let’s understand how the adjacency matrix works for weighted graphs, undirected graphs, and directed graphs (digraphs) .

1.1. Unweighted Graphs in Adjacency Matrix

An unweighted graph is a graph where edges have no weight or cost. Each edge simply shows a connection between two vertices, and all connections are treated equally. The adjacency matrix of an unweighted graph is a table that tells us whether a connection exists between every pair of vertices.

• 1 indicates that an edge (connection) exists between two vertices.
• 0 indicates that no connection exists.

The rows and columns represent the same set of vertices, so you can easily check if two vertices are connected by looking at the cell where their row and column meet.

In an undirected graph, the adjacency matrix is symmetric. This means if vertex A is connected to vertex B, then vertex B is also connected to vertex A.

Example of Unweighted Graphs in Adjacency Matrix

Vertices: A, B, C
Edges: A–B, B–C

Adjacency Matrix:

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

What the Table Shows

• The rows and columns are the vertices: A, B, C.
• 1 means there is a connection (edge) between two vertices.
• 0 means there is no connection.

Reading the Table

• Row A:
  • A → A = 0 → A is not connected to itself
  • A → B = 1 → A is connected to B
  • A → C = 0 → A is not connected to C
• Row B:
  • B → A = 1 → B is connected to A
  • B → B = 0 → B is not connected to itself
  • B → C = 1 → B is connected to C
• Row C:
  • C → A = 0 → C is not connected to A
  • C → B = 1 → C is connected to B
  • C → C = 0 → C is not connected to itself

1.2. Weighted Graphs in Adjacency Matrix

In a weighted graph, every edge has a weight or cost associated with it. This weight can represent distance, time, cost, or any value that measures how strong or meaningful the connection is between two vertices.

In the Adjacency Matrix of a weighted graph:

• Instead of writing 1 to show a connection, we write the actual weight of the edge.
• If there is no edge between two vertices, we usually write 0.
  (In some cases, ∞ or –1 is used to clearly show that no connection exists.)

This representation helps us easily compare weights and perform algorithms like Dijkstra’s and Prim’s more efficiently.

Example of Weighted Graphs in Adjacency Matrix

Suppose we have three vertices A, B, and C with the following weights:

• A–B = 5
• B–C = 7

Nodes	A	B	C
A	0	5	0
B	5	0	7
C	0	7	0

What the table shows

• The rows and columns are the vertices: A, B, C.
• The numbers show the weight of the connection (edge) between two vertices.
  • 0 means no connection.
  • Any other number (like 5 or 7) is the weight or cost of the edge.

Reading the table

1. Row A:
   • A → A = 0 → A is not connected to itself.
   • A → B = 5 → A is connected to B with a weight of 5.
   • A → C = 0 → A is not connected to C.
2. Row B:
   • B → A = 5 → B is connected to A with a weight of 5.
   • B → B = 0 → B is not connected to itself.
   • B → C = 7 → B is connected to C with a weight of 7.
3. Row C:
   • C → A = 0 → C is not connected to A.
   • C → B = 7 → C is connected to B with a weight of 7.
   • C → C = 0 → C is not connected to itself.

2. Adjacency List

An Adjacency List is a graph representation method that uses lists instead of a table. For each vertex, we maintain a list of all the vertices it is directly connected to.

This method is highly space-efficient, especially for sparse graphs (graphs with many vertices but relatively few edges). Since it stores only existing connections, it avoids the unnecessary space used in an adjacency matrix for non-existent edges.

2.1. Unweighted Graphs in Adjacency List

In an unweighted graph, edges do not have any weight or cost. Each edge simply represents a connection between two vertices.

In the Adjacency List of an unweighted graph:

• Each vertex stores a list of neighbors it is connected to.
• The order of vertices in the list does not matter.

Example of Unweighted Graphs in Adjacency List

Vertices: A, B, C
Edges: A–B, B–C

Adjacency List:

• A → B
• B → A, C
• C → B

What the List Shows?

• Each vertex has a list of vertices it is directly connected to.
• Only existing connections are stored, so it saves space compared to a matrix.
• There is no need to store zeros for non-existing edges.

Reading the Adjacency List

• Vertex A: A → B → A is connected to B
• Vertex B: B → A, C → B is connected to A and C
• Vertex C: C → B → C is connected to B

You can quickly find all neighbors of any vertex just by looking at its list.

2.2. Weighted Graphs in Adjacency List

In a weighted graph, every edge has a weight or cost associated with it. In an Adjacency List, we store not just the neighboring vertex but also the weight of the edge connecting them. This allows algorithms to easily access both the connection and its cost when performing operations like shortest path or minimum spanning tree.

Example of Weighted Graphs in Adjacency List

Vertices: A, B, C
Edges with weights: A–B = 5, B–C = 7

Adjacency List with Weights

• A → B (5)
• B → A (5), C (7)
• C → B (7)

What the List Shows

• Each vertex stores only the connected vertices along with weight.
• A → B (5): A is connected to B with a weight of 5.
• B → A (5), C (7): B is connected to A with weight 5 and C with weight 7.
• C → B (7): C is connected to B with weight 7.

Reading the Adjacency List

• Vertex A: A → B (5) → A is connected to B with weight 5
• Vertex B: B → A (5), C (7) → B is connected to A with weight 5 and C with weight 7
• Vertex C: C → B (7) → C is connected to B with weight 7

3. Incidence Matrix

An Incidence Matrix is another way to represent a graph using a table, but instead of only vertices, it shows the relationship between vertices and edges.

• The rows represent vertices.
• The columns represent edges.
• The entries show whether a vertex is connected to an edge.

This representation is useful for some algorithms and for understanding how vertices and edges relate directly.

3.1. Unweighted Graphs in Incidence Matrix

In an unweighted graph, each entry in the incidence matrix is either 1 or 0:

• 1 → the vertex is connected to that edge.
• 0 → the vertex is not connected to that edge.

Example of Unweighted Graphs in Incidence Matrix

Vertices: A, B, C
Edges: e1 = A–B, e2 = B–C

Incidence Matrix:

vertices | edges	e1	e2
A	1	0
B	1	1
C	0	1

What the Table Shows

• Rows → vertices (A, B, C)
• Columns → edges (e1, e2)
• 1 means the vertex is part of the edge.
• 0 means the vertex is not part of the edge.

Reading the Table:

• Row A:
  • A → e1 = 1 → A is connected to edge e1
  • A → e2 = 0 → A is not connected to edge e2
• Row B:
  • B → e1 = 1 → B is connected to edge e1
  • B → e2 = 1 → B is connected to edge e2
• Row C:
  • C → e1 = 0 → C is not connected to edge e1
  • C → e2 = 1 → C is connected to edge e2

3.2. Weighted Graphs in Incidence Matrix

In a weighted graph, instead of 1, the weight of the edge can be written in the corresponding cell for each vertex.

• If a vertex is not connected to an edge, we write 0.

Example of Weighted Graphs in Incidence Matrix

Edges with weights: e1 = A–B (5), e2 = B–C (7)

This means:

• Edge e1 connects A and B with weight 5
• Edge e2 connects B and C with weight 7

Nodes	e1	e2
A	5	0
B	5	7
C	0	7

Explanation of the Table

• Row A:
  A is connected only to e1, and the weight is 5 → so A’s row is (5, 0).
• Row B:
  B is connected to both edges:
  • e1 with weight 5
  • e2 with weight 7
    So B’s row is (5, 7).
• Row C:
  C is connected only to e2, with weight 7 → so C’s row is (0, 7).

This matrix clearly shows which vertex participates in which edge and the weight of each connection.

Conclusion

Understanding the different data structures used to represent graphs is essential for working with graph-based problems in DSA. Each representation—Adjacency Matrix, Adjacency List, and Incidence Matrix—has its own strengths depending on the type of graph and the operations you need to perform.

• The Adjacency Matrix is easy to understand and fast for checking connections.
• The Adjacency List is highly space-efficient, especially for large and sparse graphs.
• The Incidence Matrix clearly shows relationships between vertices and edges.

Choosing the right representation helps improve both performance and memory usage in graph algorithms. By understanding how each structure works, you can select the best one for your problem and build more efficient solutions.