企业官网建设流程全解析

• Prim、Kruskal：求最小生成树（MST），连通所有点、总边权最小
• Dijkstra、Floyd：求最短路径，点到点距离最短

极简记忆口诀

1. 生成树二选一：点多用 Prim，边多用 Kruskal
2. 最短路二选一：单点 Dijkstra，全点用 Floyd
3. 负权：只有 Floyd 能用，Dijkstra 直接报废

PRIM 算法（普里姆算法）简单讲解

PRIM 算法是用来求加权无向连通图的最小生成树（总权值最小的连通子图，且无环）的经典算法。

核心思想（贪心思想）

从一个起点顶点出发，每次都选择当前能连接到的、权值最小的边，把这条边的另一端顶点加入生成树，重复这个过程，直到所有顶点都被加入，就得到了最小生成树。

可以理解为："每次选最近的新邻居，把它拉进自己的圈子"🏠

步骤拆解

1. 初始化：
   • 选一个起点（比如顶点v₁），把它加入已访问集合S。
   • 记录S中所有顶点到未访问顶点的边的权值。
2. 选边：
   • 在所有连接S和未访问集合V-S的边中，找权值最小的边(u, v)（u∈S，v∈V-S）。
3. 更新：
   • 把顶点v加入S，同时更新S到剩余未访问顶点的最小权值。
4. 重复：
   • 重复步骤 2-3，直到S包含所有顶点，此时选出的边就构成了最小生成树。

关键特点

• 适用场景：稠密图（边数多的图），时间复杂度可以优化到O(n²)（用邻接矩阵）或O(E log n)（用优先队列）。
• 对比：和 Kruskal 算法相比，PRIM 更适合顶点少、边多的图，Kruskal 更适合边少的图。
• 无环保证：每次只加新顶点，不会形成环。

举个例子

假设有 5 个顶点的连通图，起点是 A：

• 初始：S={A}，A 能到 B (权 2)、C (权 5)
• 选最小边 A-B (2) →S={A,B}
• 现在 S 能到 C (3，B 到 C)、D (4，B 到 D)，选最小边 B-C (3) →S={A,B,C}
• 继续选 S 到剩余顶点的最小边，直到所有顶点都在 S 中，就得到了最小生成树。

最终总结：PRIM 算法是从单点出发，用贪心策略每次选最小权边扩展，最终得到最小生成树的算法✅

Kruskal 算法（克鲁斯卡尔算法）通俗讲解

我们可以用 "连村庄修公路"** 的例子来理解👇

1. 问题背景

假设有好几个村庄，我们要修公路把所有村庄连起来，要求总公路长度最短，而且不能有环路（不然就浪费了）。Kruskal 算法就是解决这个问题的最优方法之一。

2. 核心思路（贪心）

把所有公路按长度从短到长排序，然后依次选最短的公路来修，只要修这条公路不会让已经连通的村庄形成环路，就保留它，直到所有村庄都连通为止。

可以理解为："先修最短的路，能不绕就不绕，最后把所有村子连起来"🛣️

3. 具体步骤（用村庄举例）

1. 列清单：把所有两个村庄之间的公路长度全部列出来，比如 A-B (1km)、B-C (2km)、A-C (3km)、C-D (4km)。
2. 排序：按公路长度从短到长排好队：1km → 2km → 3km → 4km。
3. 依次修路：
   • 先修最短的 A-B (1km)，现在 A、B 连通，C、D 单独。
   • 再修 B-C (2km)，现在 A、B、C 连通，D 单独。
   • 下一条 A-C (3km)：修它会让 A-B-C-A 形成环路，直接跳过。
   • 再修 C-D (4km)，现在 A、B、C、D 全部连通，结束。
4. 结果：修的公路总长度是 1+2+4=7km，是最短的方案。

4. 关键知识点

• 最小生成树：最终修的这些公路，刚好把所有村庄连通、总长度最短、没有环路，就叫「最小生成树」。
• 防环路：用「并查集」来判断两个村庄是否已经连通（如果已经连通，就不用再修路了，不然会形成环路）。
• 适用场景：适合 ** 村庄多、公路少（稀疏图）** 的情况，和 Prim 算法刚好互补。

5. 和 Prim 算法的区别（一句话总结）

• Prim 算法：从一个村庄出发，每次找离这个连通圈最近的村庄修路，慢慢扩大圈子。
• Kruskal 算法：不管起点，直接按路的长短排序，从最短的路开始修，避免环路，直到全连通。

Dijkstra 算法

1. 先把问题变简单

假设你有一张城市地图：

• 每个城市是一个「点」（比如北京、上海、广州）
• 城市之间的高速公路是「边」，高速的长度是「权值」（比如北京到上海 1318 公里）
• 我们的目标：从北京（源点）出发，到其他所有城市的最短路线是什么？

Dijkstra 算法就是帮你找这个最短路线的方法。

2. 算法的核心思路（贪心思想）

它的逻辑特别像我们平时找路的思路：

1. 初始化：
   • 先假设从北京到所有城市的距离都是「无穷大」（就是还没找到路）
   • 只有北京到自己的距离是0
   • 用一个「已确定最短路线的城市列表」，一开始只有北京
2. 找最近的邻居：
   • 从「已确定」的城市出发，看它们能直接到的、还没确定路线的城市，算出到这些城市的距离
   • 选当前距离北京最近的那个城市，把它加入「已确定」列表
3. 更新路线：
   • 用这个刚加入的城市，去更新它能到的其他城市的距离（比如：北京→上海→杭州，可能比北京直接到杭州更近）
4. 重复：
   • 不断重复「找最近→更新」，直到所有城市都加入「已确定」列表

3. 用小例子走一遍

比如有 4 个城市：A（北京）、B、C、D

• A 到 B：10 公里
• A 到 C：无穷大（没直达）
• A 到 D：30 公里
• B 到 C：20 公里
• C 到 D：5 公里

步骤：

1. 初始：A (0)，B (∞)，C (∞)，D (∞)，已确定：[A]
2. 从 A 出发：A→B (10)，A→D (30)，最近的是 B → 已确定：[A,B]
3. 从 B 出发：B→C (10+20=30)，更新 C 的距离为 30；现在未确定的是 C (30)、D (30)，选任意一个（比如 C）→ 已确定：[A,B,C]
4. 从 C 出发：C→D (30+5=35)，比原来的 30 大，不更新；最后确定 D → 已确定：[A,B,C,D]
5. 最终最短路线：A→B (10)，A→B→C (30)，A→D (30)

4. 堆优化是什么？

刚才的步骤里，每次找「当前最近的城市」，如果城市很多（比如几百个），一个个找会很慢。 小根堆（优先队列）就像一个「自动排序的待选列表」：

• 每次把「到 A 的距离」放进堆里，堆会自动把最小的距离放在最上面
• 我们直接拿最上面的就行，不用一个个找，速度就快很多了

5. 小根堆优化

• 普通 Dijkstra：每次找最小要遍历所有点，时间复杂度O(V2)（V 是城市数量）
• 堆优化 Dijkstra：用堆找最小 + 更新，时间复杂度O((V+E)logV)（E 是高速路数量）

6. 一个重要限制

Dijkstra 算法不能处理「负长度的路」（比如：B 到 C 是 - 10 公里，相当于走这段路还能「倒贴」距离），因为它是贪心的，一旦确定路线就不会回头改，负权会让它算错。

Floyd

1. 先把问题变简单

假设你有一张全国城市的高铁线路图：

• 每个城市是一个「点」
• 城市之间的高铁线路是「边」，线路的耗时 / 里程是「权值」
• 我们的目标：算出任意两个城市之间的最短路线（比如北京到广州、上海到成都…… 所有组合）

Floyd 算法就是帮你一次性算出所有点对之间最短路线的方法。

2. Floyd 的核心思路：「中转」思想

Floyd 的逻辑特别简单：

从 A 到 B，有没有可能先从 A 到 C，再从 C 到 B，这样总路程更短？

它会把每一个城市都当作 “中转站”，挨个试一遍，不断更新两个城市之间的最短路线。

举个例子：

• 已知：北京→上海（1318 公里），北京→南京（1023 公里），南京→上海（301 公里）
• 用南京当中转站：北京→南京→上海 = 1023+301 = 1324 公里，比直达 1318 公里长，不更新
• 再试其他中转站，最终确定北京到上海的最短路线是直达 1318 公里

3. 用大白话讲步骤

1. 先画一张初始表：行和列都是城市，格子里填「直达的距离」，没有直达就填无穷大，自己到自己填 0。
2. 挨个当中转站：把每个城市 C 都当作中转站，遍历所有城市 A、B：
   • 计算「A→C + C→B」的总距离
   • 如果总距离比原来 A→B 的直达距离短，就更新表中的距离
3. 全部试完后，表里的每个格子就是对应两个城市的最短路线。

4. 结合你之前的题目

• Dijkstra 是从一个起点出发，算到其他所有点的最短路线；Floyd 是一次性算所有点对的最短路线。
• 当 Dijkstra 已经算出所有点对的最短路线后，dist 数组里已经是最短的结果了。
• Floyd 再执行一次，会用每个点当中转站去试，但因为已经是最短路线，不会有更短的可能，所以dist 数组不会发生任何改变，对应题目选 B。

5. 补充小知识

• Floyd 的时间复杂度是O(V3)（V 是城市数量），适合城市不多的情况。
• Floyd 可以处理有负权边的图（只要没有负权环），而 Dijkstra 不能处理负权边。

✅ 一句话总结：Floyd 就是把每个点都当中转站，试遍所有可能，算出所有点对的最短路线的算法。