DSA TrainerFoundations · Unit 13
Graphs (BFS and DFS)
Some data is not a line or a tree, it is a web. Friends connected to friends. Cities linked by roads. Tasks that depend on other tasks. None of these fit neatly into an array or a single parent-child hierarchy, because anything can connect to anything, including back to where you started.
A graph is the structure for exactly this: a set of things (nodes) and the connections between them (edges). It is the most general of the structures in this course, and trees and linked lists are really just graphs with extra rules.
Once you can store a graph, the main thing you do with it is explore: start somewhere and visit connected nodes. There are two fundamental ways to do that, breadth-first and depth-first, and knowing when to use which is the heart of most graph problems. This unit covers the structure, how to store it, and those two ways of walking it.
You’re not signed in. Your progress here won’t be saved.
Nodes and edges
A graph is two things: nodes (also called vertices), which are the items, and edges, which are the connections between pairs of items. People are nodes, friendships are edges. Cities are nodes, roads are edges.
Edges can be undirected (the connection goes both ways, like a friendship) or directed (one way, like "follows" on social media, or "task A must finish before task B"). Unlike a tree, a graph has no required root and no limit on connections, and it can have cycles, paths that loop back to where they began.
In a graph, what is an edge?
The drills and graded test are premium
The lessons above are free. The interactive practice that turns recognizing the pattern into recalling it on a blank page unlocks with premium:
- ✓2 applied drills: train spotting when the concept applies
- ✓A 5-question graded test to clear the unit
- ✓The full guided problem ladder with faded hints, plus the cold-read capstone
From $6/month. Cancel anytime.