グラフの基本要素

説明

グラフは離散構造を記述するための基本的な道具である．特に辺に重みのある有向グラフはもっともよく使われる構造の一つである．

グラフの表現には大きく分けて隣接辺リスト，隣接行列の二つがある．隣接辺リストは各頂点にそれを始点とする辺の情報をリストとして格納する．隣接行列は正方行列で (i,j) 成分に辺 (i,j) の情報を格納する．それぞれのメリット，デメリットは以下のとおり．

• 隣接リスト: O(E) が正しく O(E) で扱える．素グラフであり，頂点を基準に考えれば十分な場合に適する．
• 隣接行列: O(E) が常に O(V^2) となる．密グラフの場合，または任意の辺を効率よく追加削除参照したい場合に適する．

ソースコード

typedef int Weight;
struct Edge {
  int src, dst;
  Weight weight;
  Edge(int src, int dst, Weight weight) :
    src(src), dst(dst), weight(weight) { }
};
bool operator < (const Edge &e, const Edge &f) {
  return e.weight != f.weight ? e.weight > f.weight : // !!INVERSE!!
    e.src != f.src ? e.src < f.src : e.dst < f.dst;
}
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

typedef vector<Weight> Array;
typedef vector<Array> Matrix;