考研笔记

数据结构第 6 章：图总览

本章是「算竞背景帮助最大、但最容易因此失分」的一章。 算法你全会， 但 408 考的是教材的术语、教材的存储结构、教材的过程表——三样都和竞赛习惯不同。

页面导航

节页一句话
6.1.1图的基本概念术语精确到字；图不可以是空图
6.2.1~6.2.5图的存储及基本操作表 6.1 四列五行；十字链表与邻接多重表
6.3.1~6.3.3图的遍历复杂度取决于存储结构
6.4.1+6.4.2最小生成树与最短路径三张过程表：Prim / Kruskal / Dijkstra
6.4.3~6.4.5拓扑排序与关键路径四个参量、五个步骤
—📖 第 6 章名词库28 条名词 + 47 行范围限定清单

全章的三条线

① 算竞会、408 考的是另一半

flowchart LR
    subgraph HAVE["你已经有的（算竞）"]
        A1["BFS / DFS"]
        A2["Prim / Kruskal"]
        A3["Dijkstra / Floyd"]
        A4["拓扑排序"]
    end
    subgraph NEED["408 真正考的（差集）"]
        B1["术语精确定义<br/>极大连通子图 · 生成子图<br/>简单回路 · 弧头弧尾"]
        B2["十字链表 · 邻接多重表<br/>表 6.1 五行"]
        B3["逐轮过程表<br/>朴素 O(|V|²) 的填表格式"]
        B4["关键路径的四个参量<br/>vₑ / v_l / e / l / d"]
    end
    A1 -.-> B3
    A2 -.-> B3
    A3 -.-> B3
    A4 -.-> B4
    HAVE ==>|"直接迁移的部分很少"| NEED

    classDef have fill:#c8e6c9,stroke:#1b5e20
    classDef need fill:#ffcdd2,stroke:#b71c1c,stroke-width:2px
    class A1,A2,A3,A4 have
    class B1,B2,B3,B4 need

这一章不要重学算法，把时间全给右边那一栏。

② 表 6.1（默写目标）

邻接矩阵邻接表十字链表邻接多重表
空间复杂度无向
有向
找相邻边遍历对应行或列 找有向图入度必须遍历整个邻接表很方便很方便
删除边或顶点删边方便，删顶点需大量移动数据无向图中删边或顶点都不方便很方便很方便
适用于稠密图稀疏图和其他只能存有向图只能存无向图
表示方式唯一不唯一不唯一不唯一

③ 四个算法的适用边界

算法解决时间图的类型负权
Prim最小生成树仅带权无向图，稠密—
Kruskal最小生成树带权无向图，稀疏—
Dijkstra单源最短路径有向或无向不允许负权边
Floyd每对顶点最短路径有向或无向允许负权边，不允许负权回路
BFS无权图最短路径邻接表 都可—

教材脚注专门问过「Dijkstra 与 Prim 有何异同」，答案有三条：目的、思路、适用图。第三条最常考。

计算模板总表

场景做法
度与边无向 ；有向
点无向连通图最少边
点无向图最多几条边仍可能非连通
Dijkstra逐轮填表：行是顶点、列是轮次，每格写「dist + 路径」，末行写集合
拓扑排序唯一性每轮检查入度为 0 的顶点是否唯一
关键路径 取 Max 向前 → 取 Min 向后 → 起点 → 终点 → ， 即关键活动

高频边界

第一组 · 术语的一个字

  • 图不可以是空图（ 非空， 可空）。
  • 极大连通子图，不是「最大」。
  • 生成子图的判据是顶点集相同。
  • 简单回路允许首尾重复，简单路径不允许。
  • 弧尾是起点，弧头是终点。
  • 路径长度数边（与第 7 章查找长度数结点相反）。

第二组 · 存储结构

  • 邻接矩阵唯一，其余三种都不唯一。
  • 有向图邻接表求入度要遍历整个表——这是十字链表存在的理由。
  • 十字链表只存有向图，邻接多重表只存无向图。
  • 邻接多重表中一条边只有一个结点（邻接表是两个）。

第三组 · 复杂度与存储结构绑定

  • 遍历：邻接矩阵 ，邻接表 。
  • 生成树：邻接矩阵下唯一，邻接表下不唯一。
  • Prim 与边数无关，适合稠密图。

第四组 · 单向蕴涵（最容易被反向使用）

  • 边数 非连通（反向不成立）。
  • 边数 有环（反向不成立）。
  • 邻接矩阵是三角矩阵 存在拓扑序列（反向不一定）。
  • 有向图一次遍历访问全部顶点 该点可达所有点（不等于强连通）。

第五组 · 关键路径的方向

  • 取 Max、从前往后（拓扑序）； 取 Min、从后往前（逆拓扑序）。
  • 看弧的起点； 看弧的终点减权值。
  • 关键路径是最长路径，但等于工程的最短完成时间。
  • 关键路径可能不唯一，缩短工期要看公共活动。

复习顺序

  1. 6.1 — 术语。快扫但要抠字，尤其「极大 / 生成 / 简单回路 / 弧头弧尾」。
  2. 6.2 — 本章最该花时间的一节。表 6.1 默写，十字链表和邻接多重表的域名画三遍。
  3. 6.3 — 只看复杂度与存储结构的对应、生成树/森林、遍历次数三条。
  4. 6.4.1~6.4.2 — 动手画：Prim 逐轮树形、Kruskal 逐条取舍、Dijkstra 逐轮 dist 表。
  5. 6.4.3~6.4.5 — 关键路径五步流程 + 四列表，练三道。
  6. 名词库 — 考前扫 47 行范围限定清单。

只有 3 小时的话：默写表 6.1 → 画一遍 Dijkstra 逐轮表 → 做一道完整的关键路径 → 扫名词库清单。术语和存储结构占本章选择题的大头，关键路径占综合题。

链接

反向链接