111
Implementing the algorithm
Try running this code yourself. Maybe try changing the
person_is_
seller
function
to something more meaningful, and see if it prints
what you expect.
Running time
If you search your entire network for a mango seller, that means you’ll
follow each edge (remember, an edge is the
arrow or connection from
one person to another). So the running time is at least O(number of
edges).
You also keep a queue of every person to search. Adding one person to
the queue takes constant time: O(1). Doing this for every person will
take O(number of people) total. Breadth-first search takes O(number of
people + number of edges), and it’s more commonly written as O(V+E)
(V
for number of vertices, E for number of edges).
EXERCISE
Here’s a small graph of my morning routine.
It tells you that I can’t eat breakfast until I’ve brushed my teeth. So “eat
breakfast”
depends on
“brush teeth”.
On the other hand, showering doesn’t depend on brushing my teeth,
because I can shower before I brush my teeth.
From this graph, you can
make a list of the order in which I need to do my morning routine:
1. Wake up.
2. Shower.
3. Brush teeth.
4. Eat breakfast.