Graphs and their representation

In short

A graph G = (V, E) is a set of vertices joined by edges, and it is the general data structure from which lists, trees and networks are special cases. Choosing its representation - adjacency matrix, adjacency list, edge list or CSR - decides the memory and the running time of every algorithm built on top of it, so representation is examined as heavily as the algorithms. GATE CS/DA tests graph terminology, degree and edge counting, matrix powers, traversal order and representation complexity almost every year; AICTE/CBCS "Data Structures" and "Design and Analysis of Algorithms" papers ask the representations with diagrams. In placement rounds (TCS NQT, Infosys, Amazon, Flipkart, Microsoft India, Zoho, Oracle, Samsung R&D) most medium-hard coding questions are graph questions in disguise - grids, dependencies, networks, friend suggestions.

Explained

Definitions and terminology

• Graph: G = (V, E), V a finite non-empty vertex set (|V| = n or V), E a set of vertex pairs (|E| = m or E). Order = n, size = m.
• Undirected edge {u, v} has no direction; directed edge (arc) (u, v) goes from tail u to head v. A digraph has only arcs.
• Adjacent / incident: u and v are adjacent if {u, v} ∈ E; the edge is incident on both vertices.
• Degree deg(v) = number of edges incident on v; a self-loop adds 2 to the degree. In a digraph, in-degree and out-degree are counted separately.
• Isolated vertex: degree 0. Pendant vertex: degree 1. Regular graph: every vertex has the same degree k (k-regular).
• Walk: any vertex-edge alternating sequence. Trail: no repeated edge. Path: no repeated vertex. Cycle (circuit): a closed path of length ≥ 3 (≥ 2 in a digraph, since a 2-cycle u→v→u is legal).
• Length of a path = number of edges (unweighted) or sum of weights (weighted).
• Connected graph: a path exists between every pair. Connected component: a maximal connected subgraph.
• Digraph connectivity: strongly connected (every u reaches every v), weakly connected (connected when directions are ignored), unilaterally connected (u reaches v or v reaches u).
• Subgraph: V' ⊆ V, E' ⊆ E. Spanning subgraph: V' = V. Induced subgraph: keeps every edge of E with both ends in V'.
• Bridge (cut-edge) and articulation point (cut-vertex): removal increases the number of components - the basis of network-reliability questions.
• Eccentricity of v = greatest distance from v; diameter = largest eccentricity; radius = smallest; girth = length of the shortest cycle.
• Clique: a complete subgraph. Independent set: no two vertices adjacent. Complement Ḡ: same vertices, edges exactly where G has none.

Types and classification

• Simple graph: no self-loops, no parallel edges. Multigraph: parallel edges allowed. Pseudograph: self-loops allowed too.
• Null graph (no edges), trivial graph (one vertex), complete graph Kₙ (every pair joined).
• Bipartite graph: V splits into two sets with every edge across; a graph is bipartite ⟺ it has no odd cycle ⟺ it is 2-colourable. Complete bipartite K_{m,n}.
• Weighted graph: each edge carries a cost, distance, capacity or probability. Weights may be negative in some digraphs (but a negative cycle makes shortest paths undefined).
• Tree: connected and acyclic, E = n − 1. Forest: acyclic, possibly disconnected. DAG: directed acyclic graph - dependencies, build systems, course prerequisites, Git history.
• Sparse vs dense: sparse when E = O(n) or O(n log n); dense when E approaches n². Real-world graphs (roads, social, web) are sparse - this single fact decides the representation.
• Planar graph: drawable without edge crossings; obeys Euler's formula and E ≤ 3n − 6 (n ≥ 3).
• Isomorphic graphs: a bijection of vertices preserving adjacency; same n, same E and same degree sequence are necessary but not sufficient.

Adjacency matrix

• An n × n matrix A with A[i][j] = 1 if edge (i, j) exists, else 0. For weighted graphs store the weight, with 0 or ∞ (a sentinel such as INT_MAX, or −1) for "no edge" - say which convention you use.
• Undirected ⇒ A is symmetric, so only the upper triangle is needed (n(n−1)/2 entries). A digraph's matrix is generally asymmetric.
• Row sum = out-degree, column sum = in-degree (undirected: both equal deg(i)). Diagonal entry = 0 in a simple graph; a self-loop is stored as 1 (digraph) or conventionally 2 (undirected degree counting) - state the convention in an exam.
• A multigraph stores the number of parallel edges in each cell.
• Powers: (Aᵏ)[i][j] = number of distinct walks of length exactly k from i to j. Hence the reachability (transitive closure) matrix via Warshall's algorithm in O(n³).
• Advantages: O(1) edge lookup, O(1) edge insert/delete, trivial to code, cache-friendly, bitset version is extremely fast for dense graphs and for Floyd-Warshall.
• Limitations: Θ(n²) space even for a graph with 5 edges; listing a vertex's neighbours costs O(n); whole-graph traversal costs O(n²); n = 10⁵ is impossible (10¹⁰ cells).

Adjacency list, edge list, incidence matrix and CSR

• Adjacency list: an array (size n) of lists; list[u] holds every neighbour of u (with weight, as a pair, if weighted). Space Θ(n + 2E) undirected, Θ(n + E) directed - the default for sparse graphs.
• Implementations: vector<vector<int>> or vector<vector<pair<int,int>>> in C++, ArrayList<List<Integer>> in Java, defaultdict(list) in Python, or classic singly linked lists in a C exam answer.
• Keep lists sorted for deterministic traversal order (needed when a question says "visit in increasing order"); sorting lets adjacency be tested in O(log deg(u)).
• Adjacency set / map: replace the list with a hash set, giving O(1) expected adjacency test while keeping O(n + E) space - the practical compromise; it loses the cheap neighbour ordering and adds constant-factor memory.
• Edge list: an array of (u, v, w) triples, Θ(E) space. Natural input format, and exactly what Kruskal's MST and Bellman-Ford consume; useless for "who are u's neighbours".
• Incidence matrix: n × E matrix; undirected entry 1 if vertex i is an endpoint of edge j; directed uses −1 at the tail and +1 at the head. Space Θ(nE) - examined in theory papers (each column has exactly two non-zeros), rarely used in code.
• CSR / compressed adjacency (forward-star): two flat arrays - head[0..n] offsets and adj[0..2E−1] targets, built with a counting sort of the edge list. Same information as an adjacency list with no pointers, best cache behaviour; used by real graph engines, GPU code and competitive programmers. CSC is the same thing on incoming edges.
• Implicit graph: never store it. In a grid/maze problem the neighbours of (r, c) are computed from direction arrays dr[] = {-1,0,1,0}, dc[] = {0,1,0,-1} - the correct answer to most matrix-island questions.
• Degree-ordered or renumbered vertices (map arbitrary string IDs to 0…n−1 with a hash map first) is standard practice before any array-based representation.

Traversals on a representation

• BFS: queue-based, visits by increasing number of edges. Mark on enqueue, not on dequeue, or vertices get queued many times. Gives shortest paths in an unweighted graph and a BFS tree whose non-tree edges join vertices whose levels differ by at most 1.
• Steps: enqueue source, dist = 0; repeatedly dequeue u, and for each unvisited neighbour v set dist[v] = dist[u] + 1, parent[v] = u, enqueue v.
• DFS: recursion or an explicit stack; goes deep first. Produces discovery/finish times and classifies edges as tree, back, forward and cross edges; a back edge to a grey (in-progress) vertex is exactly a cycle.
• Both are O(V + E) with adjacency lists and O(V²) with a matrix, and both need O(V) extra space (DFS recursion depth can reach V - a stack-overflow risk for a 10⁵-vertex path graph in C++ or Python; iterative DFS or sys.setrecursionlimit is the fix).
• Loop over all vertices as sources to cover a disconnected graph; the number of outer calls = number of components.
• Applications of DFS/BFS: connected components, cycle detection, bipartite check (2-colour by BFS level parity), topological sort (reverse DFS finish order), articulation points and bridges (Tarjan's low-link), SCC (Kosaraju's two passes / Tarjan), flood fill, shortest path in a maze, word-ladder and multi-source BFS, 0-1 BFS with a deque.
• Topological sort (DAG only): Kahn's algorithm - repeatedly output a vertex of in-degree 0 and decrement its successors. If fewer than n vertices are output, the digraph has a cycle. O(V + E).
• Weighted shortest paths: Dijkstra (non-negative weights) O((V + E) log V) with a binary heap and adjacency list, O(V²) with a matrix; Bellman-Ford O(VE) handles negative weights and detects negative cycles; Floyd-Warshall O(V³) on a matrix gives all pairs.
• MST: Prim O(E log V) with a heap and adjacency list (O(V²) with a matrix - better for dense graphs); Kruskal O(E log E) on an edge list with disjoint set union.

Choosing a representation, and syllabus notes

• Rule of thumb: adjacency list (or CSR) unless the graph is dense or you need constant-time edge queries. For n ≤ 1,000 a matrix is simpler and often faster; for n ≥ 10⁵ it is not an option.
• Dense-graph algorithms (Floyd-Warshall, O(V²) Dijkstra, Hungarian/assignment, bitset reachability) are written for matrices by design.
• GATE CS/DA lists graphs under "Programming and Data Structures" (graph representation) and "Algorithms" (traversals, MST, shortest paths); numerical questions almost always turn on counting edges/degrees, matrix powers, or the complexity of an operation under a stated representation.
• University labs (AICTE model curriculum, Data Structures lab) typically require: create a graph from an adjacency matrix and an adjacency list, convert one to the other, BFS, DFS, and detect connectivity - with the input read from a file, not hardcoded.

Key points

• Graph G = (V, E) - vertices plus edges; a tree is a connected acyclic graph with E = n − 1.
• Handshaking lemma - Σ deg(v) = 2E, so the number of odd-degree vertices is always even.
• Digraph degrees - Σ in-deg = Σ out-deg = E.
• Maximum edges - n(n−1)/2 in a simple undirected graph, n(n−1) in a simple digraph, mn in K_{m,n}.
• Adjacency matrix - Θ(V²) space, O(1) edge test, O(V) to list neighbours, symmetric for undirected graphs.
• Adjacency list - Θ(V + E) space, O(deg u) edge test, O(deg u) to list neighbours; the default for sparse graphs.
• Edge list - Θ(E) space; the input format for Kruskal and Bellman-Ford.
• Incidence matrix - Θ(V·E) space; exactly two non-zeros per column (±1 if directed).
• CSR - offsets + targets in two flat arrays; adjacency-list cost with better cache locality.
• Aᵏ[i][j] - the count of walks (not paths) of length exactly k from i to j; trace(A²) = 2E for a simple undirected graph.
• BFS - queue, O(V + E), shortest path in hops; mark vertices when enqueued.
• DFS - stack/recursion, O(V + E); a back edge means a cycle; reverse finish order is a topological order.
• Strong vs weak connectivity - only digraphs distinguish them; Kosaraju/Tarjan find SCCs in O(V + E).
• Bipartite ⟺ no odd cycle - checkable by 2-colouring during BFS.
• Density = 2E / (n(n−1)); real networks sit near 0.01% - which is why matrices waste memory.
• Disconnected bound - a simple graph on n vertices with more than (n−1)(n−2)/2 edges must be connected.
• Cayley's formula - Kₙ has nⁿ⁻² labelled spanning trees.
• Self-loops and parallel edges - allowed only in pseudo/multigraphs; they break "simple graph" formulas.

Formulas and examples

Example 1 - memory, matrix vs list vs CSR (sparse graph). An Indian road network model has n = 10,000 junctions and E = 50,000 undirected road segments (4-byte vertex ids, 8-byte pointers).

• Adjacency matrix, 1 byte per cell: 10,000² = 10⁸ bytes ≈ 100 MB; with 4-byte weights, 400 MB; as a bitset, 10⁸ bits = 12.5 MB.
• Adjacency list: 2E = 100,000 list nodes; each node = 4 (id) + 8 (next) = 12 bytes → 1,200,000 bytes, plus 10,000 × 8 = 80,000 bytes of head pointers ≈ 1.28 MB (allocator overhead makes it worse in practice).
• CSR: (10,000 + 1) × 4 = 40,004 bytes of offsets + 100,000 × 4 = 400,000 bytes of targets = 440,004 bytes ≈ 0.44 MB.
• Ratio matrix : CSR = 100 / 0.44 ≈ 227 ×. Density D = 2 × 50,000 / (10,000 × 9,999) = 100,000 / 99,990,000 ≈ 0.001 = 0.1 % - the matrix would be 99.9 % zeros.

Example 2 - degree counting. (a) A graph has degree sequence 3, 3, 3, 3, 2, 2, 2. Σ deg = 12 + 6 = 18, so E = 18/2 = 9 edges. (b) Can a simple graph have 5 vertices each of degree 3? Σ deg = 15, which is odd, so no - the handshaking lemma forbids an odd degree sum. (c) A 4-regular graph with 10 vertices: E = (10 × 4)/2 = 20 edges, against E_max = 10 × 9/2 = 45. (d) With n = 10, any simple graph having more than (9 × 8)/2 = 36 edges - i.e. 37 or more - is necessarily connected.

Example 3 - matrix powers. C₄ with edges 1-2, 2-3, 3-4, 4-1:

A²[1][1] = (0,1,0,1)·(0,1,0,1) = 2; A²[1][3] = (0,1,0,1)·(0,1,0,1) = 2; A²[1][2] = (0,1,0,1)·(1,0,1,0) = 0. So A² = [[2,0,2,0],[0,2,0,2],[2,0,2,0],[0,2,0,2]]. Reading it: 2 walks of length 2 from 1 to 3 (1-2-3 and 1-4-3), none of length 2 from 1 to 2 (odd/even parity - the graph is bipartite), and trace(A²) = 2 + 2 + 2 + 2 = 8 = 2E with E = 4. ✓

Example 4 - BFS and DFS trace. Undirected graph, neighbours stored in alphabetical order: A: B, C | B: A, D | C: A, D, E | D: B, C, F | E: C, F | F: D, E.

• BFS from A: visit order A, B, C, D, E, F; distances dist(A)=0, dist(B)=dist(C)=1, dist(D)=dist(E)=2, dist(F)=3 (F is reached from D or E, both at level 2). BFS tree edges: A-B, A-C, B-D (B is dequeued before C, so D is discovered from B), C-E, D-F.
• DFS from A: A → B → D → C → E → F, i.e. preorder A, B, D, C, E, F; F finishes first, then E, C, D, B, A, so the reverse finish order is A, B, D, C, E, F. Edge D-C is a tree edge while C-A is a back edge - proof of a cycle A-B-D-C-A.

Example 5 - Kahn's topological sort. DAG of prerequisites: 1→2, 1→3, 2→4, 3→4, 3→6, 4→5, 6→5. In-degrees: 1:0, 2:1, 3:1, 4:2, 5:2, 6:1.

1. Output 1 → in-deg(2)=0, in-deg(3)=0.
2. Output 2 → in-deg(4)=1. 3. Output 3 → in-deg(4)=0, in-deg(6)=0.
3. Output 4 → in-deg(5)=1. 5. Output 6 → in-deg(5)=0. 6. Output 5.

Order = 1, 2, 3, 4, 6, 5 (6 of 6 vertices output ⇒ acyclic). Adding edge 5→1 would leave every in-degree ≥ 1 after step 0, output 0 vertices, and so report a cycle.

Example 6 - which representation. Dijkstra on a Metro-style network with V = 10⁵, E = 2×10⁵: matrix version ≈ V² = 10¹⁰ basic steps (minutes to hours, and 10¹⁰ cells of memory - infeasible); heap + adjacency list ≈ (V + E) log₂V = 3×10⁵ × 16.6 ≈ 5×10⁶ steps (milliseconds).

// adjacency list (weighted, 0-indexed) and CSR build in C++
int n, m;  cin >> n >> m;
vector<vector<pair<int,int>>> adj(n);
vector<array<int,3>> edges(m);
for (auto &e : edges) {                       // read edge list once
    cin >> e[0] >> e[1] >> e[2];              // u, v, w
    adj[e[0]].push_back({e[1], e[2]});
    adj[e[1]].push_back({e[0], e[2]});        // drop this line for a digraph
}
vector<int> head(n + 1, 0), to(2 * m);        // CSR: counting sort of degrees
for (auto &e : edges) { head[e[0] + 1]++; head[e[1] + 1]++; }
for (int v = 0; v < n; ++v) head[v + 1] += head[v];
// fill 'to' using a copy of head as write cursors; neighbours of v are
// to[head[v] .. head[v+1]-1]

# BFS shortest hops on an adjacency list (dict of lists)
from collections import deque
def bfs(adj, src, n):
    dist, par = [-1] * n, [-1] * n
    dist[src] = 0
    q = deque([src])
    while q:
        u = q.popleft()
        for v in adj[u]:
            if dist[v] == -1:          # mark on enqueue
                dist[v], par[v] = dist[u] + 1, u
                q.append(v)
    return dist, par

Where it is used

• Maps and mobility: Google Maps, Ola, Uber, Rapido and Delhivery store road networks as CSR/adjacency lists and run Dijkstra/A* and contraction hierarchies over them; IRCTC and Indian Railways model stations and sections as weighted digraphs for routing and path availability.
• Social and commerce graphs: friend/follow suggestion and "people you may know" at LinkedIn, ShareChat and Meta India; co-purchase and recommendation graphs at Flipkart, Amazon India, Myntra and Swiggy.
• Payments and fraud: UPI/NPCI and bank transaction graphs are traversed for mule-account rings, cycles and community detection; KYC/Aadhaar de-duplication uses connected components over match graphs.
• Infrastructure and telecom: Grid-India (formerly POSOCO) grid topology and load-flow network models; Jio/Airtel fibre and cell-planning use spanning trees, cuts and max-flow; water and gas distribution networks in smart-city projects.
• Software engineering roles: compilers (control-flow and call graphs, register-allocation interference graphs), build tools and CI (DAG topological order), Spark/Airflow job DAGs, package dependency resolution, deadlock detection in DBMS wait-for graphs, Kubernetes service meshes.
• Interview and exam setting: SDE roles at product firms, GATE CS/DA, ISRO/BARC/DRDO scientist exams, and UGC-NET Computer Science all test graph representation and traversal directly.

Interview questions

• Q: When do you prefer an adjacency matrix over an adjacency list? A: When the graph is dense (E close to V²), V is small enough for V² memory, or the algorithm needs O(1) edge-existence tests - Floyd-Warshall, bitset reachability and O(V²) Dijkstra all assume a matrix.
• Q: What is the space and time cost of BFS under each representation? A: O(V + E) time with an adjacency list or CSR, O(V²) with a matrix because listing a vertex's neighbours costs O(V); extra space is O(V) for the queue and visited array in both cases.
• Q: How do you store an undirected graph in half the memory of a full matrix? A: It is symmetric, so keep only the upper triangle - n(n−1)/2 entries indexed by a triangular mapping, or use a bitset per row.
• Q: What does the (i, j) entry of A³ mean? A: The number of walks of length exactly 3 from i to j - walks, not paths, so vertices may repeat.
• Q: Can the sum of degrees of a graph be odd? A: No - it equals 2E, so it is always even, and the count of odd-degree vertices is therefore even.
• Q: How do you detect a cycle in a directed graph versus an undirected one? A: Directed: DFS with three colours and look for a back edge to a grey vertex, or run Kahn's algorithm and check that all V vertices come out. Undirected: DFS finding a visited neighbour that is not the parent, or union-find on the edge list.
• Q: Difference between strongly and weakly connected? A: Strongly connected means every vertex reaches every other along arc directions; weakly connected means the graph is connected only when the directions are dropped - meaningful only for digraphs.
• Q: Why is BFS, not DFS, used for shortest paths in an unweighted graph? A: BFS explores in non-decreasing order of hop count, so a vertex is first reached by a minimum-edge path; DFS can reach it by a long detour first.
• Q: How do you represent a graph whose vertices are strings, such as city names? A: Map each label to an integer 0…n−1 with a hash map (and keep the reverse array), then use any array-based representation - keeps O(1) indexing without string comparisons.
• Q: How is a 2-D grid or maze problem a graph problem? A: Each cell is an implicit vertex with up to four (or eight) neighbours computed from direction arrays; nothing is stored, and BFS over it gives the shortest route - this is the standard "islands"/"rotting oranges" pattern.
• Q: Your graph has 10⁵ vertices and 10⁵ edges and DFS crashes. Why? A: Recursive DFS can recurse to depth V on a path-like graph and overflow the stack; use an explicit stack (or raise the recursion limit and thread stack size).
• Q: What is CSR and why do production systems use it? A: Compressed sparse row - an offsets array plus a contiguous neighbour array. It holds the same information as an adjacency list with no pointer chasing, so it is smaller and much more cache-friendly; the cost is that edges cannot be inserted cheaply.

Common mistakes

• Quoting adjacency-list space as O(E) and forgetting the O(V) array of heads - a graph with 10⁶ isolated vertices still needs 10⁶ slots.
• Adding only one direction (adj[u].push_back(v)) for an undirected edge, or adding both for a directed one - the single most common silent bug.
• Marking a vertex visited on dequeue in BFS, so vertices enter the queue repeatedly and distances come out wrong.
• Treating Aᵏ entries as paths instead of walks, and counting self-loops as degree 1 instead of 2.
• Using 0 for "no edge" in a weighted matrix when zero-weight edges exist - use ∞/−1 and say so.
• Running a single BFS/DFS and declaring the graph traversed, when it is disconnected - loop over every unvisited vertex as a fresh source.
• Applying Dijkstra to negative weights, or topological sort to a graph that has a cycle, without checking the precondition.
• Writing an O(V²) matrix solution for V = 10⁵ in a coding round - it fails on memory before it fails on time.

Related topics

• Trees and binary search trees · Stacks and queues · Heaps and priority queues · Disjoint set union · Hashing and hash tables · Arrays and strings