邻接表与前向星

写在前面的话：acdreamers的BLOG给了本文很大启发。

由于在明白了二者的写法之后，发现选择一个掌握就可以了，故只写出了邻接表的模板。

前向星（存边）：

原理：将所有边按照先起点后终点的顺序从小到大排序。记录：对所有点，记录以某点为起点的所有边在 EDGE 数组中的起始位置：head[maxn]，与长度（以该点为起点的边的个数）：len[maxn]。局限：排序操作耗时，故使用链式前向星改进。

链式前向星：

struct EDGE{ int to; int w; int next;//下一个共首边的id }; int cnt;//记录边数，用于加边 int head[maxn];//head[i]表示最后一个以i为起点的边的id

邻接表：

模板（顺序存边）： struct EDGE{ int to; int w; int fo;//former }; EDGE E[num];int cnt;//边数 int tail[maxn];//点数 void INIT(){ memset(tail,-1,sizeof(tail)); cnt = 0; return ; } void ADDEDGE(int u,int v,int w){ cnt++;//from 1 ... cnt E[cnt].to = v; E[cnt].w = w; E[cnt].fo = tail[u]; tail[u] = cnt; return ; } //遍历所有边： for(int i=1;i<=N;i++){//N为点数 for(int j=tail[i];~j;j=E[j].fo){ //... } }