Graph Traversal BFS and DFS

This is the gateway to almost every algorithm you will meet in AI and computer science. BFS and DFS are the two fundamental ways to move through a graph, and nearly every graph algorithm you'll later encounter—finding shortest routes, detecting loops in dependency chains, ranking web pages, even how a large language model reasons over its knowledge—is built on top of one of these two patterns. You'll need them for understanding how agents search through possible steps, how a recommender system finds related items by hopping from one to the next, and how relational knowledge gets navigated in RAG. Master these, and later topics like Dijkstra's algorithm, topological sort, PageRank, and the graph-theoretic view of neural networks all become much easier

A graph is a collection of points (called vertices or nodes) connected by lines (called edges). Think of a map of cities with roads between them, or a social network where people are connected by friendships. Now, imagine you are standing at one city/node and want to explore everything reachable from it. There are two natural ways to do it.

Breadth-first search (BFS) works like ripples in a pond: you first visit all nodes that are one edge away, then all nodes that are two edges away, and so on. It expands outward, level by level, like checking every shop on the same street before moving to the next street.

Depth-first search (DFS) works like exploring a maze: you pick one path and follow it as deep as you can, until you hit a dead end, then you backtrack and try the next branch. It is like going down one corridor of a tunnel system, exploring every side tunnel off it, then coming back and trying the next corridor.

Both need a way to remember which nodes you've already visited, or you'll go around in circles forever on a graph with rings. A simple list of visited nodes, checked before you enter a node, prevents that infinite loop.

You are in a large house with many rooms connected by doors. You want to explore every room starting from the entrance.

BFS is like exploring with a group of friends: you all stand at the entrance, then each of you picks a different door, and you all step into those adjacent rooms together. Then, from each of those rooms, you all send people through the doors into the next layer of rooms, and so on. You never go two doors deep from the entrance until you've seen every room just one door away. This way, if you stop at any moment, you know you've seen all rooms within a certain distance from the start.

DFS is like exploring with a single rope tied to the entrance: you walk through a door, then another door, always choosing the first available door you haven't tried, going deeper and deeper. If you hit a room with no new doors, you walk back along the rope to the last room where you had an untried door, and go down that next corridor. You completely exhaust one corridor before trying the next.

Where the analogy breaks down: In a real house, you can see the whole room when you enter it, and you know all its doors. In a graph, you only discover a node's neighbours when you actually visit it. Also, in a physical house you can leave markers (string, chalk) to know you've been somewhere; a computer uses a 'visited' list for the same purpose. And while BFS's 'level' is like rooms at the same number of doors from the entrance, in a graph the same node can be reached at multiple distances—BFS records the first (shortest) distance it finds.

Graph traversal is the process of systematically visiting every vertex of a graph by following its edges; BFS visits all vertices at distance 1, then 2, then 3, etc., while DFS follows one path to its end before backtracking to try another.

You have not studied any other topics yet, so this page must build from absolute scratch. But know that once you have BFS and DFS, you can move on to topics like: Dijkstra's shortest path (which extends BFS to weighted edges), topological sorting (which uses DFS to order dependencies), PageRank (which can be computed using a form of traversal over the web graph), and social network analysis (which uses BFS to compute degrees of separation). Your library notes also mention that 'every binary relation is a directed graph', so these traversal patterns are the basis for reasoning about any relational data.