基于有序双循环链表的低代价最短路径树快速算法

低代价最短路径树是一种广泛使用的多播树。在FLSPT算法的基础上,通过选择有序双循环链表作为待发展节点序列Q的运算与存储中心,提出了基于有序双循环链表的低代价最短路径树快速算法DKFLSPT。该算法构造的最短路径树与FLSPT算法构造的最短路径树具有相同的性能,利用有序双循环链表的局部性原理来达到改进节点路径最小值的搜索过程。随机网络模型的仿真结果表明,DKFLSPT算法效率平均可以提高19%。

基于对称边双循环链表的三角格网表示与实现

针对三角格网提出一种对称边双循环链表结构,对称边是指一条边由2个有向边表示,双循环链表是指这些线段分别以其2个端点为源点,通过同源点关系使线段之间能够顺时针与逆时针方向关联。该结构能方便地维护三角格网拓扑结构。给出三角格网中几个基本操作的伪码实现。与通用的多边形格网结构相比,它具有理解容易、操作方便、使用内存少的优点。

Delaunay三角网表示和点删除方法

对于三角网的表示方法,提出了一种双循环链表结构,这种结构能够方便的表示三角网的边拓扑和面拓扑信息,以及多边形结构。基于这种结构,对三角网点删除算法进行了改进。以前的点删除算法是基于连续的凸耳删除,提出的方法是基于多边形边的构建方法,利用D-三角网的空外接圆属性。与其它方法相比,这种方法具有容易理解,效率高的优点。

二维Delaunay三角网的动态更新

对于三角格网的动态更新,提出了一种对称边双循环链表结构,提供了如何实现这种结构,如何创建三角形,动态插入和删除点等操作的代码和伪码实现。该结构具有理解容易、操作简单、使用内存少的特点,能够快速地查找和维护三角网的拓扑结构,并且可根据实际需求进行扩充。