1

一般来说，创建一个无向图 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++;
}
4

1 回答 1

1

在我看来，您正在复制每个 push_back 的不断增长的结构。

这可能是缓慢的原因。

如果您可以显示数据结构声明，我可以尝试更具体。

编辑我仍然错过了节点声明，不过我会尝试将 edgeList 更改为指向节点的指针列表。然后

// 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));
}
于 2013-04-20T20:15:57.083 回答