三、有向图的十字链表表示法 顶点结点 data firstin firstout 顶点信息数据 指向该顶点的 指向该顶点的 第一条入弧 第一条出弧狐 ●在十字链表中,既容易找到以v为尾的狐,也容易找到以v尾 头的狐,因而容易求得顶点的出度和入度。 ●建立十字链表的时间复杂度和建立邻接表是相同的。在某些 有向图中,十字链表是很有用的工具。 北京邮电大学自动化学院 21
北京邮电大学自动化学院 21 顶点信息数据 指向该顶点的 第一条入弧 指向该顶点的 第一条出弧 data firstin firstout 顶点结点 三、有向图的十字链表表示法 ⚫ 在十字链表中，既容易找到以vi为尾的狐，也容易找到以vi尾 头的狐，因而容易求得顶点的出度和入度。 ⚫ 建立十字链表的时间复杂度和建立邻接表是相同的。在某些 有向图中，十字链表是很有用的工具
有向图的十字链表表示法 例 V2 V3 V4 0V1 0 02 20 2|3 3 V 30∧ 31A十32~∧ 北京邮电大学自动化学院
北京邮电大学自动化学院 22 例 V2 V4 V1 V3 V1 V2 V3 V4 0 1 2 3 0 1 0 2 2 0 2 3 3 0 3 1 3 2 ^ ^ ^ ^ ^ ^ ^ ^ 三、有向图的十字链表表示法
四、无向图的邻接多重表存储表示 邻接多重表是无向图的另一种链式存储结构。邻接多重表的结 构和十字链表类似。在邻接多重表中,每一条边用一个结点表 示,它由如下所示的六个域组成: mark ivex ilink jex jlink info mark为标志域,可以用以标记该条边是否被搜索过。 ●ivex和jvex为该边依附的两个顶点在图中的位置。 ●iink指向下一条依附于顶点ivex的边。 jink指向下一条依附于顶点vex的边。 ●info为指向和边相关的各种信息的指针域。 北京邮电大学自动化学院
北京邮电大学自动化学院 23 四、无向图的邻接多重表存储表示 ⚫ 邻接多重表是无向图的另一种链式存储结构。邻接多重表的结 构和十字链表类似。在邻接多重表中，每一条边用一个结点表 示，它由如下所示的六个域组成： mark ivex ilink jvex jlink info ⚫ mark为标志域，可以用以标记该条边是否被搜索过。 ⚫ ivex和jvex为该边依附的两个顶点在图中的位置。 ⚫ ilink指向下一条依附于顶点ivex的边。 ⚫ jlink指向下一条依附于顶点jvex的边。 ⚫ info为指向和边相关的各种信息的指针域
四、无向图的邻接多重表存储表示 ●每一个顶点也用一个结点表示,它由如下所示的两个域组成: data firstedge|例( 2 ●data域存储和该顶点相关的信息 ● firstedge域指示第一条依附于该顶点的边 v4 043 1v 口2口口23 4N2|N4 北京邮电大学自动化学院
北京邮电大学自动化学院 24 例 v1 v5 v3 v2 v4 0 1 2 3 v1 v3 v4 v2 4 v5 0 1 0 3 2 1 2 3 4 1 2 4 ^ ^ ^ ^ ^ ⚫ 每一个顶点也用一个结点表示，它由如下所示的两个域组成： data firstedge ⚫ data域存储和该顶点相关的信息 四、无向图的邻接多重表存储表示 ⚫ firstedge域指示第一条依附于该顶点的边
7.3图的遍历 ●从图中某一顶点出发访遍图中其余顶点,且使每一个顶点 仅被访问一次。这一过程就叫做图的遍历。 通常有两条遍历图的路径: ●深度优先搜索遍历 广度优先搜索遍历 北京邮电大学自动化学院
北京邮电大学自动化学院 25 7.3 图的遍历 ⚫ 从图中某一顶点出发访遍图中其余顶点，且使每一个顶点 仅被访问一次。这一过程就叫做图的遍历。 ⚫ 通常有两条遍历图的路径： ⚫ 深度优先搜索遍历 ⚫ 广度优先搜索遍历