来源

横向比较

代码

来源

链式前向星是ssfz神牛Malash创造的（至少Baidu上没有搜到）名词，或许这种数据结构有其他更加正规易懂的名字，但我还是没有搜到。（有一个资料称之为加上next数组前向星，但这个名字实在不好） 该数据结构可能是Jason911神牛或其他神牛发明的。

横向比较

如果说邻接表是不好写但效率好，邻接矩阵是好写但效率低的话，前向星就是一个相对中庸的数据结构。前向星固然好些，但效率并不高。而在优化为链式前向星后，效率也得到了较大的提升。虽然说，世界上对链式前向星的使用并不是很广泛，但在不愿意写复杂的邻接表的情况下，链式前向星也是一个很优秀的数据结构。

代码

模板

#include<iostream>

#include<string.h>

#include<limits>

const int maxn = 10005;

const int maxm = 1000005;//edge

using namespace std;

int n;

struct node

{

int to,next;

// int value ,from,

};

node edge [maxm];

int box[maxn];//box[i] 节点i下第一条边

int ecnt;//边的个数

void _make_map(int from,int to)

{

edge[ecnt].to=to;//to 节点

edge[ecnt].next=box[from];//同节点下该边下一跳边

box[from]=ecnt++;// 节点from的第一跳边

}

void make_map(int from,int to)//双向变

{

_make_map(from,to);

_make_map(to,from);

}

for(int i=box[u];i+1;i=edge[i].next);

//遍历父节点为u的所有边

int main()

{

while(scanf("%d",&n)!=EOF)

{

ecnt=0;

int i;int u[100],v[100];

for(i=0;i<n;i++)

{

scanf("%d%d",&u[i],&v[i]);

}

for(i=0;i<n;i++)

make_map(u[i],v[i]);

//for(int i=box[u];i+1;i=edge[i].next)

//{

//int v=edge[i].to;

//if(p==v)continue;

//}

}

}

return 0;

}