计算机工程 ›› 2009, Vol. 35 ›› Issue (22): 38-39.doi: 10.3969/j.issn.1000-3428.2009.22.013

• 软件技术与数据库 • 上一篇    下一篇

有向图扩展边集数组存储结构的实现

潘大志1,2,刘志斌2   

  1. (1. 西华师范大学数学与信息学院,南充 637000;2. 西南石油大学理学院,成都 610041)
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2009-11-20 发布日期:2009-11-20

Realization of Extended Edge-collection Array Memory Structure of Directed Graph

PAN Da-zhi1,2, LIU Zhi-bin2   

  1. (1. College of Mathematic and Information, China West Normal University, Nanchong 637000; 2. School of Sciences, Southwest Petroleum University, Chengdu 610041)
  • Received:1900-01-01 Revised:1900-01-01 Online:2009-11-20 Published:2009-11-20

摘要: 对有向图边集数组存储结构进行修改和扩展,在其基础上利用栈机制实现有向图操作的基本算法:生成算法和拓扑排序算法。该扩展结构能克服边集数组存储结构不便于图操作的缺点,通过空间的重复使用,有效地节约存储空间,通过静态存储空间实现图的表示,提高算法的稳定性。

关键词: 有向图, 边集数组, 扩展边集数组, 静态链栈, 拓扑排序

Abstract: This paper realizes the revision and extension of the edge-collection array memory structure expressing the directed graph, and on the basis of the structure, it uses of the stack to achieve the basic algorithms of directed graph: generating algorithm and topological sorting algorithm. The realization of the basic operation algorithms manifests this expansion structure can overcome the edge-collection array memory structure is not to be advantageous for the graph operation, save the storage space effectively through the spatial repeated use, and enhance the algorithm the stability through the static storage space to express graph.

Key words: directed graph, edge-collection array, extended edge-collection array, static-linked stack, topological sort

中图分类号: