6.2 图的存储表示

研究以下三种图的常用存储方式:

  • 「邻接矩阵 adjacency matrices」 假设图 GG 的邻接矩阵是 adj_mat,是一个 n×nn \times n 的二维数组。如果 (vi,vj)(v_i, v_j) (或 <vi,vj><v_i, v_j>)是图 GG 中的一条边,则 adj_mat[i][j] = 1,如果不存在这样的边,则 adj_mat[i][j] = 0。如下图。对于无向图而言,(vi,vj)(v_i, v_j)(vj,vi)(v_j, v_i) 是同一条边,所以无向图的邻接矩阵一定是对称的。因此,为了节省存储空间,无向图的邻接矩阵只需存储其上三角或下三角部分。

6-6

  • 「邻接表 adjacency lists」 通常,把边很少的图称为 「稀疏图 sparse graphs」,在稀疏图的邻接矩阵表示方式中,大多数元素值为 0,在扫描所有边的时候就会使用很多不必要的时间来检查这些 0 元素,因此引入邻接表。 在邻接表存储表示中,用 nn 个链表代替邻接矩阵中的 nn 行。图 GG 中的每个顶点对应一个链表,链表中的结点就是与顶点 ii 相邻的所有顶点。如下图,分别是图 G1G_1 和图 G3G_3 的邻接表存储方式。

    6-7

    • 「顺序存储」使用邻接表存储方式的图也可以把顶点进行顺序存储,这样就可以不用指针域。假定用数组 node[] 存储顶点,那么 node[i] 的值是顶点 i 所对应链表在数组 node[] 中的开始位置。顶点 i 的所有邻接顶点依次存放在 node[i], ..., node[i+1]-1 中。如下图给出了图 G1G_1 的这种顺序存储表示。
    • 「逆邻接表 inverse adjacency lists」 在使用邻接表的过程中,得到有向图的一个顶点的入度是比较复杂的,现在引入「逆邻接表」,与邻接表不同的是,逆邻接表中的每个链表存储的是邻接到(与邻接于相区别)对应顶点的所有顶点。如下图是图 G3G_3 的逆邻接表。
    • 「正交链表存储表示」改变邻接表的结点结构是解决计算顶点入度问题的另一种途径。如下图,改变后的结点包含四个域,用来表示图中的一条边。这与 4.6 稀疏矩阵 里稀疏矩阵的存储表示类似。

    6-10

    单个结点的结构(上)和图的正交链表存储表示(下)

  • 「邻接多重表 adjacency multilists」 为了方便查找边 (vi,vj)(v_i, v_j) 中顶点 vjv_j 的邻接表的内容,并对已扫描过的边做上标记。引入「多重表 multilists」,如下图为图 G1G_1 的邻接多重表存储表示。

单个结点的结构(上)和图的邻接多重表存储表示(下)

带权值的边

到目前为止,所讨论的图都是边上没有权值的图。在许多实际应用中,图中的边都被赋予权值。带权值的图在邻接矩阵存储表示中用边的权值取代原来的 11。对于图的邻接表和邻接多重表存储表示方式,必须在结点的结构上新增一个域 weight 来存储边上的权值。一个边上带权值的图称为 「网络 network」

results matching ""

    No results matching ""