競プロではグラフを扱う問題が頻出です。この記事では、C++で使えるグラフ用の自作ライブラリを紹介します。
主な機能と計算量
| 名前 | 説明 | 計算量 |
|---|---|---|
constructor(n) |
n頂点のグラフを作る |
$O(n)$ |
add_edge(u, v) |
辺( u→v、コスト 1 )を追加 |
$O(1)$ |
size_n() |
グラフの頂点数を返す | $O(1)$ |
size_e() |
グラフの辺の数を返す | $O(1)$ |
total_edge_cost() |
辺の合計コストを返す | $O(1)$ |
edges() |
辺リストを返す | $O(1)$ or $O(E)$ |
nexts() |
隣接リストを返す | $O(1)$ or $O(E)$ |
nexts(i) |
i からの隣接リストを返す |
$O(1)$ or $O(E)$ |
deg_in() |
入次数配列を返す | $O(1)$ or $O(E)$ |
deg_in(i) |
i の入次数を返す |
$O(1)$ |
deg_out() |
出次数配列を返す | $O(1)$ or $O(E)$ |
deg_out(i) |
i の出次数を返す |
$O(1)$ |
実装したコード
template<typename T = long long> // costの型
struct Graph {
///////////////辺の構造体↓/////////////
struct Edge{
T c;
int u,v; // u→vの辺
// 辺同士の比較は、c → u → vの順番に比較
bool operator<(const Edge &other) const {
return tie(c,u,v) < tie(other.c, other.u, other.v);
}
};
/////////////メンバ変数↓///////////////
vector<vector<pair<T,int>>> _nexts; // nexts[i] := i番目からの隣接リスト{コスト、行き先}
vector<Edge> _edges; // 辺リスト
T _total_edge_cost; // 全ての辺のコストの合計
vector<int> _deg_in; // 全ての頂点の入次数を保持
vector<int> _deg_out; // 全ての頂点の出次数を保持
//////////コンストラクタ↓////////////
Graph(int n): _nexts(n), _total_edge_cost(0), _deg_in(n,0), _deg_out(n,0) {}
//////////メンバ関数↓////////////////
//コスト1の辺u → vを追加する関数
void add_edge(int u, int v){
add_edge(T(1), u, v);
}
//コストcの辺u → vを追加する関数
void add_edge(T c, int u, int v){
_nexts[u].push_back({c, v});
_edges.push_back(Edge{c, u, v});
_total_edge_cost += c;
_deg_out[u]++;
_deg_in[v]++;
}
//頂点数を返す関数
int size_n() const {
return _nexts.size();
}
//辺の本数を返す関数
int size_e() const {
return _edges.size();
}
// 全ての辺のコストの合計を返す
T total_edge_cost() const {
return _total_edge_cost;
}
// 辺リストを返す関数
const vector<Edge>& edges() const {
return _edges;
}
// 隣接リストを返す関数
const vector<vector<pair<T,int>>>& nexts() const {
return _nexts;
}
// iから行ける場所の{コスト、行き先}の集合を返す関数
const vector<pair<T,int>>& nexts(int i) const {
return _nexts[i];
}
// 入次数配列を返す関数
const vector<int>& deg_in() const {
return _deg_in;
}
// 頂点iの入次数を返す関数
int deg_in(int i) const {
return _deg_in[i];
}
// 出次数配列を返す関数
const vector<int>& deg_out() const {
return _deg_out;
}
// 頂点iの出次数を返す関数
int deg_out(int i) const {
return _deg_out[i];
}
};
使用例
#include<bits/stdc++.h>
using namespace std;
//--ここにGraphライブラリ--//
// //
//----------------------//
int main(void){
// グラフの作成
Graph g(4);
g.add_edge(10, 0, 1); //0 → 1：コスト10の辺を追加
g.add_edge(10, 0, 2); //0 → 2：コスト10の辺を追加
g.add_edge(15, 0, 3); //0 → 3：コスト15の辺を追加
g.add_edge(10, 2, 3); //2,3の間に無向辺を追加
g.add_edge(10, 3, 2);
// グラフの合計コストを求める（無向辺は二重にカウントされることに注意）
cout << g.total_edge_cost() << endl; // 55
}
注意点・Tips
- 頂点番号は
0-indexedで扱っています - 無向辺を追加する場合は、
u → vとv → uを2本追加します - ただしその場合、
total_edge_costに重複して加算されます - 辺の比較は、デフォルトでコストが小さい順になります
- 辺コストの型
Tには、long long、int、doubleなどが使えます - 計算量が「$O(1)$ or $O(E)$」となっている部分は、
-
const vector<int>& deg_in = g.deg_in();と書けば$O(1)$ -
vector<int> deg_in = g.deg_in();と書けば$O(E)$
です
-
関連リンク
- 最小全域木（クラスカル法） ← Graphライブラリを使用しています
- ダイクストラ法 ← Graphライブラリを使用しています
- Union-Find