jygh

jygh

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.

Where Next?

Popular Pragmatic Bookshelf topics Top

brianokken
Many tasks_proj/tests directories exist in chapters 2, 3, 5 that have tests that use the custom markers smoke and get, which are not decl...
New
sdmoralesma
Title: Web Development with Clojure, Third Edition - migrations/create not working: p159 When I execute the command: user=> (create-...
New
lirux
Hi Jamis, I think there’s an issue with a test on chapter 6. I own the ebook, version P1.0 Feb. 2019. This test doesn’t pass for me: ...
New
conradwt
First, the code resources: Page 237: rumbl_umbrella/apps/rumbl/mix.exs Note: That this file is missing. Page 238: rumbl_umbrella/app...
New
brunogirin
When installing Cards as an editable package, I get the following error: ERROR: File “setup.py” not found. Directory cannot be installe...
New
taguniversalmachine
It seems the second code snippet is missing the code to set the current_user: current_user: Accounts.get_user_by_session_token(session["...
New
tkhobbes
After some hassle, I was able to finally run bin/setup, now I have started the rails server but I get this error message right when I vis...
New
dtonhofer
@parrt In the context of Chapter 4.3, the grammar Java.g4, meant to parse Java 6 compilation units, no longer passes ANTLR (currently 4....
New
New
dachristenson
I just bought this book to learn about Android development, and I’m already running into a major issue in Ch. 1, p. 20: “Update activity...
New

Other popular topics Top

ohm
Which, if any, games do you play? On what platform? I just bought (and completed) Minecraft Dungeons for my Nintendo Switch. Other than ...
New
wolf4earth
@AstonJ prompted me to open this topic after I mentioned in the lockdown thread how I started to do a lot more for my fitness. https://f...
New
axelson
I’ve been really enjoying obsidian.md: It is very snappy (even though it is based on Electron). I love that it is all local by defaul...
New
AstonJ
Or looking forward to? :nerd_face:
483 11975 256
New
dasdom
No chair. I have a standing desk. This post was split into a dedicated thread from our thread about chairs :slight_smile:
New
AstonJ
Curious to know which languages and frameworks you’re all thinking about learning next :upside_down_face: Perhaps if there’s enough peop...
New
AstonJ
You might be thinking we should just ask who’s not using VSCode :joy: however there are some new additions in the space that might give V...
New
mafinar
This is going to be a long an frequently posted thread. While talking to a friend of mine who has taken data structure and algorithm cou...
New
PragmaticBookshelf
Author Spotlight: Karl Stolley @karlstolley Logic! Rhetoric! Prag! Wow, what a combination. In this spotlight, we sit down with Karl ...
New
RobertRichards
Hair Salon Games for Girls Fun Girls Hair Saloon game is mainly developed for kids. This game allows users to select virtual avatars to ...
New

Sub Categories: