链式向前星

实质上就是一种用链表实现的邻接表，保存以每个点作为起点的边

组成：

1. idx 记录边的序号

2. 邻接表包括四个数组：e、w、ne、h

e[idx] = b：表示第 idx 条边通向 b 点
w[idx] = c：表示第 idx 条边的权值为 c
ne[idx] = h[a]：表示以a为起点的第 idx 条边的下一条边为 h[a]（-1表示无边）
h[a] = idx++：表示点 a 的上一条边为 idx

其中 h 数组的大小是点数，其他三个数组的大小都是边数。

声明数组：

int e[M], w[M], ne[M], h[N];

初始化：

memset(h, -1, sizeof h);

建边操作：

// 加入有向边 (a, b)，权值为 c
void add(int a, int b, int c)
{
     e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

访问操作:

// 访问从x出发的所有边
for (int i = h[x]; ~i; i = ne[i])
{
    int y = e[i], z = w[i];
    // 找到了一条有向边 (x, y)，权值为z
}

对图或树进行dfs操作：

因为每个点和每条边都是访问一次，所以时间复杂度为O(n + m)

void dfs(int x)
{
    vis[x] = 1; // 记录x被访问过
    for (int i = h[x]; ~i; i = ne[i]) {
        int y = e[i]; // 当前表头可以到达的点
        if (vis[y]) continue;
        dfs(y);
    }
}

参考博客