Chapter 18

These are the solutions to the exercises found in the section .

1. If a user is browsing “nails”, the website will recommend “nail polish”, “needles”, “pins”, and “hammer”.

2. The order of depth-first search would be A-B-E-J-F-O-C-G-K-D-H-L-M-I-N-P, as seen in the following image:

   

3. The order of breadth-first search would be A-B-C-D-E-F-G-H-I-J-K-L-M-N-O-P, as seen in the following image:

   

4. Following is an implementation of breadth-first search:

   ​	​import​ ​queue_implementation​
   ​
   ​
   ​	​def​ ​bfs​(starting_vertex, search_value):
   ​	queue = queue_implementation.Queue()
   ​	visited_vertices = {}
   ​	visited_vertices[starting_vertex.value] = True
   ​	queue.enqueue(starting_vertex)
   ​
   ​	​while​ queue.read():
   ​	current_vertex = queue.dequeue()
   ​	​if​ current_vertex.value == search_value:
   ​	​return​ current_vertex
   ​
   ​	​for​ adjacent_vertex ​in​ current_vertex.adjacent_vertices:
   ​
   ​	​if​ ​not​ visited_vertices.get(adjacent_vertex.value):
   ​	visited_vertices[adjacent_vertex.value] = True
   ​	queue.enqueue(adjacent_vertex)
   ​
   ​	​return​ None

5. To find the shortest path in an unweighted graph, we’re going to use breadth-first search. The main feature of breadth-first search is that it stays close to the starting vertex as long as possible. This feature will serve as the key to finding the shortest path.

   Let’s apply this to our social-networking example. Because breadth-first search stays close to Idris as long as possible, we’ll end up finding Lina first through the shortest possible path. Only later on in the search would we end up finding Lina through longer paths. In fact, we can even stop the search as soon we as find Lina. (Our implementation that follows doesn’t end early, but you can modify it to do so.)

   As we visit each vertex for the first time, then, we know that the current vertex is always part of the shortest path from the starting vertex to the vertex we’re visiting. (Remember, with BFS, the current vertex and the vertex we’re visiting aren’t necessarily the same.)

   For example, when we visit Lina for the first time, Kamil will be the current vertex. This is because in BFS, we’ll get to Lisa first through Kamil before we get to her through Sasha. When we do visit Lina (through Kamil), we can store in a table that the shortest path from Idris to Lina will be through Kamil. This table is similar to the cheapest_previous_stopover_city_table from Dijkstra’s algorithm.

   In fact, whenever we visit any vertex, the shortest path from Idris to that vertex will be through the current vertex. We’ll store all of this data in a table called previous_vertex_table.

   Finally, we can then use this data to work backward from Lina to Idris to build the precise shortest path between the two of them.

   Here’s our implementation:

   ​	​import​ ​queue_implementation​
   ​
   ​
   ​	​def​ ​shortest_path​(first_vertex, second_vertex, visited_vertices):
   ​	queue = queue_implementation.Queue()
   ​	previous_vertex_table = {}
   ​
   ​	visited_vertices[first_vertex.value] = True
   ​	queue.enqueue(first_vertex)
   ​
   ​	​while​ queue.read():
   ​	current_vertex = queue.dequeue()
   ​
   ​	​for​ adjacent_vertex ​in​ current_vertex.adjacent_vertices:
   ​	​if​ ​not​ visited_vertices.get(adjacent_vertex.value):
   ​	visited_vertices[adjacent_vertex.value] = True
   ​	queue.enqueue(adjacent_vertex)
   ​	previous_vertex_table[adjacent_vertex.value] = \
   ​	current_vertex.value
   ​
   ​	shortest_path = []
   ​	current_vertex_value = second_vertex.value
   ​
   ​	​while​ current_vertex_value != first_vertex.value:
   ​	shortest_path.insert(0, current_vertex_value)
   ​	current_vertex_value = \
   ​	previous_vertex_table.get(current_vertex_value)
   ​
   ​	shortest_path.insert(0, first_vertex.value)
   ​
   ​	​return​ shortest_path