Here's a quick investigation into depth-first and breadth-first search. The primary goal was to implement both algorithms recursively and non-recursively, an interesting exercise because of the relationship between recursion and the concept of a stack.

To aid this, I've built a very small Python library that can be used to build graphs. These graphs can then be searched using one of the four algorithms available in graphs.search.

Usage

Graphs

Instantiate an empty graph

>>> graph = graphs.Graph() 

Add a node

>>> graph.add('A')
>>> graph
{'A': set()}

Add another node and connect it

>>> graph.add('B')
>>> graph.connect('A', 'B')
>>> graph
{'A': {'B'}, 'B': {'A'}}

The graph is then traversable.

>>> graphs.search.breadth_first_search(graph)
['A', 'B']

Trees

Instantiate an empty tree

>>> tree = graphs.Tree()

Insert a node (note that the type is now important)

>>> node = graphs.Node('B')
>>> tree.insert(node)
>>> tree
{'B': set()}

The tree is then traversable.

>>> node = graphs.Node('A')
>>> tree.insert(node)
>>> graphs.search.breadth_first_search(tree)
['B', 'A']