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

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

作　　者：潘大志[1,2] 刘志斌[2] 

机构地区：[1]西华师范大学数学与信息学院,南充637000 [2]西南石油大学理学院,成都610041

出　　处：《计算机工程》2009年第22期38-39,43,共3页Computer Engineering

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

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

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

分 类 号：TP301[自动化与计算机技术—计算机系统结构]