在我们切题的时候经常会遇到一个问题...图很大,边很少.很显然这样用矩阵存图就很不值得了!而且很可能会因为这个而是你的程序爆掉。遇到这个问题大部分的OIer们都会去用链表来存数据...但是,作为沙茶的我..并不喜欢用链表....于是...我们就可以用前向星~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
首先我们来看,普通的矩阵存图存的是map[i,j] [即i到j的权值].如果..有100000个点的话...就悲剧了..这样就是100000*100000
然后,前向星是保存边,一共申请三个数组:a[i] b[i] e[i] 他们分别表示：第i条边的起点编号，第i条边的终点编号，第i条边的权值。 于是我们就可以这样读数据： -------------------------------- readln(n,m); for i:=1 to m do readln(a[i],b[i],e[i]);
---------------------------------
然后就qsort(a,1,m),为的是让这些起始编号有序(让终止编号有序也可以,看个人喜好了...不过一般都是排起始编号).
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
这就是前向星了.其实也是非常的简单.空间复杂度视边的个数(也就是m)而定.
我们可以来看一道题:
-------------------------------------------------------------------------------------------------------------------- Aim Netbar
(netbar.pas/c/cpp) 【问题背景】
绵阳中学以人数众多而闻名。三个年级共有10000 多人，学生多了附近的网吧也多。
Mzoiers 都热衷于Dota，可学校的机子配置相当差(评测服务器除外)，根本不能玩
Dota，那就只有去网吧。星期天到星期五都是晚上 10：20 才下晚自习，几乎没时间玩。
然而星期六下午放假是绝好的时间，但是学校人多啊，一放学去网吧的人就开始狂奔，竞争
之激烈，抢到机子的难度非常之大。往往在我们到达网吧之前都坐满了。
学校到网吧的路是错综复杂的， 以致于到一个自己想去的网吧都有非常多的路线可以选
择，而路线的长度又不相同，这样就决定了要花费的时间，因此想要尽快到达，选择一条最
佳的线路是很有必要的。 【问题描述】
为了简化问题，我们把学校与周边的网吧看做图中的顶点，学校与网吧，网吧与网吧之
间的路线看做边，每个边都有一个权，表示我们走完这条路的时间，由于放学人流量大，如
果反向走会有危险，因此这是一个有向图。
我的的学校在 S点，想要去的网吧在 T点。你的任务就是选择一条最佳路线，使得从
学校到目的地网吧的时间最短，你只需要输出最短到达时间即可。 【输入文件】
netbar.in 中共有M+2 行数据
第一行两个整数 N，M，表示点数和边数。
然后M行每行3 个正整数(u，v，t)，表示有一条可由u 到v耗时为 t的边。 最后一行两个正整数S、T。 【输出文件】
netbar.out 中，只有一行，一个整数表示最短时间。如果 S、T之间不存在通路则输
出“No Solution!”(双引号不输出， “!”为西文标点)。 【输入样例】 44 1 23 2 4 10 1 35 3 45 14
【输出样例】 10
【数据规模】
对于30％的数据保证有 1 -------------------------------------------------------------------------------------------------------------------- 这道题很明显就是用SPFA，但是由于这个数据规模，我们只能有两种方法：1.链表 2.前向星 这里链表就不再赘述...我们的主题是前向星. 恩...直接插程序吧.... ~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~ var a,b,e:array[1..10000] of longint; vis:array[1..20000] of boolean; q,d,f:array[1..20010] of longint; n,m,i,s,t:longint; procedure qsort(l,r:longint); var i,j,x,y:longint; begin i:=l; j:=r; x:=a[(l+r) shr 1]; repeat while a[i] if i procedure spfa(s:longint); var i,k,l,t:longint; begin fillchar(vis,sizeof(vis),0); for i:=1 to n do d[i]:=maxlongint; d[s]:=0; l:=0; t:=1; q[1]:=s; vis[s]:=true; repeat l:=l mod 10000 +1; k:=q[l]; for i:=f[k] to f[k+1]-1 do if d[k]+e[i] d[b[i]]:=d[k]+e[i]; if not vis[b[i]] then begin t:=t mod 10000 +1; q[t]:=b[i]; vis[b[i]]:=true; end; end; vis[k]:=false; until l=t; end; procedure init; begin assign(input,'netbar.in');reset(input); assign(output,'netbar.out');rewrite(output); readln(n,m); for i:=1 to m do readln(a[i],b[i],e[i]); qsort(1,m); for i:=1 to m do if f[a[i]]=0 then f[a[i]]:=i; f[n+1]:=m+1; for i:=n downto 1 do if f[i]=0 then f[i]:=f[i+1]; readln(s,t); end; procedure terminate; begin close(input); close(output); halt; end; begin init; spfa(s); writeln(d[t]); terminate; end. ~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~- 前向星的用途：一般是用来优化SPFA的。 前向星的缺点:不能用起点直接终点定位,如果程序必须要定位的话,我们也不能示弱,最好不要用朴素的方法来定位，这样很花时间的。最好，就是用二分的思想进行查找(也就是常说的对半查找)： {伪代码} Function binsearch(i,j,x);//在i,j区间中找x. { if a[(i+j)shr 1]>x then exit(binsearch(i,(i+j))shr 1) else exit(binsearch((i+j)shr 1 +1,j)); } 一种数据结构，以储存边的方式来存储图。 构造方法如下： 读入每条边的信息 将边存放在数组中 把数组中的边按照起点顺序排序 前向星就构造完了 通常用在点的数目太多，或两点之间有多条弧的时候。 一般在别的数据结构不能使用的时候才考虑用前向星。 除了不能直接用起点终点定位以外，前向星几乎是完美的。 --------------------------------------------------------------------------------------------------------- 最基本的前项星优化的spfa(有向图)，复杂度O(ke). var a,b,e:array[1..1000] of longint; vis:array[1..2000] of boolean; q,d,f:array[1..2001] of longint; n,m,i,s,t:longint; procedure qsort(l,r:longint); var i,j,x,y:longint; begin i:=l; j:=r; x:=a[(l+r) shr 1]; repeat while a[i]