S第十九讲(图的存储结构).ppt

1、数据结构与算法 -第十九讲,北方民族大学 计算机科学与工程学院 王伦津 研究员,图的存储结构,19、图的存储结构，邻接矩阵法、邻接表、十字链表和邻接多重表,掌握图的存储结构以及在各种存储结构下的图的表示方法以及各种表示方法下的实现算法 ，重点掌握邻接矩阵法、邻接表的图的表示方法,目 录,19.0 图的存贮结构 19.1 邻接矩阵法19.2 邻接表 19.3 十字链表（有向图）* 19.4 邻接多重表（无向图）*,19.1 图的存贮结构,因为在图中，任意一元素都可能有多个前趋与多个后继，所以无法通过元素的存贮次序反映元素间的关系，而必须显式地存贮结点之间的关系（即边）的信息。一般有两大类方法：

2、n 用边的集合表示图； n 用链接关系表示图。 邻接矩阵法就属于第一类，而邻接表、十字链表及邻接多重表等属于第二类。,19.1.1 邻接矩阵法,(一) 存贮方法 邻接矩阵(Adjacency Matrix)这是一种用边的集合表示图的方法。其中边集合用一个二维数组表示，数组每个元素表示一条边，它的两个下标分别表示边的两个端点的编号。结点编号要用连续的自然数，使得能与数组下标对应。,具体地讲，若用二维数组A表示图，则Aij表示边或(i,j)。边一般要用记录表示，以描述与边相关的各种信息。前面我们给出了边的抽象定义TGraphEdge0，对邻接矩阵，TGraphEdge0包含一般需求下的内容，故邻接

3、矩阵的边的定义可以是TGraphEdge0的直接派生（未增加新成员）：,A(1,1)=0 A(1,2)=1 A(1,3)=0 A(1,4)=0 A(1,5)=1 A(2,1)=1 A(2,2)=0 A(2,3)=0 A(2,4)=1 A(2,5)=0 A(3,1)=0 A(3,2)=0 A(3,3)=0 A(3,4)=0 A(3,5)=1 A(4,1)=1 A(4,2)=0 A(4,3)=0 A(4,4)=0 A(4,5)=0 A(5,1)=0 A(5,2)=0 A(5,3)=0 A(5,4)=0 A(5,5)=0,邻接矩阵边的定义 template struct TGraphEdgeMatr

4、ix:public TGraphEdge0 public: /TGraphEdge0中的函数均已实现，故这里不重载时不需给出。 ; 邻接矩阵结点的定义 template struct TGraphNodeMatrix : public TGraphNode0 / TGraphNode0中的函数均已实现，故这里不重载时不需给出。 /下面可以声明TGraphNodeMatrix中特有的函数 ;,邻接矩阵描述的图类 template /用到两个可变类型，分别是图结点内容和边内容 class TGraphMatrix: public TGraph0 public: TGraphEdgeMatrix e

5、dgesCNST_NumNodes; /存放图边的矩阵 TGraphNodeMatrix nodesCNST_NumNodes; /存放图结点的一维数组 /下面是其他成员的声明，同TGraph0，此处略(实际上机时不可略) ; 如果图结点个数变化很大，则边矩阵可以考虑用动态存储区（动态（可调）二维数组）。由于标准的C/C+不直接支持该功能，所以需要用new申请一块连续空间，然后将其封装在一个类中，设置二维数组访问接口。对结点数组，也要类似处理。,显然，对邻接矩阵，边描述TGraphEdgeMatrix中的起点和终点信息是冗余的，所以可以适当简化，例如，可以只用一个数表示边，即 边的权：若是边

6、edgesij= 特殊标志 ：若不是边,若不考虑边的权，则edges ij只表示边 是否存在，即i到j无边时 edges ij= 0或，否则 edges ij=1。,上列情况同样适合于无向图，此时，在上面的说明中，用(i,j)代替。对无向图，邻接矩阵是个对称矩阵，可按对称矩阵的压缩存贮方法存贮。,1 2 3 4 5 a b c d 1 2 3 4 1 0 1 0 0 1 2 1 0 0 1 0 a 1 0 1 0 1 3 0 0 0 0 1 b 2 1 0 0 1 4 1 0 0 0 0 c 3 0 0 0 1 5 0 0 0 0 0 d 4 1 1 1 0 图 191 所示图的邻接矩阵,例

7、191 对下面所示的有向图与无向图，它们的邻接矩阵如图所示（不考虑边权，设a,b,c,d的编号为1，2，3，4）考查增、删结点和边的实现方法。,这种存贮方式的空间复杂度正比于图的结点个数的平方，所以，当图中结点很多但边却很少时，采用这种结构会造成很大的浪费。不过，这种存贮结构没有链指针之类的附加开销。,邻接矩阵存储方式下，图的基本操作的基本实现方法。 1结点、边的增删 邻接矩阵，结点或边的增删的算法较简单，但一般要移动元素。 删除边：删除一条边比较简单，只需将对应元素置无边标志； 删除点：删除一个结点，要将与它关联的边一同删除，即删除结点在 矩阵中对应的行与列。 增加边：为现有两结点间增加一条

8、边，只需将 对应矩阵元素置边信息。 增加点：增加一个新结点，要在矩阵中相应位置插入一行一列。 增加新结点边：即插入带新结点的边，先插入新结点，然后置边信息。,(二) 算法实现的考虑,2度的计算 出度：结点i的出度等于i所对应的行上的非特殊元素的个数。 入度：结点i的入度等于i所对应的列上的非特殊元素的个数。 3找邻接点/判别是否有边 对邻接矩阵，判别是否有边是直接的，即要知结点i到j是否有边，只要测试元素Aij即可。至于找邻接点，则是个依次判别是否有边的问题。,4找路径 要找出结点x到结点y之间的路径，即path(x,y)，按下列伪码描述进行： Path(x, y) if (x=y) retu

9、rn x; /所找的路径为(x) if (若x到y有边) return (x, y); /所找的路径为(x,y) for (x的每个直接可达点u) if (u尚未试探过) if (Path(u,y)存在) return (x,u)+Path(u, y); return 0; /空路径 ,该算法并未涉及到图的具体的存贮结构，故可适合于任意存贮结构。对不同的存贮结构，只是判别是否有边及找邻接点的方法不同。,19.2.2 邻接表,(一) 存贮方法 图的邻接表(Adjacency List)存贮法与树的邻接表存贮法类似，其具体方法为： （1）为图中每个结点x建立一个线性链表，称x的出边链表。 （2）对

10、无向图，x的出边链表的每个元素，分别存放x的各邻接点边的信息。 （3）对有向图，x的出边链表的每个元素，分别存放以x为始点的各个弧的信息。,结点编号 结点内容 链头指针,（4）出边链表的结点结构为：,边终点编号 边内容 链指针,（5）为每个图结点，设立一个如下形式的结点：,（6）各结点可以存储在一个一维数组（称为头数组）中（每个数组元素分别对应一个图结点），也可以增设一个链指针，使各结点链在一起，形成另一个单链表。,例如，图 192 所示的图的邻接表。这里，假定图结点存储在数组中。 图 192,如果图中有n个结点，e条边，则邻接表需n个头数组元素、e个表结点。显然，当边数较少时，该存贮方式的存

11、贮利用率更高。这与邻接矩阵的情况正好相反。,邻接矩阵下的图边，应该是前面介绍的图边抽象类型TGraphEdge0的派生（对象）类，在数据成员方面，它只需在TGraphEdge0的基础上增加指向下条出边的指针。具体的C+描述为： template struct TGraphEdgeAL: public TGraphEdge0 /邻接表边 public TGraphEdgeAL *next; /链指针，指向与本对象邻接的下条出边 /下面是成员函数的声明，同TGraphEdge0，此处不重载，故不给出 ;,(二) 存储结构的高级语言描述,邻接表下的图结点，也应该是前面介绍的图结点抽象类型TGraph

12、Node0的派生（对象）类，在数据成员方面，它只需在TGraphNode0的基础上增加指向相应的出边链表的头结点的指针，具体的C+描述为： template struct TGraphNodeAL :public TGraphNode0 /邻接表结点 public: GraphEdgeAL * firstOutEdge; /本结点的第一条出边的指针 /面是其他成员的声明，同TGraphNode0，此处不重载，故不给出 ;,邻接表图类TGraphAL的定义。需要在TGraphAL设置指向邻接表的指针。 template /用到两个可变类型，分别是图结点内容和边内容 class TGraphAL:

13、 public TGraph0 /邻接表类 public: TGraphNodeAL *nodes; /存放图结点的一维数组（头数组） TGraphAL()nodes=NULL; numNodes=0; /构造函数 TGraphAL(long mNumNodes); /构造函数，只创建头数组 TGraphAL(TGraphEdgeRec *edgeSet, long n); /此构造函数根据边集edgeSet创建邻接矩阵 TGraphAL(); /析构函数，负责释放邻接表内结点 virtual long Cluster(long v0, long *nos,TTraverseMode tm);

14、 /面是其他成员的声明，同TGraph0，此处略(实际上机时不可略) ;,邻接表的图操作的实现，与邻接矩阵不同，下面进行讨论。 1求邻接点、关联边 求以x为始点（尾）的边时，只需搜索x的出边链表（线性链表）；求以x为终点（头）的结点时，则要搜索各结点的出边链表，检查其中是否有以x为终点的链表结点，若i的线性链表中有终点为x的结点，则就是一条边，其中i为始点。 2结点、边的增删 删除一条边：对有向图，删除边时，从x的出边链表中找到终点为y的结点，并删除之；对无向图，删除边(x,y)时，先在x的出边链表中找到终点为y的结点，并删除之，然后在y的出边链表中找到终点为x的结点并删除之。 增加新结点：在

15、头数组中增加一个元素即可。,(一) 算法实现的考虑,增加边：设要增加边，若x与y是已存在结点，则在x的线性链表中增加一个结点，置其终点为y；对无向图，还要按同样方法增加。若x或y是新结点，则先在头数组中增加对应的元素，然后按上法将边加到链表中。 删除一个结点：是上述几项操作的复合。先删除与待删结点关联的各个边，然后再在头数组中删除该结点。 3求度 出度：结点x的出度等于x的出边链表中结点个数。 入度：结点x的入度，等于各结点的出边链表中以x为终点的链结点的个数。故求入度时要扫描整个邻接表。 4路径： 基本思想同邻接矩阵。,是指如何将内存图结构转化（输出）为线性表示（表达式表示），或者如何将线性

16、表示还原为内存结构（逆串行化）。该问题对图结构的持久保存（磁盘文件保存）十分重要。对邻接矩阵，串行化问题是数组的存储问题，很简单。 对邻接表，要实现串行化，首先要确定结构的线性表示方式。我们这里将边集做为图的线性表示。例如，图 71(a)对应的边集为 , , , , , 下面我们给出基于这种线性表示的串行化程序。该程序也可TGraphAL的构造函数调用，实现根据边集创建邻接表。,5.串行化问题,template TGraphNodeAL * EdgeSetToAL(TGraphEdgeRec *edgeSet, long n, long ,else if (edgeSeti.startNo=e

17、dgeSetj.startNo | edgeSeti.startNo=edgeSetj.endNo) break; if (j=i) numN+; for (j=0; j *p; TGraphNodeAL *head; head = new TGraphNodeALnumN; for (i=0; inumN; i+) ,headi.firstOutEdge = NULL; headi.no=i; for (i=0; i ; /生成一个邻接表结点p p-startNo = edgeSeti.startNo; p-endNo = edgeSeti.endNo; p-weight = edgeSet

18、i.weight; p-next = headedgeSeti.startNo.firstOutEdge; /将p插入对应链表的最前面 headedgeSeti.startNo.firstOutEdge = p; return head; ,U 有时为了操作方便，对图采用逆邻接表存贮法。所谓逆邻接表，是指将有向图中的各弧的方向掉转后所对应的邻接表。对逆邻接表求入度与出度的方法，正好与邻接表情况相反。,19.3十字链表（有向图）*,(一) 存贮方法 图中任一结点均可能有若干个前趋和后继。如果将某结点的各前趋视为与它同“行”的元素，而将它的各后继视为与它同“列”的元素，则可沿用矩阵的十字链表存贮法

19、存贮图。这就是图的十字链表存贮法的基本思想。,通常，图的十字链表的“行”链表与“列”链表不使用循环结构。在图的十字链表中，i“行”对应的线性链表中的元素是以i为始点（尾）的边，而i“列”对应的线性链表中的结点是以i为终点（头）的边。具体地讲，图的十字链表存贮规则为 对于图中的每条边，用如下结构的一个结点描述（称为边结点）： 边信息 起点 终点 射入链 射出链 其中， 边信息：描述对应边的有关信息，如内容、权等。 起点：边的起点的编号。 终点：边的终点的编号。 射入链：指向终点相同的下条边 射出链：指向起点相同的下条边,对于每个图结点设一个顶点结点，其结构为： 结点编号 射入链头 射出链头 结点

20、信息 其中： 结点编号：存放结点的编号； 结点信息：存放结点的有关信息； 射入链头：指向该结点的射入链（即以该结点为终点的弧构成的链）中的第一个结点； 射出链头：指向该结点的射出链（即以该结点为始点的弧构成的链）中的第一个结点；,为了快速访问，可设一个一维数组（称为头数组），存放上述的各顶点结点。也可在顶点结点中增设一个链域，使各顶点结点链为一条链。图 194给出了一个有向图的十字链表。,(二) 高级语言描述： 有向图的十字链表存贮结构的主体是上面介绍的边结点和顶点结点，它们都分别是前面介绍的抽象边和抽象结点的派生（对象）类。十字链表的边结点，是在前面给出的抽象结点TGraphEdge0的基础

21、上，增加“射入链”和“射出链”信息而成，具体的C+描述如下： template struct TGraphEdgeCrossLink: public TGraphEdge0 GraphEdge *nextOut; /指向下一条射出边 TGraphEdge *nextIn; /指向下一条射入边 /下面是其他成员的声明，同TGraphEdge0，此处不 重载，故不给出 ,十字链表的顶点结点，是在前面给出的抽象结点TGraphNode0的基础上，增加指向相应的第一条射入边和第一条射出边的指针而成，具体的C+描述如下： template structTGraphNodeCrossLink: publi

22、c TGraphNode0 TGraphEdge *firstOut; /指向第一条射出边 TGraphEdge *firstIn; /指向第一条射入边 /下面是其他成员的声明，同TGraphNode0，此处 不重载，故不给出 ,至于代表整个图的类，是从TGraph0派生而来，并增加头数组作为成员，以便访问整个十字链表。 const int CNST_NumNodes; template /用到两个可变类型，分别是图结点内容和边内容 class TGraphCrossLink: public TGraph0 public: TGraphNodeCrossLink nodes CNST_NumN

23、odes /存放图结点的一维数组 /下面是其他成员的声明，同TGraph0，此略（但 实际上机时不可省略） ,(三) 结构与算法实现的考虑,图的十字链表是对图的邻接表的一种扩展，与邻接表相同的是，它也是对每条边设立一个链表结点。但不同的是，它的链表结点增设了一个用于将终点相同的弧链接在一起的链指针。所以对十字链表的操作与对邻接表的操作类似。只是要注意对新增链的利用（带来了方便性）和处理（带来了复杂性）。,十字链表实质上是邻接表与逆邻接表的结合，它同时具备这两种表的方便性，对任一结点，既可容易找出以它为始点的各边（点），也可方便找出以它为终点的各边（点）。 由于十字链表中每个链表结点（图中的边对应的结点）有两个链域，所以它的存贮效率要比邻接表低。 如果将图的邻接矩阵用矩阵的十字链表表示，则可发现，图的十字链表是图的邻接矩阵的十字链表的变形。二者的主要差别是： 前者的链表结点不需按起点与终点（相当于行号与列号）的大小排列； 前者的“行”与“列”链表一般不需构成循环结构。,19.4 邻接多重表（无向图）*,邻接多重表是面向无向图的一种链式存贮结构，可视为由有向图的十字链表演