我正在尝试将图形实现为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;
}
嗯,您的实现可能是最糟糕的:为了找到遍及整个图的输入/输出边缘。
您真的需要弧列表吗?通常,邻接表效率更高。
邻接表的简单实现是保持向量>弧,其中弧的大小是节点数。
给定一个节点u,arcs [u]给您所有的外边缘。您也可以找出如何针对边缘进行优化。