当前位置：首页 > article >正文

【数据结构】8——图3，十字链表，邻接多重表

article 2024/11/13 13:03:38

数据结构8——图3，十字链表，邻接多重表

文章目录

数据结构8——图3，十字链表，邻接多重表
前言
一、十字链表
- 结构
- - 例子
- 复杂例子
二、邻接多重表（Adjacency Multilist）
- 例子

前言

除了之前的邻接矩阵和邻接表

邻接表不唯一，在有向图中只记录出度

逆邻接表记录入度

一、十字链表

表示稀疏有向图
结合了邻接表和逆邻接表的思想
获取顶点的出边（从该顶点出发的边）和入边（指向该顶点的边）

通过为每个顶点维护两个链表来实现：一个链表用于存储从该顶点出发的所有边（出边），另一个链表用于存储到达该顶点的所有边（入边）。

结构

十字链表中的每个节点对应图中的一条边

顶点节点：包含顶点信息和两个指针。一个指针指向该顶点的第一个出边节点（如果有的话），另一个指针指向第一个入边节点（通过某个其他顶点指向该顶点的边）的表头节点（这通常是一个哑节点或哨兵节点，用于简化插入和删除操作）。

Data（数据域）：存储顶点信息。
First In（第一入边）：指向该顶点的第一条入边。
First Out（第一出边）：指向该顶点的第一条出边。

边节点：包含边的信息（如权重）、一个指向起始顶点节点的指针、一个指向下一条出边节点的指针（在同一起始顶点下），以及一个指向下一条入边节点的指针（这些入边都指向同一个终点顶点，但它们可能来自不同的起始顶点）。

Tail Vertex（弧尾）：表示边的起点。
Head Vertex（弧头）：表示边的终点。
Head Link（头链域）：指向与当前弧头相同的下一个节点（指向同一个终点的下一条边）。
Tail Link（尾链域）：指向与当前弧尾相同的下一个节点（从同一个起点出发的下一条边）。
Info（信息域）：存储该边的相关信息，例如权重。

例子

考虑一个简单的有向图，有以下顶点和边：
顶点：A, B, C
边：A -> B, A -> C, B -> C

顶点表：
A：First Out -> A -> B，First In -> None
B：First Out -> B -> C，First In -> A -> B
C：First Out -> None，First In -> A -> C

边节点：
A -> B：
Tail Vertex: A
Head Vertex: B
Tail Link: 指向下一条从 A 出发的边 A -> C
Head Link: 指向下一条指向 B 的边 None
A -> C：
Tail Vertex: A
Head Vertex: C
Tail Link: None
Head Link: 指向下一条指向 C 的边 B -> C
B -> C：
Tail Vertex: B
Head Vertex: C
Tail Link: None
Head Link: None

Vertex A:
  Out: A -> B, A -> C
  In: 
Vertex B:
  Out: B -> C
  In: A -> B
Vertex C:
  Out: 
  In: A -> C, B -> C

复杂例子

顶点：A, B, C, D, E
边：
A -> B
A -> C
A -> D
B -> C
B -> E
C -> D
C -> E
D -> E

上图，按照上面简单例子的思路
先；列顶点，再列边，然后连线

在这里插入图片描述

二、邻接多重表（Adjacency Multilist）

每条边只存储一次，但是它会被链接到两个顶点的链表中，这两个顶点是边的两个端点。

把边的两个顶点存放在边表结点中，所有依附于同一个顶点的边串联在同一链表中。由于每条边依附于两个顶点，则每个边表结点同时链接在两个链表中。

顶点表：存储图中的顶点信息，每个顶点元素包含两个域：
data域：用于存放与顶点相关的信息，如顶点名称或编号。
firstedge域（或类似指针）：指向依附于该顶点的第一条边在边表中的节点。

边表：存储图中边的信息，每个边表节点包含多个域，常见的几个域包括：
mark：标志域，用于标记该边是否被访问过或进行过其他特定操作。
ivex和jvex：分别存放该边两个顶点在顶点表中的位置（即下标）。
info：信息域，对于带权图，可以存放边的权值；对于无向图，此域可省略。
ilink和jlink：分别指向下一条依附于顶点ivex和jvex的边在边表中的节点。

例子

考虑一个简单的无向图，包含4个顶点和5条边：
顶点：A, B, C, D
边：
A-B
A-C
B-C
B-D
C-D

创建顶点节点
首先，为每个顶点创建一个顶点节点，每个节点包含一个指向其邻接边链表的指针。

顶点节点 A
顶点标识: A
边链表头指针: 指向A的邻接边链表的头节点
.

顶点节点 B
顶点标识: B
边链表头指针: 指向B的邻接边链表的头节点
.
顶点节点 C
顶点标识: C
边链表头指针: 指向C的邻接边链表的头节点
.
顶点节点 D
顶点标识: D
边链表头指针: 指向D的邻接边链表的头节点

创建边节点
为每条边创建一个边节点，每个边节点包含以下信息：
目标顶点: 目标顶点的标识或引用
边的权重（如果有）
下一个边节点的指针: 指向链表中的下一个边节点

边节点 A-B
目标顶点: B
边的权重: 无
下一个边节点的指针: null（这是A的链表中的第一个边节点）
.
边节点 A-C
目标顶点: C
边的权重: 无
下一个边节点的指针: null（这是A的链表中的第二个边节点）
.
边节点 B-C
目标顶点: C
边的权重: 无
下一个边节点的指针: null（这是B的链表中的第一个边节点）
.
边节点 B-D
目标顶点: D
边的权重: 无
下一个边节点的指针: null（这是B的链表中的第二个边节点）
.
边节点 C-D
目标顶点: D
边的权重: 无
下一个边节点的指针: null（这是C的链表中的第一个边节点）