🕸️ 408 图的四大存储结构终极拆解(邻接矩阵 / 邻接表 / 十字链表 / 邻接多重表)

核心痛点解决

为什么无向图有邻接表还要搞个“邻接多重表”?为什么有向图有邻接表还要搞个“十字链表”?每个结点到底有几个指针域? 本笔记把四大结构的 【物理结构图解 + C 语言结构体代码 + 结点/边数计算公式 + 痛点演进关系 + 408 真题破局】 彻底讲透,保证选择题与代码大题 0 失误!


🧭 0. 一张图看懂四大存储结构的“演进逻辑”(必背心法)

为什么会有这 4 种结构?(按“解决痛点”记忆,永不混淆)

  1. 邻接矩阵(二维数组):最直观,判边 。但遇到稀疏图(边极少)时,满屏都是 0 或 ∞,空间浪费极大,找邻居还要空扫整行 。
  2. 邻接表(数组 + 单链表):为了救稀疏图而生!只存实际存在的边。但它暴露出两个致命痛点:
    • 痛点 A(针对有向图):顺着链表只能算出度;想求某点的入度,必须把整个图所有链表全扫一遍!
    • 痛点 B(针对无向图):一条无向边 会在 和 的链表里各存一次(共 2 个边结点);如果要删除一条边,得去两个链表里分别找并删除,极其繁琐!
  3. 十字链表(专治有向图痛点 A):把有向图的“邻接表(管出边)”和“逆邻接表(管入边)”合二为一!一条有向弧只存 1 个结点,既能顺着查出度,又能顺着查入度。
  4. 邻接多重表(专治无向图痛点 B):让无向图的一条边只存 1 个边结点,同时挂在两个端点的链表上,删边只需改指针,无需找两处!

1. 邻接矩阵(Adjacency Matrix)—— 考察频率:⭐⭐⭐⭐⭐

一句话记忆

“稠密图首选,表示唯一,无向必对称,有向行出列入, 算路径条数”。

1.1 结构定义与代码骨架(408 算法大题高频)

用一个一维数组存顶点信息,一个二维数组 Edge[V][V] 存边的信息:

  • 不带权图(无权图):有边记为 1,无边记为 0(对角线 Edge[i][i] = 0)。
  • 带权图(网):有边记为权值 ,无边记为 ∞(或 0,对角线一般为 0)。

408 真题标准结构体定义(MGraph)

#define MAXV 100
typedef struct {
    int numVertices, numEdges;       // 顶点数 V 和边数 E
    char VerticesList[MAXV];         // 顶点表
    int Edge[MAXV][MAXV];            // 邻接矩阵(边表)
} MGraph;

1.2 核心性质与必考公式(选择题秒杀)

  1. 表示唯一性:只要顶点编号固定,图的邻接矩阵表示是唯一的!
  2. 空间复杂度:(只与顶点数 有关,与边数 无关!适合稠密图)。
  3. 无向图的邻接矩阵:
    • 一定是一个对称矩阵(Edge[i][j] == Edge[j][i])。因此在规模较大时,只需采用上/下三角压缩存储,空间可减半为 (主对角线全为 0 不用存)。
    • 顶点 的度 = 第 行(或第 列)中非零元素的个数。
    • 矩阵中非零元素的总个数 = (每条无向边贡献 2 个 1)。
  4. 有向图的邻接矩阵:
    • 不一定对称!“行出列入”(必背口诀):
      • 第 行非零元个数 = 顶点 的出度 (从 发出的边)。
      • 第 列非零元个数 = 顶点 的入度 (指向 的边)。
    • 矩阵中非零元素的总个数 = 。
  5. 矩阵幂 的图论意义(408 真题大坑):
    • 设邻接矩阵为 ,则 中的元素 表示从顶点 到顶点 长度为 (经过 条边)的路径总条数!
  6. 三角矩阵与拓扑排序的关系:
    • 若有向图的邻接矩阵是上三角或下三角矩阵(主对角线为 0),则该图必为有向无环图(DAG),一定存在拓扑序列!

2. 邻接表(Adjacency List)—— 考察频率:⭐⭐⭐⭐⭐

一句话记忆

“稀疏图首选,表示不唯一,无向边存 2 份(2E),有向边存 1 份(E),有向求入度要遍历全表”。

2.1 结构长什么样?(顶点数组 + 边单链表)

  • 顶点表结点(顺序数组):[ data (顶点信息) | firstarc (指向第一条依附于该顶点的边) ]
  • 边表结点(单链表):[ adjvex (邻接点下标) | weight (权值,可选) | nextarc (指向下一条边) ]
graph LR
    subgraph SG_V ["顶点表数组"]
        V0["0 | V0 | firstarc"]
        V1["1 | V1 | firstarc"]
        V2["2 | V2 | firstarc"]
    end
    V0 --> E01["adj:1 | next"] --> E02["adj:2 | NULL"]
    V1 --> E12["adj:2 | NULL"]
    V2 --> E20["adj:0 | NULL"]

408 真题标准结构体定义(ALGraph)

typedef struct ArcNode {          // 边表结点
    int adjvex;                   // 该弧所指向的顶点的位置(下标)
    struct ArcNode *nextarc;      // 指向下一条弧的指针
    // int info;                  // 网的边权值(可选)
} ArcNode;
 
typedef struct VNode {            // 顶点表结点
    char data;                    // 顶点信息
    ArcNode *firstarc;            // 指向第一条依附该顶点的弧的指针
} VNode, AdjList[MAXV];
 
typedef struct {
    AdjList vertices;             // 邻接表数组
    int vexnum, arcnum;           // 图的顶点数和弧数
} ALGraph;

2.2 核心性质与必考对比(无向 vs 有向)

对比维度无向图的邻接表有向图的邻接表(出边表)有向图的逆邻接表(入边表)
边结点总数(一条边在两端各存一次)
总空间复杂度
求某顶点的度数第 个链表长度,时间 求流出的出度易(数第 个链表长度)
求流入的入度难(需遍历全部 个链表,时间 )
求入度易(数链表长度)
求出度难(需遍历全表)
表示唯一性❌ 不唯一(单链表中边结点的排列顺序任意,取决于建表插入顺序)❌ 不唯一❌ 不唯一

3. 十字链表(Orthogonal List)—— 考察频率:⭐⭐⭐

408 第一铁律:十字链表 只能存【有向图】(或稀疏矩阵)!

考场上只要看到选项说“用十字链表存储无向图”,直接排掉! 核心目的:把有向图的邻接表和逆邻接表融合成一张表,解决“有向图邻接表求入度难”的痛点!

3.1 结点结构拆解(记住“顶点 3 域,弧结点 5 域”)

  1. 顶点结点(共 个,存于数组中)—— 3 个域: [ data (顶点数据) | firstin (入边表头指针:指向以该点为弧头的第一条入边) | firstout (出边表头指针:指向以该点为弧尾的第一条出边) ]

  2. 弧结点(共 个,每条有向边对应唯一 1 个结点)—— 5 个域: [ tailvex (弧尾/起点下标) | headvex (弧头/终点下标) | hlink (指向弧头相同的下一条入边) | tlink (指向弧尾相同的下一条出边) | info (权值) ]

graph LR
    subgraph OL_V ["顶点结点:共 3 个域"]
        V["data | firstin:第一条入边 | firstout:第一条出边"]
    end
    subgraph OL_A ["弧结点:共 5 个域,表示有向边 tailvex 指向 headvex"]
        A["tailvex:起点 | headvex:终点 | hlink:同终点的下一条入边 | tlink:同起点的下一条出边 | info"]
    end

3.2 怎么操作?(考点秒杀)

  • 求顶点 的出度:从 firstout 出发,顺着弧结点的 tlink(tail link,同起点) 一路往下数,时间复杂度 。
  • 求顶点 的入度:从 firstin 出发,顺着弧结点的 hlink(head link,同终点) 一路往下数,时间复杂度 。
  • 空间复杂度: 个顶点结点 + 个弧结点 = 。
  • 唯一性:❌ 不唯一。

4. 邻接多重表(Adjacency Multilist)—— 考察频率:⭐⭐⭐

408 第二铁律:邻接多重表 只能存【无向图】!

考场上只要看到选项说“用邻接多重表存储有向图”,直接排掉! 核心目的:解决无向图在普通邻接表中“一条边存 2 个结点(空间翻倍)且删除一条边需要找两个链表结点”的痛点!在邻接多重表中,一条无向边只用 1 个边结点!

4.1 结点结构拆解(记住“顶点 2 域,边结点 6 域”)

  1. 顶点结点(共 个,存于数组中)—— 2 个域: [ data (顶点数据) | firstedge (指向第一条依附于该顶点的边) ]

  2. 边结点(共 个,每条无向边对应唯一 1 个结点!)—— 6 个域(不计权值和标记则为 4 个核心域): [ mark (访问标记) | ivex (边的一个端点 i) | ilink (指向依附于顶点 ivex 的下一条边) | jvex (边的另一个端点 j) | jlink (指向依附于顶点 jvex 的下一条边) | info (权值) ]

graph LR
    subgraph AML_V ["顶点结点:共 2 个域"]
        V["data | firstedge:第一条依附边"]
    end
    subgraph AML_E ["边结点:共 6 个域,表示无向边 ivex 连接 jvex"]
        E["mark | ivex:端点i | ilink:连着i的下一条边 | jvex:端点j | jlink:连着j的下一条边 | info"]
    end

4.2 邻接表 vs 邻接多重表(无向图终极对比)

对比项无向图的邻接表无向图的邻接多重表
边结点数量 个(每条边存两份) 个(每条边只存一份!)
每个边结点的指针域数1 个(nextarc)2 个(ilink 和 jlink)
删除一条边 麻烦:必须分别在 的链表和 的链表中找到两个结点并删除极方便:只需找到这唯一的边结点,修改 ilink 和 jlink 前驱指针即可
求顶点 的所有相连边顺着 nextarc 一直走在边结点中看哪一端是 (若 ivex == i 则顺着 ilink 走;若 jvex == i 则顺着 jlink 走)

📋 5. 图的四大存储结构全景速查表(考前必背)

存储结构适用图类型顶点结点数边/弧结点数空间复杂度判两点是否有边找某点所有邻接点求入度/出度(或度)表示唯一?
邻接矩阵有向 / 无向
(稠密图)
无(二维数组 )行和=出度,列和=入度
时间均为
✅ 唯一
邻接表无向稀疏图求度:❌ 不唯一
邻接表有向稀疏图求出度:
求入度:(慢!)
❌ 不唯一
十字链表仅限有向稀疏图求出度、入度均极快❌ 不唯一
邻接多重表仅限无向稀疏图求度快,删边/标记边极方便❌ 不唯一

📝 6. 历年真题与经典好题精选(实战演练·破局版)

真题 1(四大存储结构适用性辨析 · 408 高频母题)

题目:下列关于图的存储结构的叙述中,错误的是( )。 A. 用邻接矩阵存储一个图时,在不考虑压缩存储的情况下,所占用的存储空间大小只与图中顶点数有关,而与边的条数无关 B. 邻接表只能用于有向图的存储,邻接多重表只能用于无向图的存储 C. 若一个有向图的邻接矩阵对角线以下元素均为 0,则该图的拓扑序列必定存在 D. 十字链表既是稀疏矩阵的一种链式存储结构,也是有向图的一种链式存储结构

真题 2(边结点个数与指针域数量计算 · 经典必刷)

题目:设无向图 有 个顶点和 条边。若采用邻接表存储,则边表结点的总数为( ① ),所有边表结点中指针域的总数为( ② );若改用邻接多重表存储,则边结点的总数为( ③ ),所有边结点中指向边的指针域总数为( ④ )。

真题 3(2021 年 408 算法统考大题背景 · 邻接矩阵与度计算)

题目:已知无向连通图 由顶点集 和边集 组成,。当 中度为奇数的顶点个数为不大于 2 的偶数时, 存在包含所有边且长度为 的路径(称为 EL 路径 / 欧拉路径)。设图 采用邻接矩阵存储,类型定义如下:

typedef struct {
    int numVertices, numEdges;
    char VerticesList[MAXV];
    int Edge[MAXV][MAXV];
} MGraph;

请设计算法 int IsExistEL(MGraph G),判断 是否存在 EL 路径,存在返回 1,否则返回 0,并说明时间复杂度和空间复杂度。