Notebook

🐜本の進捗(ベルマンフォード/ダイクストラ/クラスカル)::9/14

得るものが大きい.

2-5 グラフ

頂点と辺からなるデータ構造.頂点と辺の集合を$V,E$であるようなグラフを$G=(V,E)$と表し,2点$u,v$を結ぶ辺を$e=(u,v)$のように表す.

グラフには結びつきに方向性のある有向グラフと,方向性のない無向グラフがある.

木構造は閉路を持たない無向グラフであり,かつ連結であるものを指す.

代わりに連結でないものは森と呼ばれる.

有向グラフに対し,とある頂点$v$から出ていく辺の集合と,入ってくる辺の集合はそれぞれ,$\delta_+(v),\delta_-(v)$とあらわされ,$|\delta_+(v)|,|\delta_-(v)|$をそれぞれ,頂点$v$の出次数,入次数という.

閉路を持たない有向グラフはDAG(Directed Acyclic Graph:有向非巡回グラフ)と呼ばれる.

実装時の方法

行列を使って辺の情報を記憶する方法と,各々の点にリストを与え,辺を記憶する方法があるが,前者はメモリを,疎グラフであっても常に頂点数の二乗だけ必要となってしまうという欠点がある.

実装

C++の勉強兼復習を兼ねて,classでグラフを定義するとどうなるかを考える.

クラス設計等の知識が皆無なので,この方法で良いのかはわからない.

#include <bits/stdc++.h>
using namespace std;
int const nil = (1 << 31);

template <typename T>
class Vertex{
    public:
      int param=nil;
      vector< pair<Vertex *, T> > e;
      int size(){
          return e.size();
      }
};

template <typename T>
class Graph{
    public:
    vector<Vertex<T> *> V;
    Vertex<T>* getVertex(int idx){
        return V[idx];
    }
    int getColor(int idx){
        return V[idx]->param;
    }
    Graph(int v_size){
        for (int i = 0; i < v_size;i++){
            V.push_back(new Vertex<T>());
        }
    }
    int size(){
        return V.size();
    }
    void colorize(int idx, int color){
        V[idx]->param = color;
    }
    void colorize(Vertex<T>* vertex, int color){
        vertex->param = color;
    }
    bool isColorize(int idx, int color){
        if(V[idx]->param==nil)
            return false;
        V[idx]->param = color;
        return true;
    }
    void unite(int v_from, int v_to,T weight=1, bool digraph=true){
        V[v_from]->e.push_back(make_pair(V[v_to], weight));
        if(!digraph){
            V[v_to]->e.push_back(make_pair(V[v_from], weight));
        }
    }
};

彩色問題に対応するため,頂点を簡単なクラスとしてつながりと色を保持するようにする.グラフ自体をクラスとして,結合や色塗りが関数で行えるようにする.

彩色問題の探索の例として以下の問題を考えてみる.

頂点数$N$の無向グラフのすべての頂点に対し,隣り合う頂点同士が違う色になるように2色で色を塗ることができるかを出力せよ.

入力が辺の数を$K$として,

$N~K\\$

$v_1~u_1\\$

$...\\$

$v_k~u_k$

と与えられると考えると,深さ優先探索を用いて,以下のように解ける.

bool dfs(Graph<int>* g, Vertex<int>* v, int c){
    g->colorize(v, c);
    auto edges = v->e;
    for (auto u : edges)
    {
        if(v->param == u.first->param)
            return false;
        if(u.first->param==nil && !dfs(g, u.first, -c))
            return false;
    }
    return true;
}

int main(){
    int N, E;
    cin >> N >> E;
    Graph<int> *g = new Graph<int>(N);
    for (int i = 0; i < E; i++){
        int a, b;
        cin >> a >> b;
        g->unite(a, b, 1, false);
    }
    for(auto v : g->V){
        if(v->param==nil){
            if(!dfs(g, v, 1)){
                cout << "No" << endl;
                return 0;
            }
        }
    }
    cout << "Yes" << endl;
    return 0;
}

最短路問題

Bellman-Ford法

重み付き有向グラフにおける単一始点の最短経路問題を解くラベル修正アルゴリズム[1]の一種である。各辺の重みは負数でもよい。辺の重みが非負数ならば優先度付きキューを併用したダイクストラ法の方が速いので、ベルマンフォード法は辺の重みに負数が存在する場合に主に使われる。

(wikipediaより)

全辺を走査的に見ていって,始点からの最短距離を$d[i]$としたとき, $d[i]=\min\{d[j]+cost(j\rightarrow i )|e=(j,i)\in E\}$が最短経路であることを利用して,更新を行う.負の閉路が存在しないと,高々更新は$|V|-1$回で済むので,全体としては$O(|V|\cdot|E|)$の計算量となる.

Dijkstra法

グラフ理論における辺の重みが非負数の場合の単一始点最短経路問題を解くための最良優先探索によるアルゴリズムである。辺の重みに負数を含む場合はベルマン-フォード法などが使える。辺の重みが全て同一の非負数の場合は幅優先探索が速く、線形時間で最短路を計算可能である。

(wikipediaより)

多分かなり有名なアルゴリズムなので説明はいらないよね.

  1. 各地点までの距離を未確定とし、とりあえず無限大としておきます。
  2. 始点の距離を0とおきます。
  3. 未確定の地点の中から、距離が最も小さい地点を選んで、 その距離を「その地点までの最短距離」として確定します。
  4. 今確定した地点から「直接つながっている」かつ 「未確定である」地点に対して、今確定した場所を経由した場合の 距離を計算し、今までの距離よりも小さければ書き直します。
  5. 全ての地点が確定すれば終了です。そうでなければ3へ。

優先度付きキューを用いることで,最小値の取り出しが容易に行なえ,計算時間の短縮($O(|V|^{2})\rightarrow O(|E|\log|V|)$)が見込めます.

最小全域木

まず,全域木(Spanning tree)とは連結グラフの全ての頂点とそのグラフを構成する辺の一部分のみで構成される木のこと.つまり,連結グラフから適当な辺を取り除いていき,閉路をもたない木の形にしたものが全域木となる.ここで,グラフの各辺に重みがある場合,重みの総和が最小になるように辺を選んで作った全域木のことを最小全域木(Minimum spanning tree)という.

(こちらのサイトより)

最小全域木を求めるには主に以下の2つのアルゴリズムがある.

  1. Kruskal法
  2. Prim法

うち,Kruskal法について実装した.

Kruskal法

まず,頂点全体をそれぞれ1つの木とみなす.(木の数=頂点の数の森を作る)

全辺の中から,重みが最小のものを持ってきて,全体のコストに付け足す.

全体が一つの木になるまでこれを繰り返す.ただし,辺が結ぶ2点が同一の木の要素であるならば,閉路となるので飛ばす.

2を結ぶ...

3を結ぶ...

4を結...ばない(頂点1と4が同一の木構造に属するため)

5を結んで全体が1つの木になる.全体のコストの和は13となる.

このアルゴリズムを実装するに当たって肝になるのが,頂点が同一の木に属するかの判定である.これは,UnionFindを用いるのが非常に相性が良い.UnionFindの計算量は対数より小さいアッカーマンの逆関数$O(\alpha(|V|))$となるので全体の計算量は,ソートアルゴリズムの計算量で決まる.

実装

上記3つのアルゴリズムを実装した.

入力は最小全域木の説明で用いたものと同一とし,経路探索の場合は頂点0から5への最短距離(=7)の出力を目的とした.

#include <bits/stdc++.h>
using namespace std;
static const int nil = (1 << 31);
static const int inf = (1 << 30);

class UnionFind{
    private:
    vector<int> arr;
    public:
    UnionFind(int size): arr(size, -1){}
    int root(int node){
        return arr[node] < 0 ? node : arr[node] = root(arr[node]);
    }
    int size(int x){
        return -arr[root(x)];
    }
    bool unionSet(int x, int y){
        x = root(x);
        y = root(y);
        if(x!=y){
            if(arr[x] < arr[y])
                swap(x, y);
            arr[x] += arr[y];
            arr[y] = x;
        }
        return x != y;
    }
    bool findSet(int x, int y){
        return root(x) == root(y);
    }
};

template <typename T>
class Vertex{
    public:
      int idx;
      int param = nil;
      int dist = inf;
      vector<pair<Vertex *, T> > e;
      int size(){
          return e.size();
      }

      bool operator ==(const Vertex* o){
          return dist == o->dist;
      }
      bool operator !=(const Vertex* o){
          return dist != o->dist;
      }
      bool operator >(const Vertex* o){
          return dist > o->dist;
      }
      bool operator >=(const Vertex* o){
          return dist >= o->dist;
      }
      bool operator <(const Vertex* o){
          return dist < o->dist;
      }
      bool operator <=(const Vertex* o){
          return dist <= o->dist;
      }
};

template <typename T>
class Graph{
    public:
    vector<Vertex<T> *> V;
    typedef tuple<Vertex<T> *, Vertex<T> *, T> Edge;
    vector<Edge> E;
    Graph(int v_size){
        for (int i = 0; i < v_size;i++){
            auto v = new Vertex<T>();
            v->idx = i;
            V.push_back(v);
        }
    }
    static bool comp(const Edge &e1, const Edge &e2)
    {
        return get<2>(e1) < get<2>(e2);
    }
    Vertex<T> *getVertex(int idx)
    {
        return V[idx];
    }
    int getColor(int idx){
        return V[idx]->param;
    }
    int size(){
        return V.size();
    }
    void colorize(int idx, int color){
        V[idx]->param = color;
    }
    void colorize(Vertex<T>* vertex, int color){
        vertex->param = color;
    }
    bool isColorize(int idx, int color){
        if(V[idx]->param==nil)
            return false;
        V[idx]->param = color;
        return true;
    }
    void unite(int v_from, int v_to,T weight=1, bool digraph=true){
        E.push_back(make_tuple(V[v_from], V[v_to], weight));
        V[v_from]->e.push_back(make_pair(V[v_to], weight));
        if(!digraph){
            E.push_back(make_tuple(V[v_to], V[v_from], weight));
            V[v_to]->e.push_back(make_pair(V[v_from], weight));
        }
    }
    void dijkstra(int idx){
        priority_queue<Vertex<T> *, vector<Vertex<T> *>, greater<Vertex<T> *> > pq;
        Vertex<T>* s = getVertex(idx);
        s->dist = 0;
        pq.push(s);
        while (!pq.empty())
        {
            Vertex<T>* v = pq.top();
            pq.pop();
            for (auto u : v->e){
                if(u.first->dist > v->dist + u.second){
                    u.first->dist = v->dist + u.second;
                    pq.push(u.first);
                }
            }
        }
    }
    void bellmanford(int idx){
        Vertex<T>* s = getVertex(idx);
        s->dist = 0;
        while(true){
            bool update = false;
            for(auto e : E){
                Vertex<T> *from = get<0>(e);
                Vertex<T> *to = get<1>(e);
                T cost = get<2>(e);
                if(from->dist != inf && to->dist > from->dist + cost){
                    to->dist = from->dist + cost;
                    update = true;
                }
            }
            if(!update)
                break;
        }
    }
    T kruskal(){
        sort(E.begin(), E.end(), Graph::comp);
        UnionFind uf = UnionFind(size());
        int res = 0;
        for (auto e : E){
            auto u = get<0>(e);
            auto v = get<1>(e);
            if(!uf.findSet(u->idx, v->idx)){
                uf.unionSet(u->idx, v->idx);
                res += get<2>(e);
            }
        }
        return res;
    }
    void stateInit(){
        for(auto v : V){
            v->dist = inf;
            v->param = nil;
        }
    }
};


int main(){
    int N, E;
    cin >> N >> E;
    Graph<int> *g = new Graph<int>(N);
    for (int i = 0; i < E; i++){
        int a, b, c;
        cin >> a >> b >> c;
        g->unite(a, b, c, false);
    }
    g->dijkstra(0);
    cout << g->getVertex(N - 1)->dist << endl;
    g->stateInit();
    g->bellmanford(0);
    cout << g->getVertex(N - 1)->dist << endl;
    g->stateInit();
    int v = g->kruskal();
    cout << v << endl;

    return 0;
}

実行例

入力:
6 9
0 1 2
1 3 3
3 5 7
0 2 5
2 4 9
4 5 1
1 4 4
1 5 6
3 4 2

出力:
7
7
13