Digraph arc list implementation

Question

나는 Arc List로 그래프를 구현하려고하는데,이 구현이 효과가 있지만 끔찍한 것은 무엇이든 그리워서 그렇게 느리게 만드는거야? 시간은 각 노드에서 /로가는 호를 찾는 평균으로 측정되었습니다.

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; 
} 

Answer 1

글쎄, 당신 실현하는 것이 최악의 수 있습니다 : 당신이 전체 그래프를 통해 이동 한 모서리를에서 /을 찾기 위해.

호리스트가 정말로 필요합니까? 일반적으로 인접성 목록이 훨씬 효율적입니다.

인접성 목록의 순진한 구현은 아크의 크기는 노드 수있는 벡터> 호를 유지하는 것입니다.

유, 호는 [유] 당신에게 모든 아웃 가장자리을 제공하는 노드를 감안할 때. 가장자리에서 최적화하는 방법도 알아낼 수 있습니다.