幅優先探索について

ここからはmini-crawlerの核となるアルゴリズムである幅優先探索を実装します。この章ではグラフ探索の手法として、幅優先探索との比較のために深さ優先探索を紹介してから幅優先探索を紹介します。

幅優先探索についてよく知っている方はこの章を飛ばしてもかまいません。

これまでに実装したLinkExtractorを使って抽出したリンクをたどっていきたいのですが、取得したリンクを訪れる方法を考えておく必要があります。例えば、ページAにページBへのリンクがあったとして、さらにページBにもページAへのリンクがあったとします。このとき、ページAからページBを訪れてページBから再びページAを訪れるということが起こります。そうするとまたページAからページBを訪れることになり、無限ループに陥ってしまいます。そこで、すでに訪れたページを記憶しておく必要があります。

また、リンクを訪れる順番にも気を付ける必要があります。ページAにページB1, B2, ..., Bnへのリンクがあったとします。このときページB1を訪れて、ページB1にはページC1, C2, ..., Cmへのリンクがあったとします。次にページC1を訪れて、同様にページC1のリンクを訪れていくとします。このような方法でページをたどっていくと、リンクを持たないページを訪れない限り最初のページAにあった他のリンクを訪れることはありません。このたどり方のことを深さ優先探索と言います。具体例を使ってもう少しわかりやすく説明します。

深さ優先探索

A, B, C, Dという四つのページがあったとして、次の表のように各ページがリンクを持つとします。

各ページを訪問していく際に、これから訪問するページのリストVisitと訪問済みのページのリストVisitedを保持します。

ページAからスタートして深さ優先探索をしていきます。

まず、ページAのリンクを取得してリストVisitに入れます。また、ページAは訪問したのでリストVisitedに入れます。

Visit = [B, C]
Visited = [A]

次に、Visitの一番後ろにあるページCを訪れたいと思います。ページCをVisitから取り出してから、先ほどと同様にページCのリンクを取得してリストVisitに入れ、ページCをリストVisitedに入れます。ただし、訪問済みリストVisitにすでに入っているページはVisitには入れないようにします。

Visit = [B, D]
Visited = [A, C]

今度はページDを訪れます。すると、リストVisitとVisitedは次のようになります。

Visit = [B]
Visited = [A, C, D]

最後にページBを訪れれば二つのリストは次のようになります。これで全てのページを訪問しました。

Visit = []
Visited = [A, C, D, B]

深さ優先探索でページを訪れていくと、最初に訪れたページAから飛べるページBよりも先に、ページAからは直接に開けないページDの方を先に訪れることになりました。

ウェブページの場合、リンクを持たないページは滅多にないと考えられます。なので深さ優先探索では満遍なくページを訪れることはできないと思われます。全てのページを訪れることができれば問題ないのですが、ウェブページは無数にあるので訪れるページ数に制限をつける必要があります。訪れるページ数に制限があるのであれば、なるべく最初に訪れたページに近いページから収集したいというのは自然な要望でしょう。そこで必要になるのが幅優先探索というアルゴリズムです。

幅優先探索では深さ優先探索とは異なり、ページAからページB1を訪れた後にページB2を訪れるようにします。同様にして取得したリンクを取得した順に訪れていきます。こうすることで最初に訪れたページから近い順に探索することができます。

幅優先探索

前節と同じ例で幅優先探索を実行してみます。深さ優先探索と異なる点は、Visitからページを取り出すときにリストの一番前から取り出すようにすることです。

最初にページAを訪れます。ページAのリンクをリストVisitに入れて、ページAをリストVisitedに入れます。

Visit = [B, C]
Visited = [A]

次に訪れるページはBです。ページBのリンクのうち、Visitedに含まれないものをVisitに入れて、ページBをVisitedに入れます。

Visit = [C, D]
Visited = [A, B]

ページCを訪問します。先程と同様の手順を実行します。

Visit = [D, D]
Visited = [A, B, C]

ページDを訪問します。VisitとVisitedは次のようになります。

Visit = [D]
Visited = [A, B, C, D]

最後にVisitに残ったページDはすでに訪問済みなので訪問しません。これで全てのページを訪問しました。訪問した順序はページAに近い順になっています。

アルゴリズム

探索の対象をグラフとして抽象化した上で幅優先探索のアルゴリズムを定義します。また、グラフの隣接関係がわかれば十分なので、入力としては頂点vに隣接する頂点を返す関数T(v)を受け取ることとします。

訪問する頂点を記憶するVisitにはキューを使います。RustではVecDequeにあたります。訪問済みの頂点を記憶するVisitedにはハッシュを使います。RustではHashSetにあたります。

• 入力
  • 頂点に対して隣接する頂点の集合を返す関数T
  • 探索を始める頂点a
  • 訪問するページ数の上限n
• 出力
  • 訪問したページのリスト
• 手順
  1. Visitにaを挿入する。
  2. Visitが空またはVisitedの要素数がnならばVisitedを出力して終了する。
  3. Visitから頂点vを取り出す。
  4. 頂点vがVisitedに含まれていれば、手順2にジャンプする。
  5. T(v)の頂点のうち、Visitedに含まれないものをVisitに挿入する。
  6. vをVisitedに挿入する。
  7. 手順2にジャンプする。

次の章ではこのアルゴリズムをRustで実装していきます。