Graphs form an essential data structure used in various applications such as social networks, computer networks, transportation systems, and many more. In the context of data structures, graphs are mathematical structures used to model pairwise relations between objects. This chapter, an essential part of Unit 2 Notes Data Structures, will thoroughly explore the two primary graph representation techniques: adjacency matrix and adjacency list, which are extensively included in Engineering Study Material for B.Tech and BCA courses.
Introduction to Graphs
A graph is defined by two sets: a set of vertices (or nodes) and a set of edges connecting the vertices. Edges may be directed or undirected, depending on the nature of the relationship. A graph can be:
- Undirected: Edges have no direction.
- Directed: Edges have a direction. implies a connection from vertex to
- Weighted: Each edge has a weight or cost associated
- Unweighted: Edges do not carry any weight
To store and manipulate graphs, we use graph representation techniques. The two most popular methods are:
- Adjacency Matrix
- Adjacency List
These two methods allow programmers to implement graph-based algorithms such as DFS, BFS, Dijkstra’s, and Prim’s algorithm, which are crucial in solving real-world computational problems.
Adjacency Matrix Representation
The adjacency matrix is a 2D array of size , where is the number of vertices in the graph. Each element in the matrix indicates whether there is an edge from vertex to vertex .
- In an unweighted graph, the matrix contains binary values:
1for edge presence and0for absence. - In a weighted graph, the matrix contains the weight of the edge instead of
1.
Structure of Adjacency Matrix
Let us consider a graph with 4 vertices (0, 1, 2, 3):
📌 Insert Diagram: Graph with 4 vertices and directed edges
Let the edges be: (0→1), (0→3), (1→2), (2↓0)
The adjacency matrix will be:
0 1 2 3
0 [0 1 0 1]
1 [0 0 1 0]
2 [1 0 0 0]
3 [0 0 0 0]Properties
- For undirected graphs, the adjacency matrix is symmetric.
- The space complexity is , which is efficient only for dense graphs.
- Checking the existence of an edge takes time.
Advantages
- Simple and easy to implement
- Ideal for dense graphs where most of the possible edges are present
- Efficient edge look-up
Disadvantages
- Not space-efficient for sparse graphs
- Inserting or deleting a vertex requires rebuilding the entire matrix
Weighted Graph Example
0 1 2 3
0 [0 5 0 7]
1 [0 0 3 0]
2 [4 0 0 0]
3 [0 0 0 0]In this weighted matrix, the edge from 0 to 1 has a weight of 5, and so on.
Adjacency List Representation
The adjacency list is a more memory-efficient structure, especially for sparse graphs. In this representation, each vertex maintains a linked list or dynamic array of its adjacent vertices.
Structure of Adjacency List
Let us use the same example as before with 4 vertices and edges (0→1), (0→3), (1→2), (2↓0)
📌 Insert Diagram: Adjacency list representation of the graph
The adjacency list will look like:
0 → 1 → 3
1 → 2
2 → 0
3 → nullEach row indicates the vertex followed by its adjacent nodes.
Implementation
Typically implemented using:
- An array of lists (in C/C++: array of vectors or linked lists)
- Dictionary of lists in Python
Properties
- Space complexity is
- Time to check if an edge exists: , where is the degree of the vertex
- More suited for graphs with fewer edges
Advantages
- Highly space-efficient for sparse graphs
- Easy to add new edges and vertices
- Optimized for graph traversal
Disadvantages
- Checking for edge existence is slower than the adjacency matrix
- Less intuitive for matrix operations or dense graph modeling
Weighted Adjacency List
A weighted adjacency list stores pairs in the format: (vertex, weight)
0 → (1, 5) → (3, 7)
1 → (2, 3)
2 → (0, 4)
3 → nullComparison Table: Adjacency Matrix vs Adjacency List
| Feature | Adjacency Matrix | Adjacency List |
|---|---|---|
| Space Complexity | O(V^2) | O(V + E) |
| Edge Lookup | O(1) | O(k) |
| Suitable for | Dense Graphs | Sparse Graphs |
| Insert/Delete Vertex | Inefficient | Efficient |
| Insert/Delete Edge | O(1) | O(1) |
| Traversal | Faster for small graphs | More efficient for large graphs |
Practical Applications
- Adjacency matrices are used where edge density is high and fast look-up is required, such as circuit simulations or social network analysis with many connections.
- Adjacency lists are used in applications involving sparse connections, such as web crawlers, map routing systems, and AI pathfinding.
🔹 Short Answer Questions (2-3 Marks)
- What is an adjacency matrix?
An adjacency matrix is a 2D array that represents a graph by marking 1 or weight where edges exist and 0 otherwise. - What is an adjacency list?
An adjacency list is a collection of lists or arrays where each list corresponds to a vertex and stores its adjacent vertices. - Which graph representation is more space-efficient for sparse graphs?
The adjacency list is more space-efficient for sparse graphs. - What is the space complexity of an adjacency matrix?
The space complexity of an adjacency matrix is . - When is an adjacency matrix preferred over an adjacency list?
It is preferred when the graph is dense or frequent edge lookups are needed. - In an undirected graph, how is the adjacency matrix symmetric?
If there’s an edge between and , both and will be 1. - Write the adjacency list for a graph with edges: (0→1), (1→0), (2→3).
0 → 1, 1 → 0, 2 → 3, 3 → null
🔸 Long Answer Questions (5-10 Marks)
- Explain the adjacency matrix with an example. Also mention its advantages and disadvantages.
An adjacency matrix is a 2D array that shows edge presence between every pair of vertices. For a graph with vertices 0 to 3 and edges (0→1), (1→2), the matrix has 1s at respective positions. It is advantageous for dense graphs and fast edge lookup but is not space-efficient for sparse graphs due to its size. - Compare and contrast adjacency matrix and adjacency list with a table and examples.
The adjacency matrix and list differ in space complexity, edge lookup time, and efficiency for various graph types. A comparison table summarizes these differences along with examples showing their representations. - Describe how a weighted directed graph is stored using an adjacency list. Provide a code-friendly structure.
In a weighted directed graph, each vertex stores a list of tuples indicating the adjacent vertex and edge weight. For example,graph[0] = [(1, 5), (3, 7)]. This method is flexible and efficient for sparse weighted graphs. - Write an algorithm to convert an adjacency matrix to an adjacency list.
Iterate over each cell in the matrix. For everyA[i][j]that is not 0, addjto the adjacency list ofi. The resulting list represents the graph compactly and efficiently. - Why is the adjacency list preferred in modern applications like maps and social media graphs?
Modern applications often deal with sparse graphs where each node is only connected to a few others. The adjacency list saves memory and provides dynamic flexibility, making it suitable for such use cases.
📝 Chapter Summary
Graphs are used to represent relationships between entities adjacency matrix uses a 2D array for fixed-size edge storage adjacency list uses dynamic lists for each vertex adjacency matrix is good for dense graphs with fast edge lookups adjacency list is optimal for sparse graphs and efficient traversals adjacency matrix takes O(V^2) space and allows O(1) edge lookup adjacency list takes O(V+E) space and has O(k) lookup time weighted graphs store weights instead of 1s or 0s symmetric matrices indicate undirected graphs adding or deleting vertices is easier in adjacency list representation
📘 Model Paper / Sample Internal Exam Questions
- Explain the adjacency matrix representation of graphs with a neat diagram and example.
- Define adjacency list. Write its structure and advantages.
- Compare adjacency matrix and adjacency list. Which is better for sparse graphs?
- Convert the given adjacency matrix into an adjacency list and explain the process.
- Discuss the memory efficiency of adjacency matrix vs list with proper explanation.
