有向图的扩展邻接矩阵存储模式研究.pdfVIP

2007年第3期 九江学院学报 (总第140期) No，3，2007 Journal of Jiujiang University (Sum NO 14JD) 有向图的扩展邻接矩阵存储模式研究 邓长寿 任红卫 (九江学院信息科学与技术学院 江西九江 332005) 摘要：本文对于有向图的存储模式进行了。研究。在邻接矩阵和邻接表的基础之上，提出 了一种新的有向图存储结构一扩展邻接矩阵 并研究了建立该矩阵的算法。扩展邻接矩阵存 储模式同时具有邻接矩阵、邻接表和十字链表三种传统存储结构分别可以快速从有向图获 得不同信息的优点。扩展邻接矩阵为有向图的应用，提供了一种高效的存储方案。 关键词：有向图；邻接矩阵；邻接表；扩展邻接矩阵 中图分类号： 27． 文献标识码：A 文章编号：1673—4580(2007)03—0001一(o4) 1 引言 定：如果结点 到结点vi存在弧( _÷t，f)则t／, =1， 图是一种重要的数据结构。图的结点之间关系 否则t／, =o例如，有向图G的邻接矩阵存储模式如 是任意的，图中任意的两个结点之间都可能相关。 图2所示。 因此，图有着广泛的用途，在计算机科学，运筹学和 利用邻接矩阵A，可以容易判定两个结点是否 控制论中有着广泛的应用。近来，有向图已成为组 有弧相连。例如A[2][4]=1，表示从结点 ：到结 合优化问题建模与求解的重要工具¨】。利用有向图 点 有一条弧，而A[3]E4]=0，则表明从结点 求解实际问题时，有效的存储结构对于问题求解的 到结点 无弧。结点 ；的出度可以通过求第i行元 效率是非常重要的。 素之和求出，结点 的入度可以通过计算第-『列的 本文在传统的有向图存储结构邻接矩阵和邻 所有元素之和得出 j。 接表的基础之上，综合二者的优点，提出一种新的 2．2邻接表与逆邻接表 有向图的存储结构一扩展邻接矩阵。扩展邻接矩阵 邻接表是有向图的链式存储结构。在邻接表 对传统的邻接矩阵进行扩充，利用矩阵中的元素值 中，对于图中的每个结点建立一个单链表，第i个单 和增加的两列来实现有向图中结点之间的前后继 链表表示以结点 为尾的弧。有向图G的邻接表如 关系。利用扩展邻接矩阵，不仅可以方便地判定任 图3所示。在有向图的邻接表存储结构中，第i个链 意两个结点之间是否有弧相连，还可以容易找到任 表中的结点个数只是结点 的出度，为了求出该结 意结点的后继邻接点集合、前驱邻接点集合以及求 点的入度必须遍历整个邻接表。 出结点的出度和入度。 为了能够方便求出结点 的入度或者以结点 2 有向图的传统存储模式 为头的弧，可以建立一个有向图的逆邻接表，即建 有向图的传统存储模式有三种：邻接矩阵，邻 立一个以 为头的弧的表。对于图1中的有向图G， 接表(逆邻接表)和十字链表。每一种存储模式，分 逆邻接表的存储结构如图4所示。在邻接表中，很 别可以实现对有向图的有关信息的快速访问。下文 容易查询到任意结点的第一个邻接点和下一个邻 将以图1所示的有向图G为例进行阐述。 接点，但要判定任意两个结点( ；和 )之间是否有 2．1邻接矩阵 弧相连，则需要有哪些信誉好的足球投注网站第 个和第 个链表。 邻接矩阵利用二维数组A=[t／, ] 来存储有 2．3十字链表 向图。在图的邻接矩阵存储模式中，分别以