Graphs: Representation, BFS and DFS Traversal For students.

A graph is a set of vertices (nodes) connected by edges. Vertices can be cities, people, or web pages; edges can be roads, friendships, or links. Unlike trees, graphs have no root and no parent-child rule, and they can contain cycles — paths looping back to the start. A metro map is a graph you have already read.

Graphs matter because so much of the world is a network. Map apps route on road graphs, social networks suggest friends on people graphs, and the internet routes packets on a router graph. The two fundamental ways to explore a graph — breadth-first search (BFS) and depth-first search (DFS) — begin nearly every graph algorithm.

Key Concepts

• Vertex / edge: one entity (a city) and one connection (a road) in the graph.
• Directed vs undirected: edges with arrows (one-way streets) versus edges going both ways.
• Degree: edges touching a vertex; the handshake lemma says the sum of all degrees = 2E.
• Adjacency matrix: a V × V table marking edges — O(1) lookup but O(V²) memory.
• Adjacency list: each vertex lists its neighbours — O(V + E) memory, the standard choice.
• BFS: explores level by level with a queue — all neighbours of the start before going deeper.
• DFS: plunges down one path with a stack (or recursion), then backtracks.

Formulas

• Handshake lemma: sum of degrees = 2E. Five edges give total degree 10.
• Maximum edges (undirected): V(V − 1)/2. Six vertices allow 15 edges; directed graphs allow V(V − 1) = 30.
• BFS/DFS time: O(V + E) with an adjacency list — each vertex and edge processed once.
• BFS shortest path: in an unweighted graph, the first time BFS reaches a target is via the shortest path.
• Space: O(V) for the visited set plus the queue (BFS) or recursion stack (DFS).

Worked Example

Graph: vertices A, B, C, D, E with edges A–B, A–C, B–D, C–D, D–E. BFS from A: visit A; enqueue neighbours B, C; visit B, then C; from B discover D (enqueue it); from C nothing new; visit D, discover E; visit E. Order: A, B, C, D, E — and E is reached in 3 hops (A→B→D→E), the shortest path. DFS from A (alphabetical neighbours): visit A → B → D → C (B's neighbour D first, then D's neighbour C); backtrack; from D go to E. Order: A, B, D, C, E. Same vertices, different order: BFS spreads like ripples, DFS dives like a submarine.

Common Misconceptions

• "BFS and DFS visit in the same order." Wrong — the example gives A,B,C,D,E versus A,B,D,C,E.
• "DFS finds shortest paths." Wrong in general. Only BFS guarantees that, and only in unweighted graphs; weighted graphs need Dijkstra's algorithm.
• "Adjacency matrices are always better." Wrong for sparse graphs — a billion-user social network would need a 10^18-entry matrix, while the adjacency list stays tiny.

Real-World Applications

• BFS: shortest routes in unweighted networks, degrees of separation, web crawlers.
• DFS: maze solving, topological sorting of dependencies, cycle detection, Sudoku solvers.
• Graphs generally: GPS navigation, flight planning, network routing, recommendation engines.

BFS fans out in waves and finds shortest paths; DFS dives deep and untangles dependencies and cycles. Trace both by hand, and the famous algorithms built on them — Dijkstra, topological sort, connected components — become natural next steps.