-
题名最大流有效算法的实用化设计与动态实现
- 1
-
-
作者
李洪波
张吉赞
-
机构
烟台师范学院数学与信息学院
-
出处
《计算机工程与设计》
CSCD
北大核心
2006年第22期4255-4258,共4页
-
基金
山东省教育厅科技计划基金项目(J05C05)
-
文摘
对一个O(|V|3)的最大流有效组合算法进行了研究,提出了用广度优先搜索的方法实现该算法的实用化设计方法。给出了该实用化方法具有的性质,利用该性质,采取正逆双向广度优先搜索的方式,按路径长度递增的次序依次形成各辅助网L,从而计算各辅助网L的最大流,最终组合成最大流。设计了十字双向链表存储结构,该结构采用了独特的动态双向邻接表存储辅助网L,这样即保留有用信息并删除无用信息,又保证最大流有效算法的时间复杂度仍为O(|V|3),从而实现了动态存储。
-
关键词
最大流
辅助网L
正逆广度优先
十字双向链表
动态实现
-
Keywords
max-flow problem
auxiliary net L
positive and contradictory bread-first search
cross doubly linked list
dynamic implement
-
分类号
TP331
[自动化与计算机技术—计算机系统结构]
-
