甲斐性のない男が機械学習とか最適化とかを綴るブログ

うどんくらいしか食べる気がしない

競プロとかに使うアルゴリズム実装メモ(幅優先・深さ優先探索、union-find、最小全域木)

はじめに

以前の記事にて最短経路問題を解くアルゴリズムの実装を書きましたが、今回はその続きとしてグラフアルゴリズムの中でも幅優先探索深さ優先探索、union-find、最小全域木問題を解くアルゴリズム2種について実装を書いていきます。
例によって、自分の脳内整理メモの側面が強い上、検索すればそれぞれのアルゴリズムについて素晴らしい解説記事が出てくるので、まじめな解説を見たい場合はそちらを当たった方が良いと思います。

幅優先探索

用途

  • コストが全て同じグラフ(重みなしグラフ)の最短経路探索。
  • 連結成分の列挙。
  • 重みなしグラフの最小全域木

アルゴリズムのポイント

  • 隣接する頂点から順々に探索していく。
  • 距離を求める場合は、遷移元の距離に+1をする。

実装のポイント

  • キューを使う。
  • まずスタートの頂点をキューに入れ、キューの先頭から頂点を取り出し、それに隣接する頂点を探索。
  • 未探索の全て頂点はキューに追加して、またキューの先頭から頂点を取り出して・・・ということを目的の頂点が見つかるか、キューが空になるまで繰り返していく。
  • 既に探索済みの頂点かというフラグを持たせておき、既に見た頂点だった場合はキューに追加しない(下記実装では距離が初期値-1でなければ探索済みと判定)。

実装

以前と同様、メイン関数は省略。

#include <unordered_map>
#include <vector>
#include <queue>

class breadth_first_search
{
private:
    int node_num;
    int abs_time;
    std::unordered_map<int, std::vector<int>> adj_list;
    std::vector<int> dists;//始点からの距離

public:
    breadth_first_search(const int node_num,
        const std::unordered_map
        <int, std::vector<int>>& adj_list);
    void exec_search(int start);
    int get_dist(int v);
};

breadth_first_search::breadth_first_search(const int node_num,
    const std::unordered_map
    <int, std::vector<int>>& adj_list) :
    node_num(node_num),
    adj_list(adj_list),
    dists(node_num + 1, -1)
{
}

void breadth_first_search::exec_search(int start) {
    std::queue<int> v_queue;
    v_queue.push(start);
    dists[start] = 0;
    int d = 0;
    while (1) {
        if (v_queue.empty() == true)
            break;
        int v = v_queue.front();
        v_queue.pop();
       
        for (int &adj : adj_list[v]) {
            if (dists[adj] == -1) {
                dists[adj] = dists[v] + 1;
                v_queue.push(adj);
            }
        }
    }
}

int breadth_first_search::get_dist(int v) {
    return dists[v];
}

AOJのALDS1_11_Cが通ることを確認。

深さ優先探索再帰呼び出し版)

用途

  • コストが全て同じグラフ(重みなしグラフ)において、与えられたコスト以内でたどり着ける頂点の列挙。
  • 現実における迷路探索(現実だと幅優先探索は分身かワープでもできないと無理)。
  • 深さを時系列的な情報と関連づけて探索するケース。

(基本、幅優先探索と同じことができるが、それぞれ解きたい問題に応じて使い分ける)

アルゴリズムのポイント

  • 行けるところまでどんどん深くまで探索していく。
  • これ以上探索できないというところまで探索したら根まで戻り、更に別なルートの探索を進める。

実装のポイント

  • 幅優先探索と同じノリでスタックを使うパターンと再帰呼び出しを使うパターンがある(今回の実装は再帰版)。
  • 再帰呼び出しで行う場合、分岐して最深部まで探索した後、分岐点まで戻って来たときに既に探索済みか否かという情報をクリアしたいケースの実装が楽になる(上記の深さと時系列情報を関連付ける場合、分岐点に戻る=時系列的にも戻る=探索済み情報をクリアする、とするべき問題もある。これとか)。
  • 今回の実装では、AOJの問題に対応するべく、探索で移動したらカウントアップ(後戻り時もカウントアップ)するabs_time変数を用意し、exec_search_sub関数に入った時と出る時にカウントアップさせている。また、find_abs_timesには各頂点を見つけたときのabs_timeを保持しておく。
  • find_abs_timeが初期値(-1)でなければ、確定頂点として探索しない。
  • このタイムスタンプのつけ方は、問題に応じて適宜カウントアップするタイミング、回数、場合によっては初期値にクリアする等の変更が必要。

実装

#include <unordered_map>
#include <vector>
class depth_first_search
{
private:
    int node_num;
    int abs_time;
    std::unordered_map<int, std::vector<int>> adj_list;
    std::vector<int> depths;//ルートからの深さ(距離ではない)
    std::vector<int> find_abs_times;//頂点に到達した時刻
    std::vector<int> finish_abs_times;//サーチが完了した時刻
    
    void exec_search_sub(int start, int depth);

public:
    depth_first_search(const int node_num, 
                       const std::unordered_map
                        <int, std::vector<int>>& adj_list);
    
    void exec_search(int start);
    int get_depth(int v);
    int get_find_abs_time(int v);
    int get_finish_abs_time(int v);
};

depth_first_search::depth_first_search(const int node_num, 
                                       const std::unordered_map
                                        <int, std::vector<int>>& adj_list):
    node_num(node_num),
    abs_time(0),
    adj_list(adj_list),
    depths(node_num + 1, -1),
    find_abs_times(node_num + 1, -1),
    finish_abs_times(node_num + 1, -1)
{
}

void depth_first_search::exec_search_sub(int start, int depth) {
    
    if (find_abs_times[start] != -1) return;
    depths[start] = depth;
    abs_time++;//探索進みのカウントアップ
    find_abs_times[start] = abs_time;
    for (auto &v : adj_list[start]) {
        exec_search_sub(v, depth + 1);         
    }
    abs_time++;//探索後戻りのカウントアップ
    finish_abs_times[start] = abs_time;
}

void depth_first_search::exec_search(int start) {
    for (int i = start; i < node_num + 1; i++) {
        exec_search_sub(i, 0);
    }
}

int depth_first_search::get_depth(int v) {
    return depths[v];
}
int depth_first_search::get_find_abs_time(int v) {
    return find_abs_times[v];
}

int depth_first_search::get_finish_abs_time(int v) {
    return finish_abs_times[v];
}

AOJのALDS1_11_Bが通ることを確認。

union-find

用途

  • 集合を扱うデータ構造。
  • 値xとyが同じ集合に属するか否かの判定や2つの集合の結合が高速で実行可能。
  • 後に説明する最小全域木問題を解くアルゴリズムであるクラスカル法でも使われる。

アルゴリズムのポイント

  • 各集合、木構造でデータを保持する。
  • 値xとyが同じ集合か否かを判断するには(以下、find操作)、木の根を見て同じだったら同じ集合、異なれば別の集合に属すると判断すればよい。
  • そのため、なるべく木の高さが低くなるようにデータを保持した方が、高速に判断できるようになる。
  • このことから、2つの集合を結合する操作(以下、unite操作)では木の高さが低い方の根の親を高い方の根になるように連結させる。こうすれば、連結後の木の高さは元の集合のうち高い方の高さと同じになるので、高さは増えない(両方の木の高さが同じ場合は、木の高さが1だけ増える)。

実装のポイント

  • 木は親ノードの値を保持する1次元配列と所属する木の高さを保持する1次元配列で表現する。
  • こうすれば、unite操作時、低い方の木の根の親を書きかえるように親を保持する配列を操作だけで良くなる。
  • find操作時に全てのノードを直接親ノードとつなぐことで木の縮約を行う。
  • 木の縮約時に木の高さの更新を行わないので実際の木の高さと配列に保持している高さが合わなくなるが、あまり気にしなくてよい(重要なのはノードの親子関係であり、それさえ合っていればunion-findは問題なく動作する。木の高さの配列に入っている値がおかしいとunite操作時に、接続する関係が逆になり木が高くなる恐れがあるが、それよりもfind操作で縮約する方がメリットが大きい)。

実装

#include <vector>

class union_find
{
private:
    std::vector<int> parent;
    std::vector<int> rank;
    int node_num;
public:
    union_find(int node_num);
    void unite(int x, int y);
    int find(int x);
};

union_find::union_find(int node_num):
    parent(node_num + 1, 0),
    rank(node_num + 1, 0)
{
    for (int i = 0; i <= node_num; i++) {
        parent[i] = i;
    }
}

void union_find::unite(int x, int y) {
    int x_root = find(x);
    int y_root = find(y);
    //既に同じ根なら、同じ所属なので何もしない
    if (x_root == y_root) return;
    //ランクが大きい方に小さい方をくっつける
    //結合後のランクは大きい方になる。
    if (rank[x_root] > rank[y_root]) {
        parent[y_root] = x_root;
    }
    else {
        parent[x_root] = y_root;
        if(rank[x_root] == rank[y_root]){
            //ランクが等しい場合は、必ずランクが1上がる。
            rank[y_root]++;
        }
    }
}

int union_find::find(int x) {
    if (x != parent[x]) {
        // findの結果を各parentに入れることで経路を圧縮。
        //ただし、変更コストが大きいのでランクは変えてない。
        parent[x] = find(parent[x]);
    }
    return parent[x];
}

後に説明するクラスカル法の中で一緒に確認。

プリム法

用途

  • 最小全域木問題を解く。
  • 最小全域木問題自体は与えられた無向グラフから、ループがなくなるように枝を取り除き、辺のコストの合計が最小になる全域木を求める問題。
  • 例えば、全ての街間で行き来できるように最小コストで道を作りたい的な問題に使える(完全グラフを構成して最小全域木を求める等*1)。

アルゴリズムのポイント

  • ダイクストラ法と似ており、まず探索の初期位置となる頂点を決め、そこから出ている辺を探索中リストに追加する。
  • 探索中リストの中で最小のコストの辺を取り出す。この辺は最小全域木の構成要素として確定する。
  • 上記で取り出した辺につながっている頂点を次の探索対象の頂点とし、その頂点を確定頂点とする。また同様にそこから出ている辺を探索中リストに追加する(ただし、確定頂点へつながる辺は登録しない)。
  • これらの操作を全ての頂点が確定するまで繰り返す。

実装のポイント

  • ダイクストラ法と同様に優先度付きキューを使う。
  • 各頂点に対して現在どのコストで優先度付きキューに登録しているかを保持する外部変数keyを用意する。
  • 優先度付きキューから最小コストの辺(と接続先の頂点)を取り出し、この辺を最小全域木の構成要素として確定させる。
  • 同時に接続先の頂点も確定頂点として記録し、次はその頂点につながっている辺を見ていく。
  • 辺のコストを見て、接続頂点のkeyの値より小さいコストの辺だったらkeyの値を更新し、優先度付きキューに追加する。もし、大きいコストの辺だったら、その辺は最小全域木の構成要素にはなり得ないので、優先度付きキューには追加しない。これ結構大事。これをやらないと、どんどん優先度つきキューに登録されていくので、サイズがばかでかくなり、確定ノードかの判定回数が大幅に増えるので遅くなる可能性がある。

実装

#include <vector>
#include <unordered_map>
#include <algorithm>
#include <vector>
#include <unordered_map>
#include <queue>
#include <functional>
#include <climits>


class edge {
public:
    edge(int to, long long cost);
    int get_to() const;
    long long get_cost() const;
private:
    int to;
    long long cost;
};

edge::edge(int to, long long cost) : to(to), cost(cost) {}

int edge::get_to() const { return to; }

long long edge::get_cost() const { return cost; }

class prim
{
private:
    //unordered_mapを使って隣接リストを構築
    //first:接続元、second:辺のコストと接続先
    std::unordered_map<int, std::vector<edge>> adj_list;
    std::vector<int> pred;
    std::vector<long long> key;
    int node_num;
    std::vector<bool> is_done;//確定ノードか否かを保持
    long long MST_cost;
public:
    prim(const int node_num, const std::unordered_map<int, std::vector<edge>>& adj_list);
    long long get_MST_cost() const;
    //std::unordered_map<int, std::vector<edge>> calc_MST();
    std::unordered_map<int, std::vector<edge>> get_MST_list();
    void calc_MST();
};

prim::prim(const int node_num, const std::unordered_map<int, std::vector<edge>>& adj_list):
    adj_list(adj_list),
    node_num(node_num),
    is_done(node_num + 1, false),
    pred(node_num + 1, INT_MAX),
    key(node_num + 1, LLONG_MAX),
    MST_cost(0)
{

}

void prim::calc_MST() {
    MST_cost = 0;
    key = std::vector<long long>(node_num + 1, LLONG_MAX);
    pred = std::vector<int>(node_num + 1, INT_MAX);
    //優先度付きキューpairで頂点番号と最短距離を保持
    //firstの要素で比較されるので、firstが距離、secondを遷移先の頂点とする
    std::priority_queue<std::pair<long long, int>,
        std::vector<std::pair<long long, int>>,
        std::greater<std::pair<long long, int>>> p_queue;
    p_queue.push(std::make_pair(0, adj_list.begin()->first));
    key[adj_list.begin()->first] = 0;
    pred[adj_list.begin()->first] = -1;

    while (1) {
        if (p_queue.empty() == true) break; //キューが空なら終了
        std::pair<long long, int> cost_node = p_queue.top();
        p_queue.pop();
        if (is_done[cost_node.second] == false) {
            MST_cost += cost_node.first;
        }
        
        int from_node = cost_node.second;
        is_done[from_node] = true; //キューから取り出した頂点を確定頂点とする
        for (auto &it : adj_list[from_node]) {
            int adj_node = it.get_to();
            if (is_done[adj_node] == false) {
                long long adj_cost = it.get_cost();
                if (adj_cost < key[adj_node]) {
                    p_queue.push(std::make_pair(adj_cost,adj_node));
                    key[adj_node] = adj_cost;
                    pred[adj_node] = from_node;
                }
            }
        }
    }
}


long long prim::get_MST_cost() const {
    return  MST_cost;
}

std::unordered_map<int, std::vector<edge>> prim::get_MST_list() {
    std::unordered_map<int, std::vector<edge>> MST_list;
    for (int i = 0; i < node_num + 1; i++) {
        if (pred[i] >= 0 && pred[i] < node_num + 1) {
            MST_list[i].push_back(edge(pred[i], key[i]));
            MST_list[pred[i]].push_back(edge(i, key[i]));
        }
    }
    return MST_list;
}

AOJのGRL_2_Aが通ることを確認。

クラスカル

用途

アルゴリズムのポイント

  • 最初は全ての頂点間が未連結の状態(辺がない状態)からスタート。
  • 辺をコストでソート後、コストが小さい辺から順に全域木の構成要素に追加していく。ただし、ループができる場合はその辺は追加しない。
  • 辺を追加してループができるか否かは、その辺で結んでいる両頂点が既に連結関係にあるか否かで判断可能(既に連結関係にあれば、その辺を追加すると必ずループができる)。

実装のポイント

  • 連結されている頂点同士が同じ集合になるようunion-findで管理し、頂点間の連結関係を効率よく判定および操作できるようにする。
  • 実装では隣接リストをコンストラクタで渡しているが、辺を管理する変数を用意する方が楽なので、隣接リストから辺のリストに変換させている(最初から辺のリストを構築してもよい)。
  • 辺はstd::pair<int, std::pair<int, int>>型で(コスト, (頂点, 頂点))という変数にし、リストにしたとき第1要素のコストでソートされるようにする。

実装

上述のunion-findを使用する。

#include <algorithm>
#include <vector>
#include <unordered_map>
#include <queue>
#include <functional>
#include <climits>

class edge {
public:
    edge(int to, long long cost);
    int get_to() const;
    long long get_cost() const;
private:
    int to;
    long long cost;
};

edge::edge(int to, long long cost) : to(to), cost(cost) {}

int edge::get_to() const { return to; }

long long edge::get_cost() const { return cost; }

class kruskal
{
private:
    //unordered_mapを使って隣接リストを構築
    //first:接続元、second:辺のコストと接続先
    std::unordered_map<int, std::vector<edge>> adj_list;
    //最小全域木の隣接リスト
    std::unordered_map<int, std::vector<edge>> MST_list;
    int node_num;
    long long MST_cost;
public:
    kruskal(const int node_num, const std::unordered_map<int, std::vector<edge>>& adj_list);
    long long get_MST_cost() const;
    std::unordered_map<int, std::vector<edge>> get_MST_list();
    void calc_MST();
};


kruskal::kruskal(const int node_num, const std::unordered_map<int, std::vector<edge>>& adj_list):
    adj_list(adj_list),
    node_num(node_num),
    MST_cost(0)
{
}

void kruskal::calc_MST() {
    //辺のリスト。firstがコスト、secondがつながっている両頂点
    std::vector<std::pair<long long, std::pair<int, int>>> edge_list;

    //隣接リストから辺のリストへ変換
    for (auto &v : adj_list) {
        for (auto &e : v.second) {
            edge_list.push_back(std::make_pair(e.get_cost(), 
                        std::make_pair(v.first, e.get_to())));
        }
    }

    std::sort(edge_list.begin(), edge_list.end());

    union_find uf(node_num + 1);
    MST_cost = 0;
    MST_list.clear();
    for (auto &ed : edge_list) {
        int v1 = ed.second.first;
        int v2 = ed.second.second;
        long long cost = ed.first;
        //同じ根を持つなら、既に両頂点は同じ木の中
        //=辺を追加するとループができるのでなにもしない。
        if (uf.find(v1) != uf.find(v2)) {
            //根が異なる場合、両頂点間に辺を追加
            uf.unite(v1, v2);
            MST_cost += cost;
            MST_list[v1].push_back(edge(v2, cost));
            MST_list[v2].push_back(edge(v1, cost));
        }
    }
}

long long kruskal::get_MST_cost() const {
    return MST_cost;
}

std::unordered_map<int, std::vector<edge>> kruskal::get_MST_list() {
    return MST_list;
}

プリム法同様、AOJのGRL_2_Aで確認。

おわりに

前回、今回とグラフアルゴリズムについて見てきましたが、これら以外にもネットワークフロー問題やマッチング問題など様々な問題とそれらを解くアルゴリズムがあります。また、前回紹介した最短経路問題や今回扱った最小全域木問題、他にもマッチング問題など多くの問題は離散凸解析の枠組みで抽象化され、その枠組みの中で最適化アルゴリズムが提案されています。この離散凸解析についてはまだ全然理解していませんが、いつか勉強して記事を書きたいところです。
あと、このシリーズはもう少し続きます。次回は尺取り法や累積和法などを書いていこうと思います。

*1:競プロだと、完全グラフを考えると大抵の場合TLEになるので問題の性質から元のグラフをどのように構築するかというところが肝になる。