2

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

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 算法。

4

3 回答 3

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)（摊销）时间。

于 2012-12-31T20:15:48.523 回答
2

为此，我将使用 std::deque<>，因为您很可能不需要从中间删除元素（这就是为什么有人想要使用 std::list<> 的原因）。它应该比 std::vector<> 或 std::list<> 更有效。拥有连续的内存（向量）和可移动的项目（列表）是有代价的——向量和指针取消引用/列表分散内存的代价高昂的调整。

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

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

于 2012-12-31T20:10:21.703 回答
0

为图创建邻接列表的最佳方法是使用“前向列表”（考虑您的 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);
}
于 2017-12-24T10:59:47.603 回答