淘宝客网站需要备案吗,网站开发合同 附件,小红书笔记推广,招生平台网站开发数据结构8——图3#xff0c;十字链表#xff0c;邻接多重表 文章目录 数据结构8——图3#xff0c;十字链表#xff0c;邻接多重表前言一、十字链表结构例子 复杂例子 二、邻接多重表#xff08;Adjacency Multilist#xff09;例子 前言
除了之前的邻接矩阵和邻接表
…数据结构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 顶点表 AFirst Out - A - BFirst In - None BFirst Out - B - CFirst In - A - B CFirst Out - NoneFirst 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 - CIn:
Vertex B:Out: B - CIn: 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的链表中的第一个边节点 3:. 更新邻接表 顶点 A 将边节点 A-B 插入到A的邻接边链表中。 将边节点 A-C 插入到A的邻接边链表中。 链表顺序为 A-B - A-C。 顶点 B 将边节点 B-C 插入到B的邻接边链表中。 将边节点 B-D 插入到B的邻接边链表中。 链表顺序为 B-C - B-D。 顶点 C 将边节点 C-D 插入到C的邻接边链表中。 需要将边节点 A-C 插入到C的邻接边链表中。 链表顺序为 C-D - A-C。 顶点 D D的链表为空因为D没有指向其他节点的边在无向图中D的边已经在其他节点的链表中表示。 完整的邻接多重表结构 顶点 A 边链表: A-B - A-C 顶点 B 边链表: B-C - B-D 顶点 C 边链表: C-D - A-C 顶点 D 边链表: 空 复杂的上图 顶点A, B, C, D, E, F 边 A-B A-C B-C B-D C-E D-E D-F E-F A-F 重复的边不再建立节点而是连接到之前的那个节点上
