Editing 2407: Depth and Breadth
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.
The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision | Your text | ||
Line 8: | Line 8: | ||
==Explanation== | ==Explanation== | ||
+ | {{incomplete|Created by a LOAF OF DEATH. Please mention here why this explanation isn't complete. Do NOT delete this tag too soon.}} | ||
+ | |||
{{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. | {{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. | ||
Line 15: | Line 17: | ||
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. | 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. | ||
β | |||
β | |||
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 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}} | ||
Line 23: | Line 23: | ||
==Transcript== | ==Transcript== | ||
+ | {{incomplete transcript|Do NOT delete this tag too soon.}} | ||
+ | |||
:[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.] | :[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 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.] | ||
Line 41: | Line 43: | ||
:Bread-first search | :Bread-first search | ||
β | :[The arrow starts at node 1, then | + | :[The arrow starts at node 1, then leaves the tree off to the right to point to a loaf labeled "Bread".] |
{{comic discussion}} | {{comic discussion}} | ||
[[Category:Programming]] | [[Category:Programming]] | ||
[[Category:Food]] | [[Category:Food]] |