【データ構造】「木とグラフ・探索アルゴリズム」をわかりやすく解説

こんにちは。タクマ™ [@suwaru_blog] です。

ぶっちゃけ、木とグラフの問題は面倒くさいです。
だからこそエンジニア面談、競技プログラミングでは多く出題されています。

木の種類

木とは、連結グラフの一種であり、ノードで構成されるデータ構造です。
木の学習では、以下のことを意識しましょう。

つづいて、木の特徴を挙げます。

// シンプルな Node クラス定義
class Node {
    public String name;
    public Node[] children;
}

// Node をラップする Tree クラスを定義してもよい
class Tree {
    public Node root;
}

二分木 (Binary Tree) とは

二分木とは、各ノードが最大 2 個の個しか持たない木です。
すべての木が二分木というわけではありません。

たとえば、以下の木は「三分木」といえます。

二分木ではない木を使う場合は多々あります。

たとえば、たくさんの電話番号を木で表現してみましょう。
各ノードは (それぞれ 1 桁分を意味する) 最大 10 個の子ノードの 10 分木を使うことになります。

葉ノードとは

子ノードを持たないノードは「葉ノード」と呼ばれます。

二分探索木 (BST) とは

二分探索木とは、すべてのノードが特定の並び順になっている二分木のことです。
特定の並び順とは すべての左の子孫 <= n <= すべての右の子孫 を意味します。

この不等式は「各ノード直下の子だけではなく、すべての子孫で成り立っていないといけない」という点に注意してください。

上記は二分探索木です。

上記は 12 が 8 よりも左にあるので、二分探索木ではありません。
二分探索木では「左側の子孫すべてが現在のノード以下であり、右側の子孫すべてが現在のノード以上である」制約を持たせているのです。

平衡と非平衡

多くの木は平衡になっています。

平衡木とは、極端にアンバランスではない木と思っていれば大丈夫です。
データの追加や検索が O(log n) で実行できれば OK です。

左右の部分木がちょうと同じサイズ…という意味ではないので注意しましょう。

一般的な平衡木

ここでは詳しくは説明しませんが、平衡木の一般的な形は 2 種類あります。

全二分木 (Full Binary Tree) とは

すべてのノードが 0 個か 2 個の子を持つ二分木のことです。
つまり、子を 1 個だけしか持たないノードは存在しません。

上記は全二分木ではありません。

上記は全二分木です。

完全二分木とは

日本語に訳すると同じ「完全二分木」ですが、完全二分木の種類は 2 つあります。

Complete Binary Tree とは

一番深いノード以外のすべてのノードが満たされている二分木のことです。
最深部の一番右側のノードまで完全に埋まっている状態を意味します。

上記は Complete Binary Tree ではありません。

上記は Complete Binary Tree です。

Perfect Binary Tree とは

全二分木と Complete Binary Tree の性質を満たす二分木のことです。
すべての葉ノードは同じ深さであり、最も深い部分のノード数は最大になっています。

k を深さとすると、ノード数はちょうど 2^k - 1 個になります。

上記は Perfect Binary Tree です。
なお Perfect Binary Tree はレアケースということを覚えておいてください。

二分木の走査

二分木の走査 (traversal) の実装をみていきましょう。

間順走査 (In-Order Traversal) とは

最も一般的な二分木の走査です。
左側の枝、現在ノード、右側の枝で訪れることを意味します。

In-Order とは「中央順」という意味ですが、訪問するノードが昇順になるのが特徴です。

void inOrderTraversal (TreeNode node) {
    if (node != null) {
        // 再起実行 (左側の枝)
        inOrderTraversal(node.left);
        // 現在のノード
        visit(node);
        // 再起実行 (右側の枝)
        inOrderTraversal(node.right);
    }
}

前順走査 (Pre-Order Traversal) とは

Pre-Order とは「先行順」という意味ですが、現在ノードを訪れてから子ノードを訪れます。
必ず root (根) ノードから訪れるのが特徴です。

void preOrderTraversal (TreeNode node) {
    if (node != null) {
        // 現在のノード
        visit(node);
        // 再起実行 (左側の枝)
        preOrderTraversal(node.left);
        // 再起実行 (右側の枝)
        preOrderTraversal(node.right);
    }
}

後順走査 (Post-Order Traversal) とは

Post-Order とは「後行順」という意味ですが、子ノードを訪れてから現在ノードを訪れます。

void postOrderTraversal (TreeNode node) {
    if (node != null) {
        // 再起実行 (左側の枝)
        postOrderTraversal(node.left);
        // 再起実行 (右側の枝)
        postOrderTraversal(node.right);
        // 現在のノード
        visit(node);
    }
}

二分ヒープとは

最小ヒープとは

すべてのノードが子ノードよりも小さい完全二分木 (Complete Binary Tree) が最小ヒープです。
つまり root (根) ノードが木全体の最小値を持ちます。

左右の順序は決まっていません。

ノードを挿入する

完全二分木の特性上、ノードの挿入は「常に最後の部分に要素を追加する」ところから始まります。

次に、適切な位置が見つかるまで、新たに加えたノードと親ノードを入れ替えて木を修正します。
最小の要素が一番上にくるようにしましょう。

ヒープ内のノード数を n とすると、実行時間は O(log n) になります。

最小要素を取り出す

最小ヒープから最小要素を見つけるのは簡単です。
常に最小要素は一番上にあるからです。

ただし取り除くためには、最小要素とヒープ末尾の要素 (一番右下) を入れ替えます。
次にその要素と子要素を入れ替えながら、適切な位置まで下ろしていきます。

最小ヒープでは左右の順序が決まっていませんが、
上に最小値を持っていきたいので小さい方の値と交換しながら下ろします。

ヒープ内のノード数を n とすると、実行時間は O(log n) になります。

最大ヒープとは

最大ヒープは本質的には同じものですが、要素の並び順が降順になっています。

トライ木 (プレフィックス木) とは

トライ木 (プレフィックス木) とは、各ノードに文字が保持される n 分木の一種です。
木を下っていくと、その経路が単語になります。

* ノードとは

完全な単語であることを示すために * 文字を持った「 * ノード」を使うことがあります。
※ または null を持った「 null ノード」を使うこともあります。

たとえば MANY の下に * ノードがあれば MANY が完全な単語であることを示します。

* ノードの実装

ノードは TrieNode クラスから派生した TerminatingTrieNode クラスを用意するとか、
親ノード内で終端を表すフラグを使えば実装できます。

子ノードの数はどの場所でも「 0 からアルファベットサイズ + 1 」になります。

用途

接頭辞検索用の英語を保持する

よくある使い方としては、接頭辞検索用の英語を保持することです。

ハッシュテーブルでは、文字列が「正しい単語かどうか」素早く検索できますが、
文字列が「正しい接頭辞を持つかどうか」の判別はできません。

そのような場合にトライ木を使うと、文字列の長さが K とすると O(K) で実行できます。

正しい単語のリスト含む問題

正しい単語のリスト含む問題の多くはトライ木を利用します。

…といった、文字列の接頭辞を繰り返し検索する状況では、
現在のノードにそれまでの経路の参照を渡していきます。

そうすると、その都度 root (根) ノードから検索しなくても、
Y が MAN の子であるか調べるだけでよくなります。

グラフの種類

グラフとは、ノード同士のいくつかに「辺」を持ったものの集まりです。

視覚的にグラフを表現すると上記のようになります。

隣接リストとは

グラフをプログラミングで表現する一般的な方法は「隣接リスト」です。
すべての頂点 (ノード) は隣接する頂点のリストを持ちます。

無向グラフでは (a, b) のように辺が 2 回保持されます。
1 回は a の隣接点で、もう 1 回は b の隣接点です。

class Graph {
    public Node[] nodes;
}

class Node {
    public String name;
    public Node[] children;
}

木の場合と異なり、Graph クラスは単一ノードからすべてのノードに到達するとは限りません。
配列・配列リスト・連結リストであったり、ハッシュテーブルで隣接リストを持つことができます。

上記グラフは次のように表現することができます。

隣接行列とは

隣接行列とは、ノード数を N とすると N*N のブーリアン型行列のことです。
matrix[i][j] が真のとき、ノード i からノード j への辺が存在することになります。

無向グラフの場合、行列は対照的になりますが、
有向グラフの場合、行列が対照的になるとは限りません。

グラフ探索

これから紹介するグラフアルゴリズムは隣接リストで使うことができますが、
隣接行列の場合だと少し効率が落ちてしまいます。

隣接リストの場合、隣接するノードの走査を行うことができますが、
隣接行列の場合、全ノードを走査してノードが隣接しているかどうか調べる必要があるからです。

深さ優先探索 (Depth-First Search: DFS) とは

深さ優先探索 (DFS) では、root (根) ノードから探索を開始します。
そして次の枝に移る前に、各枝を完全に探索します。

DFS の優先順位

上記グラフの Node[0] から深さ優先探索をしたら、
走査する順番は以下のようになります。

DFS の実装

DFS では、ノード a に隣接するノード b に訪れるとき、
a に隣接している他の隣接ノード c などより、先に b に 隣接するノード全てを探索します。

一般的な木の走査や pre-oreder は DFS の一種ですが、
DFS における、木とグラフの違いは「そのノードをすでに訪れたかチェックするかどうか」です。

チェックしていないと無限ループにはまる可能性があります。

void dfs(Node root) {

    if (root == null) {
        return;
    }

    visit(root);
    root.visited = true;

    // 隣接ノードを取り出す
    foreach (Node n in root.adjacent) {
        if (n.visited == false) {
            // 再起実行
            dfs(n);
        }
    }
}

DFS のメリット

深さ優先探索は「グラフのすべてのノードを走査したい」場合に好まれます。

幅優先探索 (Breadth-First Search: BFS) とは

幅優先探索 (BFS) では、root (根) ノードから探索を開始します。
そして子ノードの探索をする前に、現在の隣接ノードを探索します。

BFS の優先順位

上記グラフの Node[0] から幅優先探索をしたら、
走査する順番は以下のようになります。

BFS の実装

BFS が再帰的な処理であると考えるのは間違いです。
BFS では「キュー」を利用します。

BFS では、ノード a を訪れるとき、
ノード a に隣接するノード b, c などの隣接ノードより、先に a の隣接ノード b, c を訪れます。

void bfs(Node root) {

    Queue queue = new Queue();
    root.marked = true;

    // キューの末尾に加える
    queue.enqueue(root);

    while (!queue.isEmpty()) {
        // キューの先頭から取り除く
        Node r = queue.dequeue();

        // 隣接ノードを取り出す
        foreach (Node n in r.adjacent) {
            if (n.marked == false) {
                n.marked = true;
                queue.enqueue(n);
            }
        }
    }
}

BFS のメリット

幅優先探索は「 2 つのノード間の最短経路、あるいは任意の経路を求めたい」場合に好まれます。

DFS と BFS の比較

たとえば、世界全体のすべての友人関係をグラフで表すことにしましょう。

そしてアッシュとベネッサの友人関係を表す経路を見つけたい場合、
DFS と BFS どちらのアルゴリズムがよいでしょうか。

DFS の場合

深さ優先探索を使った場合は アッシュ → ブライアン → カールトン → デイヴィス → エリック → ファラ → ゲイル → ハリー → イザベラ → ジョン → カリ → ... と非常に長くなってしまいます。

アッシュとベネッサが友人であることを認識しないで検索しているようなものです。
いつか経路は見つかりますが、非常に時間がかかりますし、最短経路ではありません。

BFS の場合

幅優先探索を使った場合、最初のアッシュから出来るだけ近いところに留まって検索します。
まずアッシュの知人をたくさん調べて、どうしても必要なときだけ遠い人間関係も調べます。

アッシュとベネッサが親友、または友人の友人くらいの関係ならすぐに見つけられるでしょう。

双方向探索 (Bidirectional Search) とは

双方向探索では、元となるノードと目的となるノードの最短経路を見つけます。

基本的には「幅優先探索」を元のノードと目的のノード 2 ヶ所から同時に行います。
探索時にお互いが衝突すれば経路発見となります。

上記は幅優先探索です。
単一の探索では s から t まで深さ 4 だとわかります。

上記は双方向探索です。
s からの探索と t からの探索、つまり双方向の探索があります。

s から t の深さ 2、t から s の深さ 2 のところで互いの探索が衝突します。
そのとき深さの和は 4 だとわかります。

双方向探索が早い理由

各ノードが隣接ノード k 個を持ったグラフがあるとします。
そのときノード s からノード t までの最短経路が d としましょう。

双方向探索が早い理由

CS シリーズ

次回

(ちょっとまってね)

前回