首页 > 代码库 > 邻接表的使用及和vector的比较
邻接表的使用及和vector的比较
这几天碰到一些对建边要求挺高的题目。而vector不好建边,所以学习了邻接表。。
下面是我对邻接表的一些看法。
邻接表的储存方式
邻接表就是就是每个节点的一个链表,并且是头插法建的链表,这里我们首先用数组进行模拟。。first [u],next[e]分别表示节点u的第一条边的编号,第e条边的下一条边的编号。。则实现代码为:
邻接表就是就是每个节点的一个链表,并且是头插法建的链表,这里我们首先用数组进行模拟。。first [u],next[e]分别表示节点u的第一条边的编号,第e条边的下一条边的编号。。则实现代码为:
next[e]=head[u[e]]; head[u[e]]=e;
然后如果和结构体进行搭配使用会非常使用。。
struct Edge { int to,val,next; }edge[maxn]; int head[maxn]; void addedge(int x,int y,int val) { edge[++cnt].to=y; edge[cnt].val=val; edge[cnt].next=head[x]; head[x]=cnt; }而相应的邻接表的遍历方式也就出来了
for(int i=head[x],i!=-1;i=next[i])第二种遍历方式为:
for(int i=head[x],i!=-1;i=edge[i].next)而vector也可以达到与邻接表相同的效果,vector容器实则是一个动态数组,但是与邻接表不同的是,它是顺序存储的.那么存储和遍历都很简单
遍历for(int i=0;i<vec[x].size();i++)表示形式就是跟数组一模一样。。
自己的一些理解,请指正。。。
邻接表的使用及和vector的比较
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。