matrix_graph

クラス · 隣接行列

template <class T>
struct matrix_graph;

概要

隣接行列

テンプレートパラメータ

名前	説明
`T`	辺の重みの型。`void` を指定すると重みなしグラフ（隣接の有無を bool で持つ）になる。

計算量

構築は $O(V^2)$、辺追加・参照は $O(1)$

備考

距離行列としての利用を前提に、add_edge / add_edges は同一頂点対の重みを最小値でマージする（多重辺は最小重みを残す）。「辺なし」を表す番兵（INF など）で初期化しておくこと。mat[a][b] を直接代入すれば任意の値を上書きできる。

構築・破棄

名前	説明	計算量
`(constructor)`	(1) v頂点の全成分をeで初期化する (2) v頂点の空グラフを構築する	$O(V^2)$

メンバ関数

名前	説明	計算量
`begin`	行列の先頭iteratorを返す	$O(1)$
`end`	行列の終端iteratorを返す	$O(1)$
`size`	頂点数を返す	$O(1)$
`add_edge`	(1) 有向辺 a→b を重み d で張る（既存の重みとは最小値でマージ）。 (2) 有向辺 a→b を張る。	$O(1)$
`add_edges`	(1) 無向辺 a-b を重み d で張る（既存の重みとは最小値でマージ）。 (2) 無向辺 a-b を張る。	$O(1)$
`input_edge`	標準入力からm本の有向辺を追加する	$O(m)$
`input_edges`	標準入力からm本の無向辺を追加する	$O(m)$

演算子

名前	説明	計算量
`operator[]`	(1)、(3) 頂点iからの行を返す (2)、(4) 頂点iからの行を変更可能な参照で返す	$O(1)$

メンバ型

名前	説明	計算量
`value_type`	(1) 辺重みの型 (2) 隣接状態の型	型エイリアスで実行時計算量はない

メンバの詳細

(constructor)

// (1)
explicit matrix_graph(int v, T e = T());

// (2)
explicit matrix_graph(int v);

(1) v頂点の全成分をeで初期化する

計算量: $O(V^2)$

(2) v頂点の空グラフを構築する

計算量: $O(V^2)$

begin

// (1)
auto begin() const;

// (2)
auto begin();

// (3)
auto begin() const;

// (4)
auto begin();

(1)、(2)、(3)、(4) 行列の先頭iteratorを返す

計算量: $O(1)$

end

// (1)
auto end() const;

// (2)
auto end();

// (3)
auto end() const;

// (4)
auto end();

(1)、(2)、(3)、(4) 行列の終端iteratorを返す

計算量: $O(1)$

size

// (1)
constexpr int size() const;

// (2)
constexpr int size() const;

(1)、(2) 頂点数を返す

計算量: $O(1)$

add_edge

// (1)
void add_edge(int a, int b, T d = T(1));

// (2)
void add_edge(int a, int b);

(1) 有向辺 a→b を重み d で張る（既存の重みとは最小値でマージ）。

計算量: $O(1)$

(2) 有向辺 a→b を張る。

計算量: $O(1)$

add_edges

// (1)
void add_edges(int a, int b, T d = T(1));

// (2)
void add_edges(int a, int b);

(1) 無向辺 a-b を重み d で張る（既存の重みとは最小値でマージ）。

計算量: $O(1)$

(2) 無向辺 a-b を張る。

計算量: $O(1)$

input_edge

// (1)
void input_edge(int m, int origin = 1);

// (2)
void input_edge(int m, int origin = 1);

(1)、(2) 標準入力からm本の有向辺を追加する

計算量: $O(m)$

input_edges

// (1)
void input_edges(int m, int origin = 1);

// (2)
void input_edges(int m, int origin = 1);

(1)、(2) 標準入力からm本の無向辺を追加する

計算量: $O(m)$

operator[]

// (1)
const auto &operator[](int i) const;

// (2)
auto &operator[](int i);

// (3)
const auto &operator[](int i) const;

// (4)
auto &operator[](int i);

(1)、(3) 頂点iからの行を返す

計算量: $O(1)$

(2)、(4) 頂点iからの行を変更可能な参照で返す

計算量: $O(1)$

value_type

// (1)
using value_type = T;

// (2)
using value_type = bool;

(1) 辺重みの型

計算量: 型エイリアスで実行時計算量はない

(2) 隣接状態の型

計算量: 型エイリアスで実行時計算量はない