图的邻接表存储结构详解

  • 内容
  • 评论
  • 相关

通常,图更多的是采用链表存储,具体的存储方法有 3 种,分别是邻接表邻接多重表十字链表

本节先讲解图的邻接表存储法。邻接表既适用于存储无向图,也适用于存储有向图。

在具体讲解邻接表存储图的实现方法之前,先普及一个"邻接点"的概念。在图中,如果两个点相互连通,即通过其中一个顶点,可直接找到另一个顶点,则称它们互为邻接点。

邻接指的是图中顶点之间有边或者弧的存在。

邻接表存储图的实现方式是,给图中的各个顶点独自建立一个链表,用节点存储该顶点,用链表中其他节点存储各自的临界点。

与此同时,为了便于管理这些链表,通常会将所有链表的头节点存储到数组中(也可以用链表存储)。也正因为各个链表的头节点存储的是各个顶点,因此各链表在存储临界点数据时,仅需存储该邻接顶点位于数组中的位置下标即可。

例如,存储图 1a) 所示的有向图,其对应的邻接表如图 1b) 所示:


邻接表存储有向图
图 1 邻接表存储有向图

本文标题:图的邻接表存储结构详解

本文地址:https://www.hosteonscn.com/5242.html

评论

0条评论

发表评论

邮箱地址不会被公开。 必填项已用*标注