图的存储之链式前向星
在学最大流时看到了这个东西，感觉名字听起来很酷，于是就研究了一下。
前向星：一种数据结构，以储存边的方式来存储图。构造方法如下：读入每条边的信息，将边存放在数组中，把数组中的边按照起点顺序排序(可以使用基数排序，如下面例程)，前向星就构造完了。通常用在点的数目太多，或两点之间有多条弧的时候。一般在别的数据结构不能使用的时候才考虑用前向星。除了不能直接用起点终点定位以外，前向星几乎是完美的。【引自百度百科】
链式前向星存储边的代码：
void add(int u,int v,int w)
{
edge[cnt].c= w;
edge[cnt].to = v;
edge[cnt].next = head[u];
head[u] = cnt++;
}
介绍一下这里面的一些东西：
edge.c——权重
edge.to——这条边的终点
edge.next——它指向同一起点的上一条边
那head数组是干啥的呢——head[u]代表以u为起点的边上一次出现的边的编号
我们可以使用它进行一个bfs
然后就没什么好讲的了……
版权声明：本文为yzxverygood原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。