Grokking Algorithms

Chapter 6
 
 
I
 
 
Breadth-first search
Note that “shower” can be moved around, so this list is also valid:
1. Wake up.
2. Brush teeth.
3. Shower.
4. Eat breakfast.
6.3
For these three lists, mark whether each one is valid or invalid.
6.4
Here’s a larger graph. Make a valid list for this graph.
You could say that this list is sorted, in a way. If task A depends on 
task B, task A shows up later in the list. This is called a 
topological sort
, 
and it’s a way to make an ordered list out of a graph. Suppose you’re 
planning a wedding and have a large graph full of tasks to do—and 
you’re not sure where to start. You could
 topologically sort 
the graph
and get a list of tasks to do, in order.

---

113
Implementing the algorithm
Suppose you have a family tree.
This is a graph, because you have nodes (the people) and edges.
The edges point to the nodes’ parents. But all the edges go down—it 
wouldn’t make sense for a family tree to have an edge pointing back up! 
That would be meaningless—your dad can’t be your grandfather’s dad!
This is called a
 tree
. A tree is a special type of graph, where no edges 
ever point back. 
6.5
Which of the following graphs are also trees?

---

114
Chapter 6
 
 
I
 
 
Breadth-first search
Recap
• Breadth-first search tells you if there’s a path from A to B.
• If there’s a path, breadth-first search will find the shortest path.
• If you have a problem like “find the shortest X,” try modeling your 
problem as a graph, and use breadth-first search to solve.
• A directed graph has arrows, and the relationship follows the 
direction of the arrow (rama -> adit means “rama owes adit money”).
• Undirected graphs don’t have arrows, and the relationship goes both 
ways (ross - rachel means “ross dated rachel and rachel dated ross”).
• Queues are FIFO (First In, First Out).
• Stacks are LIFO (Last In, First Out).
• You need to check people in the order they were added to the search 
list, so the search list needs to be a queue. Otherwise, you won’t get 
the shortest path.
• Once you check someone, make sure you don’t check them again. 
Otherwise, you might end up in an infinite loop.

---

115
In this chapter
• We 
continue the discussion of graphs, and you 
learn about weighted graphs: a way to assign
more or less weight to some edges.
• You learn Dijkstra’s algorithm, which lets you
answer “What’s the shortest path to X?” for
weighted graphs.
• You learn about cycles in graphs, where
Dijkstra’s algorithm doesn’t work.