Prim算法的一种优化实现  

On the Optimizing Realization of the Prim Algorithm

作　　者：潘大志[1] 陈友军[1] 

机构地区：[1]西华师范大学数学与信息学院,四川南充637009

出　　处：《西华师范大学学报（自然科学版）》2011年第1期63-66,共4页Journal of China West Normal University(Natural Sciences)

基　　金：四川省教育厅青年基金(10ZB018)资助项目

摘　　要：为网中的顶点专门设计了一种数据结构将V-U集合中顶点构成了静态双向循环链表,让Prim算法真正实现了只在V-U集合中去实现选取最短边的操作,让Prim算法得到优化,提高了运算效率.利用同一顶点位于U和V-U的不同时刻,该数据结构使存储空间得到了充分的使用,提高空间的利用率.This paper designs a special data structure for vertices in the network.Through the vertex array,the vertices in V-U set constitute a static bi-directional circular linked list,so Prim algorithm realizes truly operation selecting the shortest side through the V-U set,to improve the efficiency of the operation.Using the same vertex lying in U and V-U at the different moments,the specail data structure makes storage space fully used to improve space utilization.

关 键 词：网 PRIM算法 最小生成树 双向循环链表 静态链表 

分 类 号：TP311.12[自动化与计算机技术—计算机软件与理论]