« Seadragon and Zooming Interfaces | Home | Livejournal Has Massive Usability Problems »
Thinking in DFS vs BFS
By Jacob Cohen | May 14, 2007
The concepts of depth-first search (DFS) and breadth-first search (BFS) are usually used to describe an algorithm for visiting nodes in a graph or a tree structure. The key difference is whether you visit all of the nodes nearest to you first, then begin radiating outward from there, or whether you continue as deep as possible along a given path first, and backtrack only when you can continue no deeper.
A thought process can be represented as a sort of graph. If you think of one thing, and that brings to mind something else, it is like forming an edge between the two nodes that represent the different thoughts.
If thoughts are like a graph, then what is the difference between a depth-first search and a breadth-first search between thoughts and memories? Depth-first search is what happens when you make several intuitive leaps from one thought to another. For example, if someone says, “I need to go get this film developed,” and you pick up on the word “developed,” you might then think “developer,” which could lead to the famous Steve Ballmer “Developers, Developers, Developers” video, which makes you think of Microsoft, which makes you think of Bill Gates, and finally you say “hey I heard the Bill and Melinda Gates Foundation donated a lot of computers and money to the computer science program at Stanford.” Then you’d get a strange look because you were supposed to be talking about cameras and film. This is depth-first search in the human thought process.
What about breadth-first search? This is thinking about an idea and coming up with a list of all the thoughts it triggers. You have to be careful not to follow down the path of any of these thoughts, or you’ve begun depth-first search. In the example above, if someone mentioned getting film developed, you might think of camera stores, or film developing solution, or remembering to rewind a camera before taking the film out, or the difference between 24 and 36 exposure rolls.
How often have you thought of a bookmark you had as being “near the bottom” of your bookmarks list, and when you’ve added enough bookmarks that this is no longer true, that bookmark becomes much harder to find? Mentally, that bookmark’s value was secondary to the notion that it was “near the bottom” of the list. It has forced a DFS traversal on what is meant to be a breadth of information.
There are many applications that choose their own convention for where to access their options and settings. For example, in most Microsoft applications, the Options dialog is found in the Tools menu. In Photoshop, you find Preferences in the Edit menu. In Wordpad, you find Options under the View menu. But how do you find it if you don’t remember where it is? You search menu by menu looking for it, which is essentially a BFS traversal of the menu tree.
So what does this mean for interface design? It means that as we become accustomed to using an interface, our memory on how to do various things can be triggered by familiar UI elements. This causes us to make the mental leap to the process by which we accomplish whatever we’re trying to do. We remember processes and UI habits in terms of DFS, but we learn them by experimenting in BFS fashion.
July 15th, 2008 at 12:29 pm
I think traversing a menu then a menu searching for a certain menu item is DFS as u search for the menu item at the first menu and continue comparing each menu item in this menu with the menu item u are searching for, if u didn’t find it, u start moving to the neighbor menu.
I just guess so and I hope u correct me if there is something wrong.
Ahmed.