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

abtin
page 20: … protoc command… I had to additionally run the following go get commands in order to be able to compile protobuf code using go...
New
jimschubert
In Chapter 3, the source for index introduces Config on page 31, followed by more code including tests; Config isn’t introduced until pag...
New
iPaul
page 37 ANTLRInputStream input = new ANTLRInputStream(is); as of ANTLR 4 .8 should be: CharStream stream = CharStreams.fromStream(i...
New
johnp
Running the examples in chapter 5 c under pytest 5.4.1 causes an AttributeError: ‘module’ object has no attribute ‘config’. In particula...
New
raul
Hi Travis! Thank you for the cool book! :slight_smile: I made a list of issues and thought I could post them chapter by chapter. I’m rev...
New
adamwoolhether
When trying to generate the protobuf .go file, I receive this error: Unknown flag: --go_opt libprotoc 3.12.3 MacOS 11.3.1 Googling ...
New
patoncrispy
I’m new to Rust and am using this book to learn more as well as to feed my interest in game dev. I’ve just finished the flappy dragon exa...
New
akraut
The markup used to display the uploaded image results in a Phoenix.LiveView.HTMLTokenizer.ParseError error. lib/pento_web/live/product_l...
New
s2k
Hi all, currently I wonder how the Tailwind colours work (or don’t work). For example, in app/views/layouts/application.html.erb I have...
New
gorkaio
root_layout: {PentoWeb.LayoutView, :root}, This results in the following following error: no “root” html template defined for PentoWeb...
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
AstonJ
Or looking forward to? :nerd_face:
483 11078 254
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
Exadra37
Oh just spent so much time on this to discover now that RancherOS is in end of life but Rancher is refusing to mark the Github repo as su...
New
mafinar
Crystal recently reached version 1. I had been following it for awhile but never got to really learn it. Most languages I picked up out o...
New
PragmaticBookshelf
Author Spotlight Rebecca Skinner @RebeccaSkinner Welcome to our latest author spotlight, where we sit down with Rebecca Skinner, auth...
New
husaindevelop
Inside our android webview app, we are trying to paste the copied content from another app eg (notes) using navigator.clipboard.readtext ...
New
PragmaticBookshelf
Author Spotlight: Karl Stolley @karlstolley Logic! Rhetoric! Prag! Wow, what a combination. In this spotlight, we sit down with Karl ...
New
PragmaticBookshelf
Explore the power of Ash Framework by modeling and building the domain for a real-world web application. Rebecca Le @sevenseacat and ...
New
PragmaticBookshelf
A concise guide to MySQL 9 database administration, covering fundamental concepts, techniques, and best practices. Neil Smyth MySQL...
New

Sub Categories: