链式前向星

实现

//链式前向星
//定义全局初始化为0
int cnt_edge, head[MAX_N], next[MAX_M], to[MAX_M], w[MAX_M];
// 加边 
inline void add_edge(int a, int b, int c) { 
    to[++cnt_edge] = b;
    w[cnt_edge] = c;
    next[cnt_edge] = head[a];
    head[a] = cnt_edge;
    return ;
}

访问每个节点连接的边

for (int u = 1; u <= n; ++u) { //枚举节点编号
    for (int i = head[u]; i; i = next[i]) { //枚举该点边的编号
        to[i]; //获得这条边执行的节点
    }
}

解释

• int cnt_edge; //边的编号
• to[++cnt_edge] = b; //记录这条边的指向节点
• w[cnt_edge] = c; //这条边的权值
• nxt[cnt_edge] = head[a]; //以a为起点的上一条边
• head[a] = cnt_edge; //以a为起点的最好一条边的编号