- 2071 Bhadra · 1+3 marks
Graph and its representations
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.
Define graph with its different representation techniques.
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.
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.
✓ Answer checked by Claude Opus 5.5 (high effort)