Quartz 4

图的相关算法和存储

一、 图的遍历（满图乱跑找东西）

【实战迷你图】

顶点 1 连着 2 和 3；顶点 2 连着 4。

Plaintext

      2 --- 4
     /
    1
     \
      3

1. 广度优先搜索 (Breadth-First Search, BFS)

大白话：像水波纹一样一圈圈往外扩散。借助队列排队，先把离起点最近的一圈搜完，再搜下一圈。

考场推演与全部分支（从起点 1 开始）

  • 情况一（先看 2）：1 入队。1 出队，找邻居 2 和 3。2 先入队，3 后入队。输出 1。接着 2 出队，找邻居 4，4 入队，输出 2。接着 3 出队，无新邻居，输出 3。最后 4 出队，输出 4。输出序列为 1, 2, 3, 4。

  • 情况二（先看 3）：如果 1 找邻居时先看到 3。3 先入队，2 后入队。那么输出顺序就会变成 1, 3, 2, 4。

⚠️ 考场防坑法则（选择题必考）

  • 若图采用邻接矩阵存储：找邻居必定按编号从小到大扫描，序列唯一（只能是 1, 2, 3, 4）。

  • 若图采用邻接表存储：看链表里谁插在前面，序列不唯一（上述两种皆有可能）。

2. 深度优先搜索 (Depth-First Search, DFS)

大白话：不撞南墙不回头。借助栈或递归，顺着一条路死走，走到死胡同就原路退一步（回溯），换条路接着走。

考场推演与全部分支（从起点 1 开始）

  • 情况一（先走 2 这条路）：从 1 走到 2；从 2 走到 4；4 是死胡同，退回 2；2 没别的路，退回 1；1 发现还有去 3 的路没走，走到 3；3 是死胡同，退回 1，结束。输出序列为 1, 2, 4, 3（邻接矩阵下唯一）。

  • 情况二（先走 3 这条路）：从 1 走到 3；3 是死胡同，退回 1；1 换路走到 2；从 2 走到 4；4 退回 2，退回 1，结束。输出序列为 1, 3, 2, 4（邻接表下可能出现）。

二、 最小生成树 (Minimum Spanning Tree, MST)

目标：用最便宜的边把所有点连通，绝对不能有环。

【实战迷你图】

三座城市 A, B, C。报价（权值）：A-B 为 1，B-C 为 2，A-C 为 3。

Plaintext

       A
    1 / \ 3
     /   \
    B --- C
       2

3. 普里姆算法 (Prim)

大白话：“以点带面”。从一个据点开始，盯着据点向外辐射的所有边，挑一条最便宜的拉人入伙，慢慢向外吞并。

考场推演

  • 假发起点选 A。当前据点为 {A}。

  • A 向外看：去 B 权值为 1，去 C 权值为 3。选便宜的 A-B。据点更新为 {A, B}。

  • {A, B} 向外看：从 A 去 C 权值 3，从 B 去 C 权值 2。选便宜的 B-C。全部连通。

  • 最终选边顺序：A-B, B-C。

4. 克鲁斯卡尔算法 (Kruskal)

大白话：“全局上帝视角挑边”。不管点，把图里所有的边按权值从小到大排好，只要画上去不成环，就保留。

考场推演

  • 全部边排序：A-B(1), B-C(2), A-C(3)。

  • 拿最便宜的 A-B，未成环，保留。

  • 拿次便宜的 B-C，未成环，保留。

  • 拿最贵的 A-C，发现连上后 A-B-C 成环了！扔掉不要。

  • 最终选出边：A-B, B-C。

三、 最短路径 (Shortest Path)

【实战迷你图】

有向带权图。从 A 去 C 直达权值为 4。从 A 去 B 权值为 1，从 B 去 C 权值为 2。

Plaintext

       (1)
    A -----> B
     \       |
  (4) \      | (2)
       \     v
        +--> C

5. 迪杰斯特拉算法 (Dijkstra)

大白话：算单源（一个起点）到其他所有点的最短距离。核心是松弛操作（找跳板）。

考场推演（求 A 到各点最短距离）

  • 初始：A 去 B 距离 1，A 去 C 距离 4。B 离得最近，宣告 B 最短距离确定为 1。

  • 松弛：以定局的 B 为跳板向外看。发现 A → B → C 总权值为 1 + 2 = 3。

  • 更新：3 小于原来的直达距离 4，将 A 去 C 的距离更新为 3。

6. 弗洛伊德算法 (Floyd)

大白话：算多源（任意两点间）的最短距离。本质是通过三层循环穷举“中转站”。

考场防坑（代码填空题）

  • 外层循环变量必须是中转站。

  • 循环结构死记：for (k...) { for (i...) { for (j...) } }。k 必须在最外层。

四、 有向无环图应用 (DAG Applications)

7. 拓扑排序 (Topological Sort)

大白话：排课表。找没有前置条件（入度为 0）的点，拿出来，并擦掉它发出的所有箭头。

【实战迷你图】

Plaintext

   A
  / \
 B   C
  \ /
   D

考场推演（A指向B和C，B和C分别指向D）

  • A 没有箭头指着（入度为 0）。输出 A，擦掉 A 和连出的线。

  • 此时 B 和 C 入度都变成了 0。分支出现：先选 B 或先选 C 都可以。

  • 假设先选 B，输出 B 并擦线；再选 C，输出 C 并擦线。

  • 最后只剩 D，输出 D。

  • 有效拓扑序列：A, B, C, D 或者 A, C, B, D。（如果擦到一半找不到入度为 0 的点，说明图里有环）。

8. 关键路径 (Critical Path)

大白话：找工程里耗时最长的那条流水线。

【实战迷你图】

路线 1：起步 A → 中期 B (耗时2)；B → 终点 C (耗时3)。

路线 2：起步 A → 终点 C (耗时6)。

Plaintext

      (2)       (3)
[A] ----> [B] ----> [C]
  |                   ^
  +-------------------+
           (6)

考场野路子极速推演

  • 把所有从起点到终点的可行路线全列出来，算总时长。

  • 路径 1 (A→B→C) 总时长 = 2 + 3 = 5。

  • 路径 2 (A→C) 总时长 = 6。

  • 判定：取最大值！因为 6 天的那条线没完工，整个项目就没法交差。因此关键路径为 A→C，关键路径长度为 6。

📌 408 图存储结构：高频必考精简版

绝对核心一：邻接矩阵 (Adjacency Matrix)

【大白话】 开个二维数组（大表格）。不管有没有边，所有顶点之间的关系全列出来，有边填 1，没边填 0。

【常考极简例子】

3 个顶点 A(0), B(1), C(2)。只有一条边：A 指向 B。

Plaintext

      0(A)  1(B)  2(C)
0(A) [  0     1     0  ]   <- A的第一行有个1，说明A出度为1
1(B) [  0     0     0  ]   
2(C) [  0     0     0  ]

🔥 408 常考命题点：

  1. 查边贼快：想知道 A 和 C 连没连？直接查 Array[0][2] 是不是 1，一步到位（常考时间复杂度 ）。

  2. 太占空间：不管图里有几条边，空间永远死死占用 ，所以只适合稠密图。

  3. 遍历唯一：DFS/BFS 只要是用它存的，写出来的序列绝对唯一。

  4. 度数计算（大题常考）：有向图里，第 行的 1 的个数 = 出度；第 列的 1 的个数 = 入度。

绝对核心二：邻接表 (Adjacency List)

【大白话】 数组 + 链表。数组里只存顶点，每个顶点后面拖着一个链表，只记录自己真实连着的边，绝不浪费多余空间。

【常考极简例子】

3 个顶点 A, B, C。A 指向 B，A 也指向 C。

Plaintext

数组(顶点)      链表(它指向谁)
[ A ] -------> [ B ] -> [ C ] -> NULL
[ B ] -------> NULL
[ C ] -------> NULL

🔥 408 常考命题点：

  1. 超级省空间：有几条边就存几个节点，空间复杂度 ，所以适合稀疏图。

  2. 有向图的致命弱点：找“出度”很容易（顺着 A 的链表数就行），但找“入度”极其痛苦！想知道谁指向了 B，必须把整个图所有人的链表都遍历一遍。

  3. 遍历不唯一：DFS/BFS 序列不唯一，因为 A 后面跟着的 [B] 和 [C]，谁插在前面都可以。

附属考点：选择题“一句话秒杀”区

这俩兄弟绝对不会考大题，只需死记硬背它们是为了解决什么痛点而诞生的，看到选择题能选出来就行。

  • 十字链表：

    • 专治：有向图。

    • 痛点解决：完美解决了邻接表“找入度太痛苦”的问题（给边加了双向指针）。

  • 邻接多重表：

    • 专治：无向图。

    • 痛点解决：完美解决了无向图在邻接表里“一条边被存两次，删除/修改太麻烦”的问题（让两个顶点共享同一条边的记录）。

Graph View

Backlinks