摘要： 对有向图边集数组存储结构进行修改和扩展，在其基础上利用栈机制实现有向图操作的基本算法：生成算法和拓扑排序算法。该扩展结构能克服边集数组存储结构不便于图操作的缺点，通过空间的重复使用，有效地节约存储空间，通过静态存储空间实现图的表示，提高算法的稳定性。
关键词:
有向图,
边集数组,
扩展边集数组,
静态链栈,
拓扑排序
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
中图分类号:
潘大志;刘志斌. 有向图扩展边集数组存储结构的实现[J]. 计算机工程, 2009, 35(22): 38-39.
PAN Da-zhi; LIU Zhi-bin. Realization of Extended Edge-collection Array Memory Structure of Directed Graph[J]. Computer Engineering, 2009, 35(22): 38-39.