Head First Algorithms and Data Structures

Chapter 7. Graphs and Graph Traversal: Understanding Graphs

So far, we’ve worked with data structures like arrays, stacks, queues, lists, and hash tables. Each of these gives us a structured way to store and retrieve data, but they mostly focus on organizing individual items efficiently. Graphs introduce something different. Instead of just storing data, graphs focus on relationships between data. They let us model systems where each item can connect to many others—like social networks, road maps, or links between web pages. In this chapter, you’ll learn how graphs represent connections and how to explore them using two fundamental algorithms: Depth-first search (DFS) and Breadth-first search (BFS). These algorithms provide systematic ways to navigate networks, discover paths, and understand how connected systems are structured.

It’s all about relationships

Many real-world problems are more than just data points; they are also the relationships between data points. With these kinds of problems, instead of asking “what’s at this index?” or “what key maps to this value?”, we start asking questions about connections: who links to whom, how information flows, what paths exist, and which data items depend on which others, and how.

What kinds of problems? Think about cities, the internet, and social media. Cities are connected by winding roads. Websites link to thousands of other ...