グラフ問題の基本解法

[履歴] [最終更新] (2016/07/10 02:27:50)

プログラミング/IoT の関連商品 (Amazonのアソシエイトとして、当メディアは適格販売により収入を得ています。)

オープンソース・ソフトウェアルータVyatta入門　――実践ルーティングから仮想化まで (Software Design plus)

ゼルダの伝説ブレスオブザワイルド - Switch

サンハヤト SAD-101 ニューブレッドボード

リングフィットアドベンチャー -Switch

ポケットモンスターシールド -Switch

星

用語

共通の用語

vertex, node 頂点
edge 辺
頂点の次数
- 頂点につながっている辺の数
パス
- 隣接している頂点を結んでいった経路
閉路
- 始点と終点が同じパス

特殊なグラフの用語

二部グラフ
- 隣接する頂点を異なる色で彩色するとき、必要な最小の色数が 2 であるグラフ
連結グラフ
- 任意の頂点間にパスが存在するグラフ
重み付きグラフ
- 辺に cost 重みがあるグラフ
無向グラフと有向グラフ
- 辺の向きの有無によるグラフの分類
出次数と入次数
- 有向グラフのある頂点の次数 = 出次数 + 入次数
DAG (Directed Acyclic Graph)
- 閉路のない有向グラフ
トポロジカル順序
- DAG に付与できる順序。トポロジカルソートで求められます。
- vi から vj への edge(vi, vj) について i < j となることが任意の edge について成立する vi の順序。
tree 木
- 閉路のない無向の連結グラフ
  - 「辺の数 == 頂点の数 -1」の無向の連結グラフ
  - 「辺の数 == 頂点の数 -1」の無向の閉路のないグラフ
森
- tree が一つ以上存在するグラフ (連結である必要はなく、閉路のない無向グラフ)
根付き木
- 根 root がある tree
- すべての木は根つき木になれます
全域木 (Spanning Tree)
- 連結な無向グラフの部分グラフのうち、任意の 2 頂点を連結にするような tree
最小全域木 (Minimum Spanning Tree; MST)
- 全域木のうち辺のコストの総和が最小のもの

グラフの表現方法

隣接リストは省メモリな一方で走査する必要があります。
隣接行列はメモリを消費する代わりにアクセスは高速です。

in.txt

5 4  ← 頂点数、辺数
0 3 9  ← vi と vj の cost
1 2 1
1 3 2
1 4 8

main.cpp

隣接リスト

#include <iostream>
#include <vector>
#define INF (1e9)
using namespace std;

const int MAXN = 1024; // 最大頂点数

typedef pair<int,int> Edge;
#define to first
#define cost second
vector<Edge> G[MAXN];

int V,E;

int main() {
    cin>>V>>E;

    for (int i = 0; i < E; ++i) {
        int a,b,cost; cin>>a>>b>>cost;
        G[a].push_back(Edge(b,cost));
        G[b].push_back(Edge(a,cost));
    }

    for(int i = 0; i < V; ++i) {
        for(int j = 0; j < (int)G[i].size(); ++j) {
            cout << "from: " << i
                 << ", to: " << G[i][j].to
                 << ", cost: " << G[i][j].cost
                 << endl;
        }
    }
    return 0;
}

隣接行列

#include <iostream>
#include <vector>
#define INF (1e9)
using namespace std;

const int MAXN = 1024; // 最大頂点数
int G[MAXN][MAXN];
int V,E;

int main() {
    cin>>V>>E;

    fill((int *)G, (int *)(G+MAXN), INF);
    for (int i = 0; i < E; ++i) {
        int a,b,cost; cin>>a>>b>>cost;
        G[a][b] = G[b][a] = cost;
    }

    for(int i = 0; i < V; ++i) {
        for(int j = 0; j < V; ++j) {
            if(G[i][j] == INF) continue;
            cout << "from: " << i
                 << ", to: " << j
                 << ", cost: " << G[i][j]
                 << endl;
        }
    }
    return 0;
}

全探索

グラフの頂点を O(n) で走査して、グラフの性質を判定できます。二部グラフの判定や連結グラフの判定など。

#include <iostream>
#include <vector>
#define INF (1e9)
using namespace std;

const int MAXN = 1024;

typedef pair<int,int> Edge;
#define to first
#define cost second
vector<Edge> G[MAXN];

int V,E;
int color[MAXN]; // 初期値: 0, 二色: -1, +1

bool dfs(int v, int c) {
    color[v] = c;
    for(int i = 0; i < (int)G[v].size(); ++i) { // 頂点 v の辺を走査
        if(color[G[v][i].to] == c) return false;
        if(color[G[v][i].to] == 0 && !dfs(G[v][i].to, -c)) return false;
    }
    return true; // 彩色できる
}

int main() {
    cin>>V>>E;
    fill(color, color+MAXN, 0);
    for (int i = 0; i < E; ++i) {
        int a,b,cost; cin>>a>>b>>cost;
        G[a].push_back(Edge(b,cost));
        G[b].push_back(Edge(a,cost));
    }

    // 二部グラフ判定用 dfs

    // 連結グラフ用
    cout << (dfs(0, 1) ? "Yes" : "No") << endl;

    // // 連結していない可能性がある場合はこちら
    // for(int i = 0; i < V; ++i) {
    //     if(color[i] != 0) continue;
    //     if(!dfs(i, 1)) { cout << "No" << endl; return 0; }
    // }
    // cout << "Yes" << endl;
    return 0;
}

ダイクストラ法 (単一始点最短経路問題)

while ループ一回につき、始点から 1 ステップ先の最短経路が確定するイメージのアルゴリズムです。負の辺がない場合に使用できます。ベルマンフォード法よりも効率がよいです。

#include <iostream>
#include <vector>
#include <queue>
#define INF (1e9)
using namespace std;

const int MAXN = 1024;

typedef pair<int,int> Edge;
#define to first
#define cost second
vector<Edge> G[MAXN];

typedef pair<int,int> pii;
#define A top().first
#define B top().second

int V,E;
int dist[MAXN];

void dijkstra(int s) {
    fill(dist, dist+MAXN, INF);
    dist[s] = 0;

    priority_queue<pii,vector<pii>,greater<pii> > pq; // greater: pair.first が小さい順
    pq.push(pii(0,s)); // cost, vertex

    while(!pq.empty()) {
        int cost = pq.A;
        int v = pq.B;
        pq.pop();
        if(cost > dist[v]) continue;
        for(int i = 0; i < (int)G[v].size(); ++i) {
            Edge e = G[v][i];
            if(dist[e.to] > dist[v] + e.cost) {
                dist[e.to] = dist[v] + e.cost;
                pq.push(pii(dist[e.to], e.to));
            }
        }
    }
}

int main() {
    cin>>V>>E;
    for (int i = 0; i < E; ++i) {
        int a,b,cost; cin>>a>>b>>cost;
        G[a].push_back(Edge(b,cost));
        G[b].push_back(Edge(a,cost));
    }
    dijkstra(0); // 始点 0 からの dist を計算
    for(int i = 0; i < V; ++i) cout << "0 -> " << i << " : " << dist[i] << endl;
    return 0;
}

最短経路の出力

previous に最短経路が更新された頂点の直前の頂点を記憶しておくことで、最短経路の出力ができます。以下のように 4 箇所を追加します。ベルマンフォード法やワーシャルフロイド法も同様の考え方で対応できます。

#include <iostream>
#include <vector>
#include <queue>
#define INF (1e9)
using namespace std;

const int MAXN = 1024;

typedef pair<int,int> Edge;
#define to first
#define cost second
vector<Edge> G[MAXN];

typedef pair<int,int> pii;
#define A top().first
#define B top().second

int V,E;
int dist[MAXN];
int previous[MAXN]; // vi の直前の vertex を記憶するための配列 (追加 1/4)

void dijkstra(int s) {
    fill(dist, dist+MAXN, INF);
    fill(previous, previous+MAXN, -1); // 追加 2/4
    dist[s] = 0;

    priority_queue<pii,vector<pii>,greater<pii> > pq; // greater: pair.first が小さい順
    pq.push(pii(0,s)); // cost, vertex

    while(!pq.empty()) {
        int cost = pq.A;
        int v = pq.B;
        pq.pop();
        if(cost > dist[v]) continue;
        for(int i = 0; i < (int)G[v].size(); ++i) {
            Edge e = G[v][i];
            if(dist[e.to] > dist[v] + e.cost) {
                dist[e.to] = dist[v] + e.cost;
                previous[e.to] = v; // 追加 3/4
                pq.push(pii(dist[e.to], e.to));
            }
        }
    }
}

vector<int> get_path(int t) { // 追加 4/4
    vector<int> path;
    for(; t != -1; t = previous[t]) path.push_back(t);
    reverse(path.begin(), path.end());
    return path;
}

int main() {
    cin>>V>>E;
    for (int i = 0; i < E; ++i) {
        int a,b,cost; cin>>a>>b>>cost;
        G[a].push_back(Edge(b,cost));
        G[b].push_back(Edge(a,cost));
    }
    dijkstra(0); // 始点 0 からの dist を計算
    for(int i = 0; i < V; ++i) { // 始点 0 から各 vi までの最短経路を表示する例
        vector<int> path = get_path(i);
        for(int j = 0; j < (int)path.size(); ++j) {
            cout << path[j];
            if(j != (int)path.size() - 1) cout << " -> ";
        }
        cout << endl;
    }
    return 0;
}

ベルマンフォード法 (単一始点最短経路問題)

while ループ一回につき、始点から 1 ステップ先の最短経路が確定するイメージのアルゴリズムです。負のコストの閉路が存在しなければ |V| - 1 回の while で終了します。

#include <iostream>
#include <vector>
#define INF (1e9)
using namespace std;

const int MAXN = 1024;

typedef pair<int,int> Edge;
#define to first
#define cost second
vector<Edge> G[MAXN];

int V,E;
int dist[MAXN];

void bellman_ford(int s) {
    fill(dist, dist+MAXN, INF);
    dist[s] = 0;
    while(true) {
        bool update = false;
        for(int i = 0; i < V; ++i) {
            for(int j = 0; j < (int)G[i].size(); ++j) {
                Edge e = G[i][j];
                if(dist[i] != INF && dist[e.to] > dist[i] + e.cost) {
                    dist[e.to] = dist[i] + e.cost;
                    update = true;
                }
            }
        }
        if(!update) break;
    }
}

int main() {
    cin>>V>>E;
    for (int i = 0; i < E; ++i) {
        int a,b,cost; cin>>a>>b>>cost;
        G[a].push_back(Edge(b,cost));
        G[b].push_back(Edge(a,cost));
    }
    bellman_ford(0); // 始点 0 からの dist を計算
    for(int i = 0; i < V; ++i) cout << "0 -> " << i << " : " << dist[i] << endl;
    return 0;
}

ワーシャルフロイド法 (任意の二点間の最短経路)

O(n^3) と計算量はかかりますが、任意の二つの頂点の最短経路をすべて計算できます。単一始点最短経路問題の解法にもなります。隣接リストではなく隣接行列を利用します。

負の辺があっても動作します (ベルマンフォード法と同じです)
負のコストの閉路が存在すると、最短経路という概念がなくなるため最短経路の出力にはなりません (ベルマンフォード法と異なり計算は終了します)
- 負のコストの閉路が存在する場合は、マイナスになる G[i][i] (どちらも i です) が存在します。検出に使えます。

main.cpp

#include <iostream>
#include <vector>
#define INF (1e9)
using namespace std;

const int MAXN = 1024;
int G[MAXN][MAXN]; // vi から vj への最短経路
int V,E;

void warshall_floyd() {
    for (int k = 0; k < V; ++k) { // vertex k を固定して考えます。
        for (int i = 0; i < V; ++i) {
            for (int j = 0; j < V; ++j) {
                // k を経由したほうがよいかどうか (複数の vertex 集合が k として代表される)
                G[i][j] = min(G[i][j], G[i][k] + G[k][j]);
            }
        }
    }
}

int main() {
    cin>>V>>E;
    fill((int *)G, (int *)(G+MAXN), INF);
    for(int i = 0; i < V; ++i) G[i][i] = 0; // 重要
    for (int i = 0; i < E; ++i) {
        int a,b,cost; cin>>a>>b>>cost;
        G[a][b] = G[b][a] = cost;
    }
    warshall_floyd();

    for(int i = 0; i < V; ++i) {
        for(int j = 0; j < V; ++j) {
            if(G[i][j] == INF) continue;
            cout << i << " -> "
                 << j << " : "
                 << G[i][j]
                 << endl;
        }
    }
    return 0;
}

プリム法 (最小全域木)

最小全域木が存在する (連結な重み付き無向グラフである) とします。最小全域木をプリム法で求めることができます。

最小全域木の辺のコストの総和 (prim() の返り値)
最小全域木の根を vertex 0 としたときの vertex i に下りるコスト (mincost[i])

main.cpp

#include <iostream>
#include <vector>
#include <queue>
#define INF (1e9)
using namespace std;

const int MAXN = 1024;

typedef pair<int,int> Edge;
#define to first
#define cost second
vector<Edge> G[MAXN];

typedef pair<int,int> pii;
#define A top().first
#define B top().second

int V,E;
int mincost[MAXN]; // 最小全域木の根を `vertex 0` としたときの `vertex i` に下りるコスト
bool used[MAXN];

int prim() {
    fill(mincost, mincost+MAXN, INF);
    fill(used, used+MAXN, false);
    mincost[0] = 0; // vertex 0 から貪欲的に使用済み集合を拡大
    int res = 0; // 辺のコストの総和

    priority_queue<pii,vector<pii>,greater<pii> > pq; // greater: pair.first が小さい順
    pq.push(pii(0,0)); // cost, vertex

    while(!pq.empty()) {
        int cost = pq.A;
        int v = pq.B;
        pq.pop();
        if(used[v]) continue;
        res += cost;
        used[v] = true; // 使用済み集合に加える
        for(int i = 0; i < (int)G[v].size(); ++i) {
            Edge e = G[v][i]; // vertex v に生えている辺は「使用済み集合」に新規に生えた辺
            if(!used[e.to] && mincost[e.to] > e.cost) {
                mincost[e.to] = e.cost;
                pq.push(pii(mincost[e.to], e.to));
            }
        }
    }
    return res;
}

int main() {
    cin>>V>>E;
    for (int i = 0; i < E; ++i) {
        int a,b,cost; cin>>a>>b>>cost;
        G[a].push_back(Edge(b,cost));
        G[b].push_back(Edge(a,cost));
    }
    cout << prim() << endl; // 最小全域木の辺のコストの総和
    return 0;
}

クラスカル法 (最小全域木)

Union-Find 木を用いたクラスカル法によっても最小全域木を求めることができます。イメージはプリム法と同じで、コストの小さい辺から順に unite していきます。

最小全域木の辺のコストの総和 (kruskal() の返り値)

main.cpp

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 1024;

int par[MAXN];
int rnk[MAXN];
void init(int n) { for(int i = 0; i < n; ++i) { par[i] = i; rnk[i] = 0; }}
int find(int x) { if(par[x] == x) return x; else return par[x] = find(par[x]); }
bool same(int x, int y) { return find(x) == find(y); }
void unite(int x, int y) { x = find(x); y = find(y); if(x == y) return;
    if(rnk[x] < rnk[y]) par[x] = y; else { par[y] = x; if(rnk[x] == rnk[y]) ++rnk[x]; }}

// クラスカル法においては Edge を cost でソートする必要があるため、
// u, v を cost と同様に要素として扱えるデータ構造 struct を利用します。
struct Edge { int u, v, cost; };

Edge es[MAXN];
int V,E;

bool comp(const Edge& e1, const Edge& e2) {
    return e1.cost < e2.cost;
}

int kruskal() {
    sort(es, es + E, comp);
    init(V);
    int res = 0;
    for(int i = 0; i < E; ++i) {
        Edge e = es[i];
        if(!same(e.u, e.v)) {
            unite(e.u, e.v);
            res += e.cost;
        }
    }
    return res;
}

int main() {
    cin>>V>>E;
    for (int i = 0; i < E; ++i) {
        Edge e; cin>>e.u>>e.v>>e.cost;
        es[i] = e;
    }
    cout << kruskal() << endl; // 最小全域木の辺のコストの総和
    return 0;
}