0

グラフをアークリストとして実装しようとしています。この実装は機能しますが、効率はひどいものですが、見逃したものがあれば、それが非常に遅くなりますか？時間は、各ノードから/へのアークを探す平均として測定されました。

struct Arc 
{
    int start;
    int end;
    Arc(int start,int end)
      : start(start),
        end(end)
    { }
};

typedef vector<Arc> ArcList;

class AListGraph
{
public:
    AListGraph(IMatrix* in); //Fills the data from Incidence Matrix
    bool IsE(int va,int vb); //checks if arc exists a->b
    int CountEdges(); //counts all the arcs
    int CountNext(int v); //counts all outgoing arcs from v
    int CountPrev(int v); //counts all arcs incoming to v

private:
    ArcList L;
    int VCount;
};

//Cut out constructor for clarity

int AListGraph::CountEdges() 
{
    return L.size();
}

int AListGraph::CountNext(int v)
{
    int result=0;
    for(ArcList::iterator it =L.begin();it!=L.end();it++)
    {
        if(it->end==v)result++;
    }
    return result;
}

int AListGraph::CountPrev(int v)
{
    int result=0;
    for(ArcList::iterator it =L.begin();it!=L.end();it++)
    {
        if(it->start==v)result++;
    }
    return result;
}
4

1 に答える 1

1

さて、あなたの実装は最悪の可能性があります.in/outエッジを見つけるために、グラフ全体に行きます。

アークリストは本当に必要ですか？通常、隣接リストの方がはるかに効率的です。

隣接リストの単純な実装は、アークのサイズがノードの数であるベクトル > アークを保持することです。

ノード u を指定すると、arcs[u] はすべてのアウト エッジを提供します。エッジでも最適化する方法を理解できます。

于 2011-04-11T17:42:57.557 に答える