前向星

首先，这名字并没什么特殊含义，不要问我为什么.....

贴一段代码：

1 void add(int u,int v,int w)
2 {
3     edge[cnt].w = w;//u指向v的边权值 
4     edge[cnt].to = v;//u指向谁 
5     edge[cnt].next = head[u];//上一条u指向某一个节点的边在edge的哪里,看清楚是上一条
6     head[u] = cnt++; //这里记录了边的位置,cnt++的意思是先赋值，再加一 
7 }

以上是添边的过程,head[i]的意思是i指向某一个节点,这个节点是最后加入的，然后往上推，edge[head[i]].next(这是倒数第二条)，edge[edge[head[i]].next].next(这是倒数第三条).....

head要初始化为-1,作为边界,因为往上推到第一条边往上就没有边了.

0其实也可以,但是cnt要从1开始,这里统一用-1,下面有一个用-1的小理由

memset(head,-1,sizeof(head));

我们在遍历以u节点为起始位置的所有边的时候是这样的:

 for(int i=head[u];~i;i=edge[i].next)

-1转成二进制为11111111....(这个一有多长取决于你用什么数据类型)

然后取反就全部变成0；

如果你用0，那么就要这要写

i ！= 0;

求轻喷.......

前向星

原文：http://www.cnblogs.com/sorhri/p/star.html