【408 数据结构】图论核心算法（拓扑/关键路径）与二叉搜索树精髓夺分笔记

🎯 导语：在计算机专业基础综合（408）的数据结构复习中，图论与查找树是必考的硬骨头。本文基于今日全网最高效的复习笔记，将抽象的算法映射为生活常识，用最接地气的大白话和方法总结，帮你彻底对抗庞大的知识量！

文章目录

• • 一、 图论核心考点深度解析
  • • 1. 图的连通性与最少边数判定（常考选择题）
    • 2. 图的遍历复杂度对比
    • 3. 拓扑排序（DAG 图的经典应用）
    • 4. 关键路径（AOE 网的核心计算）
    • • 基础概念映射
      • 时间参数求解规律
      • 活动（边）的时间参数与“摸鱼”理论
    • 📝 关键路径经典演练（真题模拟）
  • 二、 查找与二叉搜索树（BST）
  • • 1. 查找
    • 2. 插入
    • 3. 创建
    • 4. 删除

一、 图论核心考点深度解析

1. 图的连通性与最少边数判定（常考选择题）

对于一个含

n

n

n 个顶点的图，保证其连通性的最少边数规律如下：

• 强连通有向图：由于必须形成有向环，最少需要 $n$
• 连通无向图：最极端的情况是退化为一棵树，最少需要 $n-1$

💡 核心方法总结（必定连通的边界判定）： 问题：求判定有

n

n

n 个顶点的无向图，在任意情况下必定连通需要多少条边？ 解题套路：先孤立一个顶点，保证剩下的

n

−

1

n-1

n−1 个顶点组成一个完全图（即尽可能把边耗尽却依然不连通），最后再加一条边连通孤立点。 必定连通公式：

最少边数

=

(

n

−

1

)

(

n

−

2

)

2

+

1

\\text{最少边数} = \\frac{(n-1)(n-2)}{2} + 1

最少边数=2(n−1)(n−2)​+1

2. 图的遍历复杂度对比

3. 拓扑排序（DAG 图的经典应用）

• 前提条件：图必须是有向无环图（DAG 图）。
• 核心解题步骤：

4. 关键路径（AOE 网的核心计算）

基础概念映射

• 顶点 —— 表示事件（可以理解为项目的某个里程碑，不消耗时间）。
• 边 —— 表示活动（需要消耗一定的时间开销）。

💡 核心方法总结（大白话理解）： 关键路径可以完美理解为**“沏茶问题”的变式**。也就是说，我们需要寻找一个完成所有任务所需时间最长的步骤序列。 为什么是最长路径？ 因为期间时间开销小的子任务与同期开销大的子任务是**同步进行（并行）**的，短任务必须等长任务，所以实际求解时，每次获取到当前顶点的最长路径才是制约总工期的关键。

时间参数求解规律

• 事件最早开始时间 $ve(j)$

口诀：早 max（必须等所有前置任务全部完成）

\\text{口诀：早 max（必须等所有前置任务全部完成）}

口诀：早 max（必须等所有前置任务全部完成）

• 事件最晚开始时间 $vl(j)$

口诀：迟 min（必须避免任一后续任务产生延误）

\\text{口诀：迟 min（必须避免任一后续任务产生延误）}

口诀：迟 min（必须避免任一后续任务产生延误）

• 💡 精妙总结：求 $vl(j)$

活动（边）的时间参数与“摸鱼”理论

• 活动最早开始时间 $e(i)$
• 活动最晚开始时间 $l(i)$
• 💡 趣味方法总结：

摸鱼时间（总时差）

=

l

(

i

)

−

e

(

i

)

\\text{摸鱼时间（总时差）} = l(i) – e(i)

摸鱼时间（总时差）=l(i)−e(i)

当摸鱼时间 = 0（即

l

=

e

l=e

l=e）时，该活动不存在任何偷懒空间，此活动即为关键活动，由关键活动组成的路径即为关键路径。

📝 关键路径经典演练（真题模拟）

【例题图示】 根据笔记中的 AOE 网，拓扑结构如下（其中数字为事件，字母及其数值为活动及时间开销）：

#mermaid-svg-aCAYHI6MeUOnRX7C{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-aCAYHI6MeUOnRX7C .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-aCAYHI6MeUOnRX7C .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-aCAYHI6MeUOnRX7C .error-icon{fill:#552222;}#mermaid-svg-aCAYHI6MeUOnRX7C .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-aCAYHI6MeUOnRX7C .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-aCAYHI6MeUOnRX7C .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-aCAYHI6MeUOnRX7C .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-aCAYHI6MeUOnRX7C .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-aCAYHI6MeUOnRX7C .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-aCAYHI6MeUOnRX7C .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-aCAYHI6MeUOnRX7C .marker{fill:#333333;stroke:#333333;}#mermaid-svg-aCAYHI6MeUOnRX7C .marker.cross{stroke:#333333;}#mermaid-svg-aCAYHI6MeUOnRX7C svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-aCAYHI6MeUOnRX7C p{margin:0;}#mermaid-svg-aCAYHI6MeUOnRX7C .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-aCAYHI6MeUOnRX7C .cluster-label text{fill:#333;}#mermaid-svg-aCAYHI6MeUOnRX7C .cluster-label span{color:#333;}#mermaid-svg-aCAYHI6MeUOnRX7C .cluster-label span p{background-color:transparent;}#mermaid-svg-aCAYHI6MeUOnRX7C .label text,#mermaid-svg-aCAYHI6MeUOnRX7C span{fill:#333;color:#333;}#mermaid-svg-aCAYHI6MeUOnRX7C .node rect,#mermaid-svg-aCAYHI6MeUOnRX7C .node circle,#mermaid-svg-aCAYHI6MeUOnRX7C .node ellipse,#mermaid-svg-aCAYHI6MeUOnRX7C .node polygon,#mermaid-svg-aCAYHI6MeUOnRX7C .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-aCAYHI6MeUOnRX7C .rough-node .label text,#mermaid-svg-aCAYHI6MeUOnRX7C .node .label text,#mermaid-svg-aCAYHI6MeUOnRX7C .image-shape .label,#mermaid-svg-aCAYHI6MeUOnRX7C .icon-shape .label{text-anchor:middle;}#mermaid-svg-aCAYHI6MeUOnRX7C .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-aCAYHI6MeUOnRX7C .rough-node .label,#mermaid-svg-aCAYHI6MeUOnRX7C .node .label,#mermaid-svg-aCAYHI6MeUOnRX7C .image-shape .label,#mermaid-svg-aCAYHI6MeUOnRX7C .icon-shape .label{text-align:center;}#mermaid-svg-aCAYHI6MeUOnRX7C .node.clickable{cursor:pointer;}#mermaid-svg-aCAYHI6MeUOnRX7C .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-aCAYHI6MeUOnRX7C .arrowheadPath{fill:#333333;}#mermaid-svg-aCAYHI6MeUOnRX7C .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-aCAYHI6MeUOnRX7C .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-aCAYHI6MeUOnRX7C .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-aCAYHI6MeUOnRX7C .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-aCAYHI6MeUOnRX7C .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-aCAYHI6MeUOnRX7C .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-aCAYHI6MeUOnRX7C .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-aCAYHI6MeUOnRX7C .cluster text{fill:#333;}#mermaid-svg-aCAYHI6MeUOnRX7C .cluster span{color:#333;}#mermaid-svg-aCAYHI6MeUOnRX7C div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-aCAYHI6MeUOnRX7C .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-aCAYHI6MeUOnRX7C rect.text{fill:none;stroke-width:0;}#mermaid-svg-aCAYHI6MeUOnRX7C .icon-shape,#mermaid-svg-aCAYHI6MeUOnRX7C .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-aCAYHI6MeUOnRX7C .icon-shape p,#mermaid-svg-aCAYHI6MeUOnRX7C .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-aCAYHI6MeUOnRX7C .icon-shape .label rect,#mermaid-svg-aCAYHI6MeUOnRX7C .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-aCAYHI6MeUOnRX7C .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-aCAYHI6MeUOnRX7C .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-aCAYHI6MeUOnRX7C :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

a=1

b=3

c=5

d=10

e=9

①

②

③

④

【求解推导过程】

• $ve(1)=0$
• $ve(3)=ve(1)+3=3$
• $ve(2)=\max \{ve(1)+1,ve(3)+5\}=\max \{1,8\}=8$
• $ve(4)=\max \{ve(2)+10,ve(3)+9\}=\max \{18,12\}=18$
• 整个项目的最短工期为 18。

• $vl(4)=18$
• $vl(2)=vl(4)-10=8$
• $vl(3)=\min \{vl(4)-9,vl(2)-5\}=\min \{9,3\}=3$

• 对于活动

  d

  d

  d（边 ②

  →

  \\rightarrow

  → ④）：

• 最早开始时间：

  e

  (

  d

  )

  =

  v

  e

  (

  2

  )

  =

  8

  e(d) = ve(2) = 8

  e(d)=ve(2)=8

• 最晚开始时间：

  l

  (

  d

  )

  =

  v

  l

  (

  4

  )

  −

  10

  =

  8

  l(d) = vl(4) – 10 = 8

  l(d)=vl(4)−10=8

• 摸鱼时间：

  l

  (

  d

  )

  −

  e

  (

  d

  )

  =

  0

  →

  l(d) – e(d) = 0 \\rightarrow

  l(d)−e(d)=0→ 关键活动！

• 对于活动

  e

  e

  e（边 ③

  →

  \\rightarrow

  → ④）：

• 最早开始时间：

  e

  (

  e

  )

  =

  v

  e

  (

  3

  )

  =

  3

  e(e) = ve(3) = 3

  e(e)=ve(3)=3

• 最晚开始时间：

  l

  (

  e

  )

  =

  v

  l

  (

  4

  )

  −

  9

  =

  9

  l(e) = vl(4) – 9 = 9

  l(e)=vl(4)−9=9

• 摸鱼时间：

  l

  (

  e

  )

  −

  e

  (

  e

  )

  =

  9

  −

  3

  =

  6

  →

  l(e) – e(e) = 9 – 3 = 6 \\rightarrow

  l(e)−e(e)=9−3=6→ 可安全摸鱼 6 天。

二、 查找与二叉搜索树（BST）

二叉搜索树（Binary Search Tree）的核心性质非常优美，通过大白话可以将其核心操作总结如下：

1. 查找

• 方法总结：每次拿着关键字跟根节点比，“小往左找，大往右找”。

2. 插入

• 方法总结：一路遵循查找逻辑比下去，直到下面为空，最后“挂”在相应的叶子节点上。

3. 创建

• 💡 核心方法总结：

创建的本质，就是连续的插入。

\\text{创建的本质，就是连续的插入。}

创建的本质，就是连续的插入。

（即把一组无序序列，一个个按照插入规则“挂”到树中）。

4. 删除

• 方法总结：为了不破坏BST的左小右大特性，若删除节点有两个子树，通常“将左子树的最右节点（左子树最大值）或右子树的最左节点（右子树最小值）移到新空位”来顶替它。

💡 结语：把书读薄，把公式变白话，这就是408一轮复习建立数字资产护城河的最佳实践！保持这个总结节奏，高分上岸稳了！ 标签：#计算机考研 #408 #数据结构 #图论 #二叉排序树 #学习笔记