首页 > 代码库 > 浅谈前向星
浅谈前向星
现在才搞懂前向星的遍历,原来是要从后往前的!之后的一切都是以此为基础的。
1.前向星的遍历
看到有一篇blog写的不错:http://blog.csdn.net/acdreamers/article/details/16902023
1 2
2 3
3 4
1 3
4 1
1 5
4 5
那么排完序后就得到:
编号: 1 2 3 4 5 6 7
起点u: 1 1 1 2 3 4 4
终点v: 2 3 5 3 4 1 5
得到:
head[1] = 1 len[1] = 3
head[2] = 4 len[2] = 1
head[3] = 5 len[3] = 1
head[4] = 6 len[4] = 2
但是利用前向星会有排序操作,如果用快排时间至少为O(nlog(n))
如果用链式前向星,就可以避免排序.
特别注意:head[i]保存的是以i为起点的所有边中编号最大的那个,而把这个当作顶点i的第一条起始边的位置.
这样在遍历时是倒着遍历的,也就是说与输入顺序是相反的,不过这样不影响结果的正确性.
比如以上图为例,以节点1为起点的边有3条,它们的编号分别是0,3,5 而head[1] = 5
我们在遍历以u节点为起始位置的所有边的时候是这样的:
for(int i=head[u];~i;i=edge[i].next)
那么就是说先遍历编号为5的边,也就是head[1],然后就是edge[5].next,也就是编号3的边,然后继续edge[3].next,也
就是编号0的边,可以看出是逆序的.
type rec=record pre,en,w:longint; end; var n,x,y,w,tot,i,cc:longint; a:array[0..10000]of rec; head:array[0..10000]of longint; p:integer; procedure adde(u,v,w:longint); begin inc(tot);a[tot].en:=v; a[tot].pre:=head[u];head[u]:=tot; a[tot].w:=w; end; begin readln(n); fillchar(head,sizeof(head),255); fillchar(a,sizeof(a),255); for i:=1 to n do begin readln(x,y,w); adde(x,y,w); writeln(‘Edge ‘,i,‘: ‘,a[i].en,‘ ‘,a[i].pre,‘ ‘,head[i]); end; while true do begin readln(x); p:=head[x]; while p>0 do begin writeln(a[p].en); p:=a[p].pre; end; writeln; end; end.
2.前向星的作用之dijkstra算法的空间优化(时间优化为堆实现)
{链式前向星存储+dijkstra+堆优化} type rec=record pre,en,w:longint; end; rec2=record id,val:longint; end; const inf=233333333; maxm=500000; maxn=10000; var i,j,n,m,s,x,y,z,tot,nd:longint; d,head:array[-maxn..maxn]of longint; a:array[-maxm..maxm]of rec; dui:array[0..4*maxm]of rec2; procedure swap(var a,b:rec2); var t:rec2; begin t:=a; a:=b; b:=t; end; procedure adde(u,v,w:longint); begin inc(tot); a[tot].en:=v; a[tot].pre:=head[u]; head[u]:=tot; a[tot].w:=w; end; procedure swap(var a,b:longint); var t:longint; begin t:=a;a:=b;b:=t;end; procedure up(x:longint);//将一个结点“上浮” begin while x>1 do begin //没有上浮到最顶层 if dui[x].val>dui[x div 2].val then break;//如果上方的结点小于此节点,则暂停上浮 swap(dui[x],dui[x div 2]);//交换上方结点与此结点 x:=x div 2; end; end; procedure down(x:longint);//将一个节点“下沉” var y:longint; begin while x<nd do begin y:=x+x;//y是x的左儿子 if y>nd then break;//x已经沉到底部 if (y<nd)and(dui[y+1].val<dui[y].val) then inc(y);//如果x存在右儿子,且右儿子比左儿子小,则将y赋值到右儿子 if dui[x].val<=dui[y].val then break;//若两个儿子中的较小值仍然比x大,则停止下沉 swap(dui[x],dui[y]);//下沉 x:=y; end; end; function pop():longint; begin pop:=dui[1].id; swap(dui[1],dui[nd]);//将最后的结点(保证其没有儿子)与最顶端交换 dec(nd); down(1);//下沉顶端 end; procedure dijkstra(v0:longint); var i,j,k,minn,u,v,p:longint; vis:array[-maxn..maxn]of boolean; begin fillchar(vis,sizeof(vis),false); for i:=1 to n do d[i]:=inf; d[v0]:=0; dui[1].val:=0; dui[1].id:=v0; nd:=1; for i:=1 to n do begin u:=pop(); while vis[u] and (nd>0) do u:=pop(); vis[u]:=true; p:=head[u]; while p>0 do begin v:=a[p].en; if (not vis[v]) and(d[u]+a[p].w<d[v]) then begin d[v]:=d[u]+a[p].w; inc(nd); dui[nd].id:=v; dui[nd].val:=d[v]; up(nd); end; p:=a[p].pre; end; end; end; begin readln(n,m,s); for i:=1 to m do begin readln(x,y,z); adde(x,y,z); end; dijkstra(s); for i:=1 to n do if d[i]=inf then write(2147483647,‘ ‘)else write(d[i],‘ ‘); writeln; end.
浅谈前向星