链式前向星

这里的边集数组和链式邻接表中的类似，是一维的，用结构体来存每一个边，每一个边存下 终点，边权，同父节点的另一条边 注意看下图的绿色箭头
表头数组，用来存储每个点的第一个 出边 的编号
边的编号来自于 idx
如下图进行连接

链式前向星的复杂度

• 时间复杂度
• 空间复杂度

链式前向星的使用场景

各种图，能处理反向边，但是它这个表示起来比较麻烦
题目要处理一个点的相邻边，因为这里边集数组以点为中心，维护了他的邻边

链式前向星的实现

建图

定义边集数组

struct edge{int v,w,ne;};
edge e[M];

定义边的编号

int idx;

定义表头数组，存储每一个点第一条出边的编号

int h[N];

int main() {
  cin >> n >> m;
  memset(h,-1,sizeof h); //表头数组初始化为-1
  for(int i = 1; i<=m;  i++) {
    cin >> a >> b >> c;
    add(a,b,c);
    add(b,a,c);
  }
  dfs(1,0); //1是入口，0是判断是否死循环的父节点
}

添加元素

void add(int a, int b, int c) { //一个边的三个要素，a是入口，b是终点，c是边权
  e[idx] = {b,c,h[a]}; //e是边集数组，存储每一个边的信息，idx是边的编号，从0到n-1，自然排序，给边编号添加索引。a是这个边的进入方向，b是这个边的出口，h[a]是父节点的另一边，也就是第一条出边 
  h[a]=idx++;//把边的编号和节点的出边对应
}

遍历

void dfs(int u, int fa) {
  for(int i = h[u]; ~i; i=e[i].ne) { //i是入口u的第一条出边，只要它还有边，进入u的另一条边
    int v = e[i].v, w=e[i].w;
    if( v == fa ) continue; //入口节点u的父节点来过，那么跳过
    cout << u << v << w;
    dfs(v,u);//终点变成新的入口
  }
}