vector - C++でベクトルを使用して重み付き有向グラフを実装するにはどうすればよいですか?

Question

2D ベクトルの配列を使用して、有向加重グラフの隣接リスト表現を作成しようとしています。頂点に対応する重みを格納できるように、2D ベクトルの配列を使用しています。より良い方法はありますか？

Answer 1

これは、加重グラフの私の典型的な表現がc++次のように見えるものです:

vector<vector<pair<int, int> > > adj_list;

最初の要素はstd::pairエッジの宛先ノードであり、2 番目の要素はその重みです。ケースによっては、ノードにカスタム構造を使用する方がよい場合もあります。何かのようなもの：

struct edge {
  int to;
  int weight;
};

....
vector<vector<edge> > adj_list;