c++ - C++中创建图形adt的执行时间

Question

一般来说，创建一个无向图 adt 应该需要很长时间吗？

如果我有一个包含 40 个节点的图，并且每个节点都连接到 20% 的其他节点，当我的程序试图将这些节点连接在一起时，它就会停止。

我真正能达到的最大密度是 20 个节点的 20%。我将顶点链接在一起的代码如下所示:

    while(CalculateDensity()){
    LinkRandom();
    numLinks++;
}

void LinkRandom(){
int index = rand()%edgeList.size();
int index2 = rand()%edgeList.size();
edgeList.at(index).links.push_back(edgeList.at(index2));
edgeList.at(index2).links.push_back(edgeList.at(index));
}

有什么方法可以更快地做到这一点？

编辑:这里是数据结构声明的地方:

    for(int i=0; i<TOTAL_NODES; i++){
    Node *ptr = new Node();
    edgeList.push_back(*ptr);       //populate edgelist with nodes
}
cout<<"edgelist populated"<<endl;
cout<<"linking nodes..."<<endl;
while(CalculateDensity()){
    LinkRandom();
    numLinks++;
}

Answer 1

在我看来，每次 push_back 都在复制一个不断增长的结构。

这可能是速度缓慢的原因。

如果你能展示数据结构声明，我可以尝试更具体一些。

编辑 我仍然想念 Node 声明，不过我会尝试将 edgeList 更改为指向 Node 的指针列表。然后

// hypothetic declaration
class Node {
  list<Node*> edgeList;
}

//populate edgelist with nodes
for(int i=0; i<TOTAL_NODES; i++)
  edgeList.push_back(new Node());
....

void LinkRandom(){
  int index = rand()%edgeList.size();
  int index2 = rand()%edgeList.size();
  edgeList.at(index)->links.push_back(edgeList.at(index2));
  edgeList.at(index2)->links.push_back(edgeList.at(index));
}