Graph representation in data structure

Graph representation is about how we store and organize a graph in a computer so that it can be easily used and processed. A graph is made up of points called vertices (or nodes) and lines connecting them called edges. In a directed graph, edges have a direction, so an edge from u to v is different from an edge from v to u, while in an undirected graph, edges have no direction, so u to v is the same as v to u. Edges can also have weights representing distance, cost, or value.

Graph representation allows the computer to store all this information efficiently, and there are common methods like the adjacency matrix, which uses a 2D table to store connections, and the adjacency list, which keeps a list of connected vertices for each vertex.

Graphs are widely used in real life, such as in maps where locations are vertices and roads are edges, in social networks where people are vertices and friendships are edges, and in internet networks where computers are vertices and connections are edges. In simple terms, graph representation is the way a computer stores all the points and connections of a graph so we can easily work with it.

What is a Graph in Data Structure?

A graph is a collection of:

• Vertices (V): Also called nodes, represent entities such as people, places, or objects.
• Edges (E): Represent connections or relationships between pairs of vertices.

Graphs can be:

• Directed: Edges have a direction → (u, v) ≠ (v, u)
• Undirected: Edges have no direction → (u, v) = (v, u)
• Weighted: Edges have weights or costs.
• Unweighted: Edges have no associated weight.

Example:
In a social media network like Facebook:

• Each person = a vertex
• Friendships or followers = edges

Why Do We Represent Graphs?

Storing graphs efficiently helps us:

• Perform traversals (like BFS and DFS)
• Run algorithms (Dijkstra, Prim’s, Kruskal’s)
• Optimize storage space and time complexity

There are two popular ways to represent graphs:

1. Adjacency Matrix
2. Adjacency List

1. Adjacency matrix representation

An adjacency matrix is a method to represent a graph in a computer using a 2D table of size V × V, where V is the number of vertices in the graph. Each row and column of the matrix represents a vertex. The value in a cell at position (i, j) shows whether there is an edge between vertex i and vertex j. If there is an edge, the cell contains 1 (or the weight of the edge if it is a weighted graph). if there is no edge, it contains 0. In this way, the adjacency matrix clearly shows which vertices are connected, making it easy to check for edges and work with the graph in algorithms. It works for both directed and undirected graphs, in directed graphs, (i, j) and (j, i) can be different, while in undirected graphs, they are the same.

For Un-Directed graph

M[i][j] = 1 ↔ M[j][i] = 1

In an adjacency matrix of a graph, Mi,j​=1 when there is an edge between vertex i and vertex j, and Mi,j​=0 when no edge exists between them. The direction of the edge does not matter in this case.

For Directed graph

The direction matters, M[i][j] = 1 only if edge goes from i → j

In an adjacency matrix representation of a directed graph, M[i][j]=1 if there is an edge that starts from vertex i and ends at vertex j. If no such edge exists, then M[i][j]=0. In this case, M[i][j] is not always equal to M[j][i] since the direction of edges matters in a directed graph.

The adjacency matrix lets us quickly check if an edge exists between two nodes in constant time O(1). However, it uses more memory, with a space complexity of O(V²), where V is the number of vertices.

Time and Space Complexity:

Operation	Complexity
Check edge	O(1)
Add edge	O(1)
Space required	O(V²)

Advantages:

• Fast edge lookup: O(1)
• Simple and easy to implement

Disadvantages:

• Wastes space for sparse graphs
• Not memory efficient if edges ≪ vertices²

2. Adjacency list representation

An adjacency list is a simple way to represent a graph in a computer’s main memory. In this method, we keep a list of all the vertices in the graph, and for each vertex, we store another list that contains all the vertices directly connected to it by an edge. This makes it easy to see the neighbors of any vertex. The adjacency list is more space-efficient than an adjacency matrix, especially when the graph has fewer edges

Un-directed graph

If A is connected to B, then:

• A’s list contains B
• B’s list contains A

Directed graph

Only list the outgoing edges from each vertex.

Time and Space Complexity

Operation	Complexity
Check edge	O(V)
Add edge	O(1)
Space required	O(V + E)

Advantages:

• Saves space for sparse graphs
• Easy to iterate over neighbors

Disadvantages:

• Slower edge lookup (than matrix)

Comparison Table

Feature	Adjacency Matrix	Adjacency List
Space Complexity	O(V²)	O(V + E)
Edge Lookup	O(1)	O(V)
Best for	Dense Graphs	Sparse Graphs
Ease of Iteration	Moderate	Easy
Memory Efficient	No	Yes

FAQs on Graph Representation

Q1. What is the most memory-efficient graph representation?

Adjacency List, especially for sparse graphs.

Q2. When to use adjacency matrix?

Use it for dense graphs or when you need fast edge lookup.

Q3. What is the time complexity to find an edge?

• Matrix: O(1)
• List: O(V)

Q4. Which is better: adjacency list or matrix?

It depends:

• Use adjacency list for fewer edges (sparse graphs)
• Use adjacency matrix for many edges (dense graphs)

Final Thoughts

Choosing the right graph representation depends on the problem’s nature—whether the graph is sparse or dense, directed or undirected, or weighted or unweighted.

Understanding both adjacency matrix and adjacency list gives you a strong foundation to solve graph-based problems efficiently in DSA, interviews, and real-world projects.