链式前向星

定义

---

链式前向星

链式前向星是邻接表的一种特殊实现，通过数组来模拟链表，更为高效。

Tips

在存储无向图时，请注意将数组大小开到2倍。

模版

---

int N, M;
int head[N], nxt[N], cnt;
// head为每个节点的第一条边，默认为-1
// nxt为每条边的下一条边，下一条边为-1时遍历结束
struct edge  
{  
    int to, w; // 终点和边权
} edges[M];  
 
void init() // 初始化
{
	cnt = -1;
	for(int i = 0; i < N; i++)
		head[i] = -1;
}
 
void add(int u, int v, int w)  
{
    nxt[++cnt] = head[u];  // edges[++cnt]为新的边，原来的第一条边成为新的边的下一条边
    head[u] = cnt;  // 新的边成为u的第一条边
    edges[cnt].to = v;  // 设置终点
    edges[cnt].w = w;  // 设置边权
}
 
void traverse_edges(int u) // 遍历节点u的出边
{
	for(int i = head[u]; i != -1; i = nxt[i])
	{
		int v = edges[i].to;
		int w = edges[i].w;
	}
}