CH 06

Graph and hashing

Data Structures · GATE

Graph basicsGraph basics

A graph G = (V, E): V vertices, E edges. Directed or undirected, weighted or unweighted.
Sum of all degrees = 2E (handshaking lemma), so the number of odd-degree vertices is even.
Max edges: V(V − 1)/2 undirected, V(V − 1) directed.
A tree is a connected acyclic graph with V − 1 edges.

Graph G = (V, E): V vertices, E edges. Directed ya undirected, weighted ya unweighted.
Saari degrees ka sum = 2E (handshaking lemma), isliye odd-degree vertices ki ginti hamesha even hoti hai.
Max edges: undirected mein V(V − 1)/2, directed mein V(V − 1).
Tree ek connected acyclic graph hai jisme V − 1 edges hote hain.

RepresentationsRepresentations

	Adjacency matrix	Adjacency list
Space	O(V²)	O(V + E)
Check edge (u, v)	O(1)	O(degree of u)
List neighbours of u	O(V)	O(degree of u)
Best for	Dense graphs	Sparse graphs

BFS and DFSBFS aur DFS

	BFS	DFS
Uses	Queue	Stack / recursion
Time (adj. list)	O(V + E)	O(V + E)
Time (adj. matrix)	O(V²)	O(V²)
Finds	Shortest path in unweighted graphs	Cycles, topological order, components

TipIn BFS of an undirected graph there are no forward edges; in DFS of an undirected graph there are no cross edges.Undirected graph ke BFS mein forward edges nahi hote; undirected graph ke DFS mein cross edges nahi hote.

HashingHashing

A hash function maps a key to a slot in a table of size m, giving average O(1) search, insert and delete. Collisions (two keys in one slot) are handled by chaining or open addressing.Hash function ek key ko size m ki table ke ek slot pe map karta hai, jisse search, insert aur delete average O(1) mein hote hain. Collisions (do keys ek hi slot mein) ko chaining ya open addressing se handle karte hain.

Division method:  h(k) = k mod m      (choose m prime, not close to a power of 2)
Load factor:      α = n / m

Collision resolutionCollision resolution

Method	Probe sequence	Problem
Chaining	Linked list at each slot	Extra memory for pointers
Linear probing	h(k) + i	Primary clustering
Quadratic probing	h(k) + c₁i + c₂i²	Secondary clustering
Double hashing	h₁(k) + i·h₂(k)	None of the above (best spread)

Expected search cost (uniform hashing)Expected search cost (uniform hashing)

Method	Unsuccessful	Successful
Chaining	1 + α	1 + α/2
Open addressing	1 / (1 − α)	(1/α) ln(1 / (1 − α))

Common mistakeCommon galtiIn open addressing α must be < 1 (the table can fill up); in chaining α can be greater than 1.Open addressing mein α < 1 hona chahiye (table bhar sakti hai); chaining mein α 1 se zyada bhi ho sakta hai.

Quick revision

Adjacency matrix: O(V²) space, O(1) edge check. Adjacency list: O(V + E) space.
BFS and DFS both take O(V + E) with an adjacency list.
Undirected graph: max edges = V(V − 1) / 2.
Hashing: chaining has no clustering; linear probing causes primary clustering, quadratic probing causes secondary clustering.
Double hashing avoids both kinds of clustering.

Formulas & facts

Load factor α: n / m (keys / slots)
Chaining, unsuccessful search: 1 + α
Open addressing, unsuccessful search: 1 / (1 − α)
Division method: h(k) = k mod m

Done with this chapter? Now put it to use.Today's GATE question →