をちょっと考えてみます。まずいかにもアルゴリズムの教科書に載ってそうなグラフから。グラフの表現はとりあえずディクショナリを使って、

graph = {"a":["b","f"],"b":["a","c","e"],"c":["b","d","e","f"],
         "d":["c"],"e":["b","c","f"],"f":["a","c","e"]}

こんな感じで。ノードとそれに接続するノードのリストが要素。リストの左側のものが優先的に探索されます。ディクショナリまるごと渡したらジェネレータの利点がなくなるんじゃ、って感はありますが。

import copy
def graph_depth(node, graph):
    g = copy.deepcopy(graph)
    def graph_depth_inner(node):
        if node in g:
            yield node
            nodes = g.pop(node)
            for n in nodes:
                if n in g:
                    for i in graph_depth_inner(n):
                        yield i
    for n in graph_depth_inner(node):
        yield n

def graph_breadth(node, graph):
    g = copy.deepcopy(graph)
    def graph_breadth_inner(queue):
        q = []
        for n in queue:
            if n in g:
                yield n
                q += g.pop(n)
        if q:
            for n in graph_breadth_inner(q):
                yield n
    for n in graph_breadth_inner([node]):
        yield n

graph_depthが深さ優先、graph_breadthが幅優先。木を探索する場合にはノード、左部分木、右部分木とはっきり分割できるのでジェネレータを再帰的に呼び出すだけでいいのですが、グラフの場合はどこを探索したのかを覚えておく必要があります。ディクショナリをコピーしてそれを破壊しながら探索するのが楽。探索済みのノードはディクショナリから削除することで判定するようにします。それぞれの関数の内部で定義された**_innerが実際の探索を行います。

ノードaから深さ優先探索する場合、aを出力、graph-{"a"}をノードbから深さ優先探索、bを出力、graph-{"a","b"}をノードcから深さ優先探索...と再帰的にジェネレータを適用できます(graph-{"a"}はgraphからノードaを取り除いたグラフとします)。

>>> for t in graph_depth("a",graph):
    print t,

a b c d e f

>>> for t in graph_depth("c",graph):
    print t,

c b a f e d

幅優先の場合、探索を開始したノードから等しい高さ(辺数)にあるノードをひとまとめにして再帰。もっとスマートにできそうですが。

>>> for t in graph_breadth("a",graph):
    print t,

a b f c e d

>>> for t in graph_breadth("c",graph):
    print t,

c b d e f a

もう少し大きいグラフを

graph2 = {1:[2,5],2:[1,3,5],3:[2,4,9],4:[3,5],
          5:[1,2,4,6,7],6:[5,9],7:[5,8],8:[7],
          9:[3,6,10],10:[9,11],11:[10]}

深さ優先

>>> for t in graph_depth(1,graph2):
    print t,

1 2 3 4 5 6 9 10 11 7 8

>>> for t in graph_depth(9,graph2):
    print t,

9 3 2 1 5 4 6 7 8 10 11

幅優先

>>> for t in graph_breadth(1,graph2):
    print t,

1 2 5 3 4 6 7 9 8 10 11

>>> for t in graph_breadth(9,graph2):
    print t,

9 3 6 10 2 4 5 11 1 7 8

少しだけいじると

def graph_depth(node, graph):
    g = copy.deepcopy(graph)
    def graph_depth_inner(node):
        if node in g:
            yield node
            nodes = g.pop(node)
            for n in nodes:
                if n in g:
                    for i in graph_depth_inner(n):
                        yield i
                    yield node
    for n in graph_depth_inner(node):
        yield n

深さ優先で行って帰ってきたり、

>>> for t in graph_depth(1,graph2):
    print t,

1 2 3 4 5 6 9 10 11 10 9 6 5 7 8 7 5 4 3 2 1

>>> for t in graph_depth(9,graph2):
    print t,

9 3 2 1 5 4 5 6 5 7 8 7 5 1 2 3 9 10 11 10 9

def graph_breadth(node, graph):
    g = copy.deepcopy(graph)
    def graph_breadth_inner(queue):
        q = []
        for n in queue:
            if n in g:
                yield n
                q += g.pop(n)
        if q:
            yield "|"
            for n in graph_breadth_inner(q):
                yield n
    for n in graph_breadth_inner([node]):
        yield n

幅優先で同じ高さ(辺数)にあるノードを区切ったりできます。

>>> for t in graph_breadth(1,graph2):
    print t,

1 | 2 5 | 3 4 6 7 | 9 8 | 10 | 11 |

>>> for t in graph_breadth(9,graph2):
    print t,

9 | 3 6 10 | 2 4 5 11 | 1 7 | 8 |

次はグラフの各ノードをクラスとして、ノード間の距離も考えてみます。あんまり変わらなそうですが。