摘要
经典的Prim和Kruskal算法不能求解赋权有向图最小生成树。针对有向图存在最小生成有向树的情形,给出了有向图最小生成树的数学模型。根据有向树顶点入度d(v)1-≤的特点,设计了以u为根的有向树的编码和解码,提出了应用粒子群优化算法求解赋权有向图最小生成树问题的策略,并在此基础上设计了相应的粒子群优化算法流程。
The classical Prim and Kruskal algorithm cannot solve the problem of the minimum spanning tree.Aiming at the existence of minimum spanning tree in the directed graph,the mathematical model of the minimum spanning tree of directed graph is given.Based on the characteristics of a vertex to the tree into the degree,the encoding and decoding for root directed treeare designed and the particle swarm optimization algorithm was proposed to solve empowerment strategies in the directed graph minimum spanning tree problem and the corresponding particle swarm optimization algorithm flow is designed.
作者
严坤妹
YAN Kunmei(The Foundation Department, Fujian Business University, Fuzhou Fujian 350012)
出处
《福建师大福清分校学报》
2017年第5期16-21,共6页
Journal of Fuqing Branch of Fujian Normal University
基金
福建省教育厅科技项目(JB10221)
关键词
赋权有向图
最小生成树
粒子编码
启发式算法
weighted directed graph
minimum spanning tree
particle coding
heuristic algorithm
