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

摘要：

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

关键词：最大流、辅助网L、正逆广度优先、十字双向链表、动态实现

所属期刊栏目：27

分类号：TP331(计算技术、计算机技术)

资助基金：山东省教育厅资助项目J05C05

在线出版日期：2006-12-25（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：4255-4258