若无向图中有n个顶点、e条边,则它的邻接表需n个头 结点和2e个表结点。显然,在边稀疏e<mn1)2)的情况 下,用邻接表表示图比邻接矩阵节省存储空间,当和边相 关的信息较多时更是如此。 在无向图的邻接表中,顶点ⅵ的度恰为第i个链表中的结 点数;而在有向图中,第个链表中的结点个数只是顶点v 的出度,为求入度,必须遍历整个邻接表。在所有链表中 其邻接点域的值为的结点的个数是顶点ⅵ的入度。有时 为了便于确定顶点的入度或以顶点ⅵ为头的弧,可以建立 一个有向图的逆邻接表,即对每个顶点ⅵ建立一个链接以 ⅵ为头的弧的链表 2021年1月21日 数据结构讲义 26
2021年1月21日 数据结构讲义 26 • 若无向图中有n 个顶点、e条边，则它的邻接表需n个头 结点和2e个表结点。显然，在边稀疏(e<<n(n-1)/2)的情况 下，用邻接表表示图比邻接矩阵节省存储空间，当和边相 关的信息较多时更是如此。 • 在无向图的邻接表中，顶点vi的度恰为第i个链表中的结 点数；而在有向图中，第i个链表中的结点个数只是顶点vi 的出度，为求入度，必须遍历整个邻接表。在所有链表中 其邻接点域的值为i的结点的个数是顶点vi的入度。有时， 为了便于确定顶点的入度或以顶点vi为头的弧，可以建立 一个有向图的逆邻接表，即对每个顶点vi 建立一个链接以 vi为头的弧的链表
下图所示为有向图G2的邻接表和逆邻接表。 1 啊A明 A V2 V2 2V3 2 V3 0A A v4 2∧ (a)邻接表 )逆邻接表 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 27 • 下图所示为有向图G2的邻接表和逆邻接表
在建立邻接表或逆邻接表时,若输入的顶点信息即 为顶点的编号,则建立邻接表的复杂度为O(mte) 否则,需要通过查找才能得到顶点在图中位置,则时 间复杂度为0(ne) 在邻接表上容易找到任一顶点的第一个邻接点和下 个邻接点,但要判定任意两个顶点(ⅵ和v)之间 是否有边或弧相连,则需搜索第个或第j个链表,因此 ,不及邻接矩阵方便。 2021年1月21日 数据结构讲义 28
2021年1月21日 数据结构讲义 28 • 在建立邻接表或逆邻接表时，若输入的顶点信息即 为顶点的编号，则建立邻接表的复杂度为O（n+e）， 否则，需要通过查找才能得到顶点在图中位置，则时 间复杂度为O（n·e）。 • 在邻接表上容易找到任一顶点的第一个邻接点和下 一个邻接点，但要判定任意两个顶点（vi 和vj）之间 是否有边或弧相连，则需搜索第i个或第j个链表，因此 ，不及邻接矩阵方便
8.2.3十字链表 ◆十字链表( Orthogonal List)是有向图的一种存储方 法,它实际上是邻接表与逆邻接表的结合,即把每一条 边的边结点分别组织到以弧尾顶点为头结点的链表和以 弧头顶点为头顶点的链表中。在十字链表表示中,顶点 表和边表的结点结构分别如下图的(a)和(b)所示。 顶点值域指针域指针域 werte firstin firstout (a)十字链表顶点表结点结构 弧尾结点弧头结点弧上信息指针域 指针域 tailvex heaven Info hlink tlink b)十字链表边表的结点结构 十字链表顶点表、边表的肌结点结构示意 2021年1月
2021年1月21日 数据结构讲义 29 8.2.3 十字链表 十字链表（Orthogonal List）是有向图的一种存储方 法，它实际上是邻接表与逆邻接表的结合，即把每一条 边的边结点分别组织到以弧尾顶点为头结点的链表和以 弧头顶点为头顶点的链表中。在十字链表表示中，顶点 表和边表的结点结构分别如下图的(a)和(b)所示
·在弧结点中有五个域:其中尾域taie)和头( Cheadvex)分 别指示弧尾和弧头这两个顶点在图中的位置,链域hink指 向弧头相同的下一条弧,链域tink指向弧尾相同的下一条 弧,info域指向该弧的相关信息、。弧头相同的弧在同一链 表上,弧尾相同的弧也在同一链表上。它们的头结点即为 顶点结点,它由三个域组成:其中 vertex域存储和顶点相 关的信息; fisting和 firstout为两个链域,分别指向以该顶 点为弧头或弧尾的第一个弧结点。若将有向图的邻接矩阵 看成是稀疏矩阵的话,则十字链表也可以看成是邻接矩阵 的链表存储结构,在图的十字链表中,弧结点所在的链表 非循环链表,结点之间相对位置自然形成,不一定按顶点 序号有序,表头结点即顶点结点,它们之间是顺序存储 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 30 • 在弧结点中有五个域：其中尾域(tailvex)和头(headvex)分 别指示弧尾和弧头这两个顶点在图中的位置，链域hlink指 向弧头相同的下一条弧，链域tlink指向弧尾相同的下一条 弧，info域指向该弧的相关信息。弧头相同的弧在同一链 表上，弧尾相同的弧也在同一链表上。它们的头结点即为 顶点结点，它由三个域组成：其中vertex域存储和顶点相 关的信息；firstin和firstout为两个链域，分别指向以该顶 点为弧头或弧尾的第一个弧结点。若将有向图的邻接矩阵 看成是稀疏矩阵的话，则十字链表也可以看成是邻接矩阵 的链表存储结构，在图的十字链表中，弧结点所在的链表 非循环链表，结点之间相对位置自然形成，不一定按顶点 序号有序，表头结点即顶点结点，它们之间是顺序存储