有向图中邻接表和权重的有效表示

Question

我想获得一些关于存储图形邻接表的反馈。

我通常使用向量的向量表示相邻列表，例如，std::vector<std::vector<int>> adj_list

对于边 E=(u,v)，它只是使用 adj_list[u].push_back(v) 存储。如果我想删除这条边，我只需做

it = std::find(adj_list[u_idx].begin(), adj_list[u_idx].end(), v);
adj_list[u_idx].erase(it);

我还需要一个数据结构来存储边对应的权重。所以最初，我想制作另一个向量的向量std::vector<std::vector<double>> weights，但这似乎不是最有效的解决方案。在权重中添加一个新元素很简单，就像上面一样。我所要做的就是weights[u].push_back(weight_to_add)。但是从权重中删除一个权重似乎比我上面所做的要困难一些，即找到迭代器，然后使用该迭代器执行删除。我可以在 adj_list 中找到迭代器对应的索引，然后从权重中删除索引，但我不知道这是否是最好的方法。

因此，我没有使用两个变量来表示邻接列表和权重，而是考虑制作一个同时存储邻接列表和权重的 3-D 向量。向量的向量向量。最后一个维度的大小为 2，用于存储节点 ID、v 和相应的边权重。所以实际上，它可能只是数组向量的向量。所以像 vector<vector<array<...>>> 这样的东西。但这里的问题是 v 是一个 int 并且权重是双倍的，所以显然我不能在这里使用数组。我可以将两者封装在一个结构中，然后执行类似 vector<vector<my_struct>> 的操作。或者像 vector<vector<pair<int,double>>> 这样的东西会更好？

关于如何解决这个问题有什么建议吗？

Answer 1

使用

std::vector<std::vector<Entry>> adj_list

条目为

typedef struct {
    int node;
    double weight;

    bool operator == (const int e) const
    {
    return (node == e);
    }
} Entry;

Answer 2

是的，你可以使用一对向量的邻接表来做同样的事情 vector< pair<int, int> > adj[V];

void printGraph(vector<pair<int,int> > adj[], int V) 
{ 
    int v, w; 
    for (int u = 0; u < V; u++) 
    { 
        cout << "Node " << u << " makes an edge with \n"; 
        for (auto it = adj[u].begin(); it!=adj[u].end(); it++) 
        { 
            v = it->first; 
            w = it->second; 
            cout << "\tNode " << v << " with edge weight ="
                 << w << "\n"; 
        } 
        cout << "\n"; 
    } 
}

有向图中邻接表和权重的有效表示

Efficient representation for adjacency list and weights in directed graph

c++

graph

adjacency-list