Editing 2407: Depth and Breadth

{{comic
| number    = 2407
| date      = January 4, 2021
| title     = Depth and Breadth
| image     = depth_and_breadth2.png
| titletext = A death-first search is when you lose your keys and travel to the depths of hell to find them, and then if they're not there you start checking your coat pockets.
}}

==Explanation==
{{w|Tree (data structure)|Tree structure}}s are one of the most common data structures used in computer science.  The common ways of enumerating items arranged in a tree is either {{w|Depth-first search|depth-first}}, or {{w|Breadth-first search|breadth-first}}, which are depicted accurately in the comic.  Randall humorously combines the words, to produce "brepth-first", "deadth-first", "bread-first", and "death-first" search algorithms.

Depth-first search explores down a full branch of the tree before working back to a higher level. This type of tree structure was already discussed as inefficient for human needs in [[761: DFS]]. The "opposite" of this is breadth-first search, which explores each level of the tree at a time.

In the "brepth-first" algorithm, a depth-first and a breadth-first search are hybridized where the left-most node is visited more frequently than the right node, but the right node is still visited.  This might be good for exploring data that is loosely but not strictly weighted to the left, or where data in deeper nodes needs some time to be loaded before it can be used. As implied by [[761: DFS]], this might be the best algorithm for a human to employ, where one can explore several topics briefly before deciding which one to explore more deeply, rather than blindly following the first rabbit hole to an absurd conclusion. Informed search algorithms like {{w|A* search algorithm|A* search}}, {{w|Beam search}}, and other {{w|Best-first search}} algorithms show this type of behavior by expanding the most ''promising'' node in the current set (under some appropriate metrics).

The nature of the "deadth-first" algorithm is unclear and inefficient, since it searches the same nodes multiple times before moving to an entirely different region of the tree.  It might be useful in a context where examining nodes has some probability of returning a noisy or incorrect result, such as searching for small objects that may be overlooked.

It may also be how people with OCD search, but this would be very stereotypical.

The bread-first search is taken literally.  Bread is searched for first.  Since the computer user now has already met their want to find bread, the computer has no reason to explore the tree at all.{{Citation needed}}

The title text introduces a "death-first" search, in which the user explores what it is like to be dead, before considering anything else. Specifically, the title text refers to hell, which calls to mind the adventures of Dante Alighieri in {{w|Inferno (Dante)| his ''Inferno''}}, and is a less likely place for keys to be left than one's coat pockets {{Citation needed}}. In 2021 (the year this comic was published) there are celebrations for the 700th anniversary of Dante's Death. Celebrations are expected to take place among the living only, and not in Hell.{{Citation needed}} A much more pleasant death-first algorithm might be to skip hell and purgatory and search heaven first, perhaps multiple times (which in itself would be a use of the deadth-first approach).

==Transcript==
:[Five panels, each containing identical copies of a rooted tree graph, grayed out in the background. The tree has a height of 3 and 15 nodes.]
:[In all five panels, a black twisty arrow in the foreground indicates the order in which nodes are traversed. The arrow does not complete the entire traversal but cuts off at some point. Backtracking is indicated with a dotted line.]
:[In the descriptions below, node 1 is the root, nodes 2 and 3 are its child nodes, nodes 4 and 5 are 2's child nodes, nodes 6 and 7 are 3's child nodes, nodes 8 and 9 are 4's child nodes, and so on up to node 15.]
:[Backtracking is omitted from the descriptions below, as they increased confusion when read.]

:Depth-first search
:[The arrow visits nodes 1, 2, 4, 8, 9, 5, 10, 11.]

:Breadth-first search
:[The arrow visits nodes 1, 2, 3, 4, 5, 7<sup>[''sic'']</sup>, 6, 8.]

:Brepth-first search
:[The arrow visits nodes 1, 2, 4, 5, 8, 9, 3, 6, 10, 11.]

:Deadth-first search
:[The arrow visits nodes 1, 2, 4, 4, 2, 4, 3, 6, 12, 13, 12.]

:Bread-first search
:[The arrow starts at node 1, then immediately leaves the tree off to the right to point to a small loaf labeled "Bread".]

{{comic discussion}}
[[Category:Programming]]
[[Category:Food]]