有向图圆弧列表实现

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

嗯，你的实现可能是最糟糕的:为了找到输入/输出边，你要遍历整个图。

你真的需要一个圆弧列表吗？通常邻接列表的效率要高得多。

邻接表的一个天真的实现是保持一个矢量>圆弧，其中圆弧的大小是节点的数量。

给定一个节点u，arcsu会给出所有的外边。你也可以弄清楚如何优化它的内部边缘。