A Common-Sense Guide to Data Structures and Algorithms in Python, Volume 1: Chapter 18 search/traversal terminology (pages 348)

A Common-Sense Guide to Data Structures and Algorithms in Python, Volume 1: Chapter 18 search/traversal terminology (pages 348)

@jaywengrow

The search versus traversal terminology leads to a potential continuity quirk.

On page 339 the text points out–in two places–that search can be used to find a specific vertex or to traverse the graph. Searching and traversing are used interchangeably, such as in the following:

Code Implementation: Depth-First Search

Here is an implementation of depth-first traversal:

def dfs_traverse(vertex, visited_vertices):

In the Breadth-First section (page 348), however, it’s a bit quirky (emphasis mine):

Breadth-First Search

Breadth-first search, often abbreviated BFS, is another way to search a graph. Unlike depth-first search, breadth-first search does not use recursion. Instead, the algorithm revolves around our old friend, the queue. As you’ll recall, the queue is a FIFO data structure, and whatever goes in first, comes out first.

Here is the algorithm for breadth-first search. As with our walkthrough of depth-first search, we’re going to focus on graph traversal using breadth-first search. That is, we’re going to visit each vertex from our example social network.

Here is the algorithm for breadth-first traversal:

Notice the repeated “Here is the algorithm” phrase. Although it’s been established that search and traversal are very nearly synonymous it still reads a bit strangely. In part this follows from setting up Exercise 4 in the chapter where the user is asked to implement the search functionality for Breadth-First Search.

One way around this might be to simply remove the first “Here is the algorithm” sentence–or to alter the wording slightly to remove the repetition. This is judgment call, and a fairly nit-picky one at that, so adopt/adapt/ignore as you see fit.