前向星和后向星

来自NOCOW

跳转到：导航, 搜索

前向星

构造方法如下：

读入每条边的信息

将边存放在数组中

把数组中的边按照起点顺序排序

前向星就构造完了

通常用在点的数目太多，或两点之间有多条弧的时候。

一般在别的数据结构不能使用的时候才考虑用前向星。

除了不能直接用起点终点定位以外，前向星几乎是完美的。 //——By Clarkok 如果是前向星，则可以用起点定位，如果是后向星，则可以用终点定位，可以再开一个数组s，s[i]表示以i为起点的边在边的数组中的起始位置（边已经排序过了），这个数组可以用O(e)的复杂度求出，Pascal代码以及更多解释在链接里面文章的中间部分。链接： http://www.clarkok.com/blog/?p=304

链式前向星

参见http://malash.me/200910/linked-forward-star/

[编辑]

图论及图论算法

图 - 有向图 - 无向图 - 连通图 - 强连通图 - 完全图 - 稀疏图 - 零图 - 树 - 网络