图的邻接表存储表示 头结点 data starc 每个链表上附设一个表头结点。在表头结点中,除了设有链域 ( firstarc)指向链表中第一个结点之外,还设有存储顶点v的名 或其它有关信息的数据域(data) Ⅴ exdatafirstarc adivex 例 八 0 3 4 2 4 2 0 G2 2 八 北京邮电大学自动化学院 16
北京邮电大学自动化学院 16 ⚫ 每个链表上附设一个表头结点。在表头结点中，除了设有链域 (firstarc)指向链表中第一个结点之外，还设有存储顶点Vi的名 或其它有关信息的数据域(data)。 头结点 data firstarc 二、图的邻接表存储表示 例 V1 V5 V3 V2 V4 G2 0 1 2 3 V1 V3 V4 V2 vexdatafirstarc 1 4 2 3 ^ ^ ^ adjvexnext 4 V5 2 4 2 0 ^ 1 0 2 1 ^
图的邻接表存储表示 exdatafirstarc adivex 例 0V 八 2 2 2 0 G2 4|V 2 ●若无向图中有n个顶点、e条边,则它的邻接表需n个头结点 和2e个表结点。显然,在边稀疏(e<<n(n-1)2)的情况下,用 邻接表表示图比邻接矩阵节省存储空间,当和边相关的信息 较多时更是如此。 北京邮电大学自动化学院
北京邮电大学自动化学院 17 ⚫ 若无向图中有n个顶点、e条边，则它的邻接表需n个头结点 和2e个表结点。显然，在边稀疏(e<<n(n-1)/2)的情况下，用 邻接表表示图比邻接矩阵节省存储空间，当和边相关的信息 较多时更是如此。 二、图的邻接表存储表示 例 V1 V5 V3 V2 V4 G2 0 1 2 3 V1 V3 V4 V2 vexdatafirstarc 1 4 2 3 ^ ^ ^ adjvexnext 4 V5 2 4 2 0 ^ 1 0 2 1 ^
图的邻接表存储表示 vexdatafirstarc adjvexnext 例 0 V 2 1|入 2V3 3A 0 ●在无向图的邻接表中,顶点v的度恰为第个链表中的结点数; ●而在有向图中,第i个链表中的结点个数只是顶点v的出度,为 求入度,必须遍历整个邻接表。 ●在所有链表中其邻接点域的值为的结点的个数是顶点v的入 度。 北京邮电大学自动化学院
北京邮电大学自动化学院 18 例 G1 V2 V4 V1 V3 0 1 2 3 V1 V3 V4 V2 vexdatafirstarc 2 1 3 0 ^ ^ ^ ^ adjvexnext 二、图的邻接表存储表示 ⚫ 在无向图的邻接表中，顶点vi的度恰为第i个链表中的结点数； ⚫ 而在有向图中，第i个链表中的结点个数只是顶点vi的出度，为 求入度，必须遍历整个邻接表。 ⚫ 在所有链表中其邻接点域的值为i的结点的个数是顶点vi的入 度
二、图的邻接表存储表示 有时,为了便于确定顶点的入度或以顶点v为头的弧,可以建 立一个有向图的逆邻接表,即对每个顶点v建立一个链接以v 为头的弧的链表。 0|A 3∧ 1 B 3 0入 2 C 3D 2 4 E 0 在邻接表上容易找到任一顶点的第1个邻接点和下一个邻接点, ●但是要判定任意两个顶点(v和v)之间是否有边或狐相连,则 需搜索第i个或第个链表,因此,不及邻接矩阵方便。 北京邮电大学自动化学院 19
北京邮电大学自动化学院 19 A B E C D 二、图的邻接表存储表示 ⚫ 有时，为了便于确定顶点的入度或以顶点vi为头的弧，可以建 立一个有向图的逆邻接表，即对每个顶点vi 建立一个链接以vi 为头的弧的链表。 ⚫ 在邻接表上容易找到任一顶点的第1个邻接点和下一个邻接点， 3 3 0 4 2 E 0 D C B A 4 3 2 1 0 ⚫ 但是要判定任意两个顶点（vi和vj）之间是否有边或狐相连，则 需搜索第i个或第j个链表，因此，不及邻接矩阵方便
有向图的十字链表表示法 ●十字链表是有向图的另一种链式存储结构。可以看成是将 有向图的邻接表和逆邻接表结合起来得到的一种链表。 ●在十字链表中,对应于有向图中每一条弧有一个结点,对 应于每一个顶点也有一个结点。这些结点的结构如下: 弧的结点结构 tailvex headvex hlink tlink info 孤尾顶点位置弧头顶点位置弧的相关信息 指向下一个有 指向下一个 相同弧头的结 有相同弧尾 点 的结点 北京邮电大学自动化学院
北京邮电大学自动化学院 20 三、有向图的十字链表表示法 ⚫ 十字链表是有向图的另一种链式存储结构。可以看成是将 有向图的邻接表和逆邻接表结合起来得到的一种链表。 ⚫ 在十字链表中，对应于有向图中每一条弧有一个结点，对 应于每一个顶点也有一个结点。这些结点的结构如下： 弧的结点结构 弧尾顶点位置 弧头顶点位置 弧的相关信息 指向下一个 有相同弧尾 的结点 指向下一个有 相同弧头的结 点 tailvex headvex hlink tlink info