---
title: "Graph and its representations"
subject: "Data Structure and Algorithm"
chapter: 10
key: "semester_4/data_structure_and_algorithm:graph-define-representation"
source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/graph-define-representation
site: BCT Engineering
---

# Graph and its representations

Data Structure and Algorithm · Chapter 10: Graphs

- Asked in: 2071 Bhadra, 1+3 marks
- Video: [6.1 Graph Representation in Data Structure(Graph Theory)|Adjacency Matrix and Adjacency List](https://www.youtube.com/watch?v=5hPfm_uqXmw) — Jenny's Lectures CS IT
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/graph-define-representation
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-10

## Question

Define graph with its different representation techniques.

## Short answer

A graph G=(V,E) consists of vertices and edges connecting pairs. Representations include adjacency matrix (O(V²) space, O(1) edge test), adjacency list (O(V+E) space, good for sparse graphs), and incidence matrix.

## Answer

A **graph** G = (V, E) is a set V of vertices (nodes) and a set E of edges connecting pairs of vertices. It can be directed (edges have direction) or undirected, and weighted or unweighted.

#### Representations
Example graph: V = {1, 2, 3, 4}, edges 1-2, 1-3, 2-4, 3-4.

**1. Adjacency matrix:** an n × n matrix with A[i][j] = 1 (or the edge weight) if an edge from i to j exists, else 0.

| | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 1 | 0 | 1 | 1 | 0 |
| 2 | 1 | 0 | 0 | 1 |
| 3 | 1 | 0 | 0 | 1 |
| 4 | 0 | 1 | 1 | 0 |

Space O(V²); edge test O(1); good for dense graphs.

**2. Adjacency list:** for each vertex, a linked list of its neighbours.
```text
1 -> 2 -> 3
2 -> 1 -> 4
3 -> 1 -> 4
4 -> 2 -> 3
```
Space O(V + E); good for sparse graphs; edge test takes O(degree).

**3. Incidence matrix:** a V × E matrix in which entry [v][e] = 1 if vertex v is an end of edge e, else 0. It is used less often.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. A graph G = (V, E) consists of what?
   A. A set of vertices with no connections
   B. A set of vertices and a set of edges joining pairs of them
   C. Only a set of edges
   D. A tree plus extra vertices
   Answer: B. A graph is a vertex set V with an edge set E connecting pairs of vertices. (Key point: Graph definition)

2. For an adjacency matrix of n vertices, what are its size and edge-test cost?
   A. E x E; O(n) edge test
   B. n x n; O(1) edge test
   C. n x E; O(1) edge test
   D. n x n; O(degree) edge test
   Answer: B. It is n x n with direct lookup A[i][j], so edge test is O(1), but space is O(V^2). (Key point: Adjacency matrix)

3. Which graphs suit an adjacency list best, and why?
   A. Dense graphs, since edge test is O(1)
   B. Sparse graphs, since space is O(V+E)
   C. Only directed graphs
   D. Dense graphs, since space is O(V^2)
   Answer: B. The list stores only existing edges, so it uses O(V+E) space, ideal for sparse graphs. (Key point: Adjacency list)

4. What are the dimensions of an incidence matrix?
   A. V x log V
   B. V x V
   C. V x E
   D. E x E
   Answer: C. Rows are vertices, columns are edges, with 1 where a vertex is an end of an edge. (Key point: Incidence matrix)