vector - 如何在 C++ 中使用向量实现加权有向图？

Question

我正在尝试使用二维向量数组来为有向加权图创建邻接表表示。我正在使用二维向量数组，以便可以使用顶点存储相应的权重。有什么更好的方法吗？

Answer 1

这就是我对加权图的典型表示c++：

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

我使用 astd::pair来存储边，第一个元素是边的目标节点，第二个是它的权重。根据具体情况，更好的方法可能是为节点使用自定义结构。就像是：

struct edge {
  int to;
  int weight;
};

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