Algorithms and Datastrucstures: Graphs 图的存储结构 2、邻接表( adjacency list) 设有向图或无向图具有n个结点,则用结点表、边表表示该有向图或无向图。 ·结点表:用数组或单链表的形式存放所有的结点。如果结点数n已知,则采用数 组形式,否则采用单链表的形式更好。 边表(边结点表):每条边用一个结点进行表示。同一个结点的所有的边形成 它的边结点单链表。 优点:内存=结点数+边数 缺点:确定ⅰ->j是否有边,最坏需耗费o(n)时间。无向图同一条边表示两次 边表空间浪费一倍。有向图中寻找进入某结点的边,非常困难。 结点表中的结点的表示: ·用数组 data:结点的数据场,保存结点的数据值。 data firstarc firstarc:结点的指针场,给出自该结点出发的 的第一条边的边结点的地址。 ALDS11 物料管理 ALDS 11 Algorithms and DataStrucstures:Graphs 图的存储结构 2、邻接表（adjacency list） • 设有向图或无向图具有 n 个结点，则用 结点表、边表表示该有向图或无向图。 • 结点表：用数组或单链表的形式存放所有的结点。如果结点数n已知，则采用数 组形式，否则采用单链表的形式更好。 • 边表（边结点表）：每条边用一个结点进行表示。同一个结点的所有的边形成 它的边结点单链表。 • 优点：内存 ＝ 结点数 ＋ 边数 • 缺点：确定 i --> j 是否有边，最坏需耗费 O(n) 时间。无向图同一条边表示两次 边表空间浪费一倍。有向图中寻找进入某结点的边，非常困难。 data firstarc 结点表中的结点的表示： • 用数组 data:结点的数据场，保存结点的数据值。 firstarc:结点的指针场，给出自该结点出发的 的第一条边的边结点的地址