有向弧列表实现
我正在尝试将图形作为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;
}
没有找到相关结果
已邀请:
1 个回复
森含械