最大流有效算法的实用化设计与动态实现

对一个O(|V|3)的最大流有效组合算法进行了研究,提出了用广度优先搜索的方法实现该算法的实用化设计方法。给出了该实用化方法具有的性质,利用该性质,采取正逆双向广度优先搜索的方式,按路径长度递增的次序依次形成各辅助网L,从而计算各辅助网L的最大流,最终组合成最大流。设计了十字双向链表存储结构,该结构采用了独特的动态双向邻接表存储辅助网L,这样即保留有用信息并删除无用信息,又保证最大流有效算法的时间复杂度仍为O(|V|3),从而实现了动态存储。