ここからは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という四つのページがあったとして、次の表のように各ページがリンクを持つとします。
ページ | リンク |
---|---|
A | B, C |
B | A, D |
C | D |
D | C, A |
各ページを訪問していく際に、これから訪問するページのリスト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
- 頂点に対して隣接する頂点の集合を返す関数
- 出力
- 訪問したページのリスト
- 手順
-
Visit
にa
を挿入する。 -
Visit
が空またはVisited
の要素数がn
ならばVisited
を出力して終了する。 -
Visit
から頂点v
を取り出す。 - 頂点
v
がVisited
に含まれていれば、手順2にジャンプする。 -
T(v)
の頂点のうち、Visited
に含まれないものをVisit
に挿入する。 -
v
をVisited
に挿入する。 - 手順2にジャンプする。
-
次の章ではこのアルゴリズムをRustで実装していきます。