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 ごとに成長する構造をコピーしているように思えます。

それが速度低下の原因かもしれません。

データ構造の宣言を示すことができれば、より具体的にすることができます。

編集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));
}
于 2013-04-20T20:15:57.083 に答える