在C ++中使用STL创建邻接列表的有效方法是什么？

Question

我目前使用的向量矢量如下：

typedef pair<int, int> vertex;
vector < vector<vertex> > adj_list(n); // n is number of vertices

// Input graph
for (int i = 0; i < edges; i++ )
{
   cin >> source >> target >> weight;
   vertex v(target, weight);
   adj_list[source].push_back(v);
}

是列表矢量即。

vector < list<vertex> > adj_list(n);

更好的选择？如果是，为什么？我主要关心的是有效地创建邻接列表，并能够快速读取连接到特定顶点的所有顶点，以实现Dijkstra算法。

Answer 1

为此我会使用std :: deque <>，因为你很可能不需要从中间删除元素（这就是为什么有人想要使用std :: list <>）。它应该比std :: vector <>或std :: list <>更有效。具有连续的内存（向量）和可移动的项目（列表）具有它的价格 - 用于列表的向量和指针解除引用/分散的内存的昂贵的调整大小。

另见：http://www.gotw.ca/gotw/054.htm

请注意，如果您的目标是算法竞赛，您可能会对这种基于STL的数据结构可以采用多少内存感到惊讶。

Answer 2

您的需求是快速插入和快速迭代。渐渐地，vector<vector<T> >和vector<list<T> >之间没有区别：

• list<T>是一个双向链表，所以每个插入都需要O(1)时间，迭代每个元素需要O(1)时间。
• vector<T>是一个数组，实现使得每个插入都需要O(1)（摊销）时间[1]，并且迭代需要每个元素使用O(1)时间。

操作的常量可能不同，但这是你必须通过分析找到的东西。

然而，空间效率会有利于vector<vector<T> >，因为vector<list<T> >中的每个元素也带有前向和后向指针。所以你可能想要使用vector<vector<T> >，但是你可以避免在常见情况下重新分配（以节省时间），但不要保留太多（以节省空间）。

对于外部矢量，您可以在其上调用.reserve(n)，其中n是图中顶点的数量。

对于内部向量，它有点难度，它实际上取决于您的数据如何被馈送到此过程。

---

[1] vector<T>的实施应该在每次重新分配时使其容量加倍，因此重新分配所花费的时间是O(1+2+4+...+n/4+n/2+n) = O(n(1/n+2/n+4/n+...+1/4+1/2+1)) <= O(1+1/2+1/4+...)) = O(2n)。因此分布在n元素上，插入需要O(1)（摊销）时间。

Answer 3

为图形创建邻接列表的最佳方法是使用“转发列表”（考虑您在C ++中的语言）。欲了解更多信息，请访问https://www.geeksforgeeks.org/forward-list-c-set-1-introduction-important-functions/

请阅读下面的代码以获取“转发列表”的说明注意： - 在阅读代码之前，请正确理解STL库提供的用于“转发列表”的实用程序功能。

/* The code has been designed to give output only if ENTER key is pressed, 
before that it'll keep 
recieving inputs from the user. So provide all your inputs in one line 
seperated by whitespaces. */

                      /* This is the implementation of DFS */

#include<iostream>
#include<forward_list>
using namespace std;

class graph{
    private:
        int noOfVertices;
        forward_list<int> *adj;
        void dfsUtil(int v, bool *visited);
    public:
        graph(int v);
        void addEdge(int s, int d);
        void dfs(int startVertex);
};

graph::graph(int v){
    noOfVertices = v;
    adj = new forward_list<int>[noOfVertices];
}

void graph::addEdge(int s, int d){
    adj[s].push_front(d);       
}

void graph::dfs(int startVertex){
    bool *visited = new bool[noOfVertices];

    for(int i = 0 ; i < noOfVertices ; i++){
        visited[i] = false;
        adj[i].reverse();
    }

    dfsUtil(startVertex, visited);
}

void graph::dfsUtil(int v, bool *visited){
    forward_list<int>::iterator i; 
    visited[v] = true;
    cout << v << " ";

    for(i = adj[v].begin() ; i != adj[v].end() ; i++){
        if(!visited[*i])
            dfsUtil(*i, visited);
    } 
}

int main(){
    int v, s, d;
    cin >> v;
    graph g(v);

    while(cin.peek() != '\n')
    {
        cin >> s >> d;
        g.addEdge(s, d);
    }

    g.dfs(2);
}