bfs(幅優先探索)のpythonでの実装

pythonでqueueを使いたいときは、listにappendとpop(0)を使えば良い。

あとはwikipediaにあるように

function 幅優先探索(v)
    Q ← 空のキュー
    v に訪問済みの印を付ける
    v を Q に追加
    while Q が空ではない do
        v ← Q から取り出す
        v を処理する
        for each v に接続している頂点 i do
            if i が未訪問 then
                i に訪問済みの印を付ける
                i を Q に追加

に従って実装する。