链式向前星与Trajan算法

模板：

加边：

struct node{int to,next,w;
}edge[1000];
int head[1000],cnt;
void add(int u,int v,int w)
{++cnt;edge[cnt].to = v;edge[cnt].next = head[u];edge[cnt].w = w;head[u] = cnt;
}

e[i].to是指第i条边的终点，e[i].next是指与第i条边同起点（即u）的下一条边的储存下标（0时退出），e[i].w即第i条边的权重，head[u]是指u为起点的存储下标。

遍历：（遍历以u为起点的边）

for(i=head[u];i;i=edge[i].next)

i开始为第一条边，每次指向下一条(以0为结束标志)  （若下标从0开始，next应初始化-1）

假设输入1 2; 1 3; 1 5，即head一直更新，head[1] = 1；head [1] = 2；head[1] = 3，访问时其实是倒着访问的，先访问edge[3]，然后i更新为edge[i].next即前一个head[1]即2，访问edge[2]，再然后i更新为1，访问edge[1]。

推荐博客：

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！