对比邻接表的优劣

优:

• 运行速度比邻接表快

劣:

• 没有邻接表灵活简洁

构建

struct edge
{
	int next,v,w;
}g[N];
int head[N],tot=0;
void add(int u,int v,int w)
{
	g[++tot]={head[u],v,w};
	head[u]=tot;
}

遍历

for(int i=head[u];i;i=g[i].next)
{
	int v=g[i].v,w=g[i].w;
	
}

不同点

在邻接表中

每加一条边,就会在 g[u] 进行

push_back({v,w}) (当然,也可以 emplace_back({v,w}) )

点都是加在后面

子结点遍历顺序:

$v_1,v_2,...,v_n$

---

在链式前向星中

点都是往前加

说白了就是越后面的越先遍历

子结点遍历顺序:

$v_n,v_{n-1},...,v_1$