Prim、Kruskal求最小生成树MST连通所有点、总边权最小Dijkstra、Floyd求最短路径点到点距离最短算法核心用途通俗理解适用图时间复杂度 (邻接矩阵)贪心 / 动态规划关键特点Prim最小生成树“点抱团”从一个起点出发每次连最近的未加入点慢慢把点圈起来稠密图点少边多、无向图O(n2)贪心适合点少边多和 Dijkstra 逻辑很像只是 Dijkstra 求最短路Prim 求生成树Kruskal最小生成树“边挑小的”把所有边从小到大排序依次选不形成环就加进去稀疏图点多边少、无向图O(ElogE)贪心用并查集判环适合边少的图代码简单Dijkstra单源最短路径“定点出发找最近”一个起点算出它到所有其他点的最短距离有向 / 无向边权不能为负O(n2)贪心只能求单个起点负权边失效Floyd多源最短路径“中转试探法”任意两点都试试 “借中间点绕路会不会更近”有向 / 无向可负权无负环O(n3)动态规划直接求所有点到所有点最短路代码极简三重循环极简记忆口诀生成树二选一点多用 Prim边多用 Kruskal最短路二选一单点 Dijkstra全点用 Floyd负权只有 Floyd 能用Dijkstra 直接报废PRIM 算法普里姆算法简单讲解PRIM 算法是用来求加权无向连通图的最小生成树总权值最小的连通子图且无环的经典算法。核心思想贪心思想从一个起点顶点出发每次都选择当前能连接到的、权值最小的边把这条边的另一端顶点加入生成树重复这个过程直到所有顶点都被加入就得到了最小生成树。可以理解为每次选最近的新邻居把它拉进自己的圈子步骤拆解初始化选一个起点比如顶点v₁把它加入已访问集合S。记录S中所有顶点到未访问顶点的边的权值。选边在所有连接S和未访问集合V-S的边中找权值最小的边(u, v)u∈Sv∈V-S。更新把顶点v加入S同时更新S到剩余未访问顶点的最小权值。重复重复步骤 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 (3B 到 C)、D (4B 到 D)选最小边 B-C (3) →S{A,B,C}继续选 S 到剩余顶点的最小边直到所有顶点都在 S 中就得到了最小生成树。最终总结PRIM 算法是从单点出发用贪心策略每次选最小权边扩展最终得到最小生成树的算法✅Kruskal 算法克鲁斯卡尔算法通俗讲解我们可以用 连村庄修公路** 的例子来理解1. 问题背景假设有好几个村庄我们要修公路把所有村庄连起来要求总公路长度最短而且不能有环路不然就浪费了。Kruskal 算法就是解决这个问题的最优方法之一。2. 核心思路贪心把所有公路按长度从短到长排序然后依次选最短的公路来修只要修这条公路不会让已经连通的村庄形成环路就保留它直到所有村庄都连通为止。可以理解为先修最短的路能不绕就不绕最后把所有村子连起来️3. 具体步骤用村庄举例列清单把所有两个村庄之间的公路长度全部列出来比如 A-B (1km)、B-C (2km)、A-C (3km)、C-D (4km)。排序按公路长度从短到长排好队1km → 2km → 3km → 4km。依次修路先修最短的 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 全部连通结束。结果修的公路总长度是 1247km是最短的方案。4. 关键知识点最小生成树最终修的这些公路刚好把所有村庄连通、总长度最短、没有环路就叫「最小生成树」。防环路用「并查集」来判断两个村庄是否已经连通如果已经连通就不用再修路了不然会形成环路。适用场景适合 ** 村庄多、公路少稀疏图** 的情况和 Prim 算法刚好互补。5. 和 Prim 算法的区别一句话总结Prim 算法从一个村庄出发每次找离这个连通圈最近的村庄修路慢慢扩大圈子。Kruskal 算法不管起点直接按路的长短排序从最短的路开始修避免环路直到全连通。Dijkstra 算法1. 先把问题变简单假设你有一张城市地图每个城市是一个「点」比如北京、上海、广州城市之间的高速公路是「边」高速的长度是「权值」比如北京到上海 1318 公里我们的目标从北京源点出发到其他所有城市的最短路线是什么Dijkstra 算法就是帮你找这个最短路线的方法。2. 算法的核心思路贪心思想它的逻辑特别像我们平时找路的思路初始化先假设从北京到所有城市的距离都是「无穷大」就是还没找到路只有北京到自己的距离是0用一个「已确定最短路线的城市列表」一开始只有北京找最近的邻居从「已确定」的城市出发看它们能直接到的、还没确定路线的城市算出到这些城市的距离选当前距离北京最近的那个城市把它加入「已确定」列表更新路线用这个刚加入的城市去更新它能到的其他城市的距离比如北京→上海→杭州可能比北京直接到杭州更近重复不断重复「找最近→更新」直到所有城市都加入「已确定」列表3. 用小例子走一遍比如有 4 个城市A北京、B、C、DA 到 B10 公里A 到 C无穷大没直达A 到 D30 公里B 到 C20 公里C 到 D5 公里步骤初始A (0)B (∞)C (∞)D (∞)已确定[A]从 A 出发A→B (10)A→D (30)最近的是 B → 已确定[A,B]从 B 出发B→C (102030)更新 C 的距离为 30现在未确定的是 C (30)、D (30)选任意一个比如 C→ 已确定[A,B,C]从 C 出发C→D (30535)比原来的 30 大不更新最后确定 D → 已确定[A,B,C,D]最终最短路线A→B (10)A→B→C (30)A→D (30)4. 堆优化是什么刚才的步骤里每次找「当前最近的城市」如果城市很多比如几百个一个个找会很慢。 小根堆优先队列就像一个「自动排序的待选列表」每次把「到 A 的距离」放进堆里堆会自动把最小的距离放在最上面我们直接拿最上面的就行不用一个个找速度就快很多了5. 小根堆优化普通 Dijkstra每次找最小要遍历所有点时间复杂度O(V2)V 是城市数量堆优化 Dijkstra用堆找最小 更新时间复杂度O((VE)logV)E 是高速路数量6. 一个重要限制Dijkstra 算法不能处理「负长度的路」比如B 到 C 是 - 10 公里相当于走这段路还能「倒贴」距离因为它是贪心的一旦确定路线就不会回头改负权会让它算错。Floyd1. 先把问题变简单假设你有一张全国城市的高铁线路图每个城市是一个「点」城市之间的高铁线路是「边」线路的耗时 / 里程是「权值」我们的目标算出任意两个城市之间的最短路线比如北京到广州、上海到成都…… 所有组合Floyd 算法就是帮你一次性算出所有点对之间最短路线的方法。2. Floyd 的核心思路「中转」思想Floyd 的逻辑特别简单从 A 到 B有没有可能先从 A 到 C再从 C 到 B这样总路程更短它会把每一个城市都当作 “中转站”挨个试一遍不断更新两个城市之间的最短路线。举个例子已知北京→上海1318 公里北京→南京1023 公里南京→上海301 公里用南京当中转站北京→南京→上海 1023301 1324 公里比直达 1318 公里长不更新再试其他中转站最终确定北京到上海的最短路线是直达 1318 公里3. 用大白话讲步骤先画一张初始表行和列都是城市格子里填「直达的距离」没有直达就填无穷大自己到自己填 0。挨个当中转站把每个城市 C 都当作中转站遍历所有城市 A、B计算「A→C C→B」的总距离如果总距离比原来 A→B 的直达距离短就更新表中的距离全部试完后表里的每个格子就是对应两个城市的最短路线。4. 结合你之前的题目Dijkstra 是从一个起点出发算到其他所有点的最短路线Floyd 是一次性算所有点对的最短路线。当 Dijkstra 已经算出所有点对的最短路线后dist 数组里已经是最短的结果了。Floyd 再执行一次会用每个点当中转站去试但因为已经是最短路线不会有更短的可能所以dist 数组不会发生任何改变对应题目选 B。5. 补充小知识Floyd 的时间复杂度是O(V3)V 是城市数量适合城市不多的情况。Floyd 可以处理有负权边的图只要没有负权环而 Dijkstra 不能处理负权边。✅ 一句话总结Floyd 就是把每个点都当中转站试遍所有可能算出所有点对的最短路线的算法。
Prim、Kruskal、Dijkstra、Floyd
Prim、Kruskal求最小生成树MST连通所有点、总边权最小Dijkstra、Floyd求最短路径点到点距离最短算法核心用途通俗理解适用图时间复杂度 (邻接矩阵)贪心 / 动态规划关键特点Prim最小生成树“点抱团”从一个起点出发每次连最近的未加入点慢慢把点圈起来稠密图点少边多、无向图O(n2)贪心适合点少边多和 Dijkstra 逻辑很像只是 Dijkstra 求最短路Prim 求生成树Kruskal最小生成树“边挑小的”把所有边从小到大排序依次选不形成环就加进去稀疏图点多边少、无向图O(ElogE)贪心用并查集判环适合边少的图代码简单Dijkstra单源最短路径“定点出发找最近”一个起点算出它到所有其他点的最短距离有向 / 无向边权不能为负O(n2)贪心只能求单个起点负权边失效Floyd多源最短路径“中转试探法”任意两点都试试 “借中间点绕路会不会更近”有向 / 无向可负权无负环O(n3)动态规划直接求所有点到所有点最短路代码极简三重循环极简记忆口诀生成树二选一点多用 Prim边多用 Kruskal最短路二选一单点 Dijkstra全点用 Floyd负权只有 Floyd 能用Dijkstra 直接报废PRIM 算法普里姆算法简单讲解PRIM 算法是用来求加权无向连通图的最小生成树总权值最小的连通子图且无环的经典算法。核心思想贪心思想从一个起点顶点出发每次都选择当前能连接到的、权值最小的边把这条边的另一端顶点加入生成树重复这个过程直到所有顶点都被加入就得到了最小生成树。可以理解为每次选最近的新邻居把它拉进自己的圈子步骤拆解初始化选一个起点比如顶点v₁把它加入已访问集合S。记录S中所有顶点到未访问顶点的边的权值。选边在所有连接S和未访问集合V-S的边中找权值最小的边(u, v)u∈Sv∈V-S。更新把顶点v加入S同时更新S到剩余未访问顶点的最小权值。重复重复步骤 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 (3B 到 C)、D (4B 到 D)选最小边 B-C (3) →S{A,B,C}继续选 S 到剩余顶点的最小边直到所有顶点都在 S 中就得到了最小生成树。最终总结PRIM 算法是从单点出发用贪心策略每次选最小权边扩展最终得到最小生成树的算法✅Kruskal 算法克鲁斯卡尔算法通俗讲解我们可以用 连村庄修公路** 的例子来理解1. 问题背景假设有好几个村庄我们要修公路把所有村庄连起来要求总公路长度最短而且不能有环路不然就浪费了。Kruskal 算法就是解决这个问题的最优方法之一。2. 核心思路贪心把所有公路按长度从短到长排序然后依次选最短的公路来修只要修这条公路不会让已经连通的村庄形成环路就保留它直到所有村庄都连通为止。可以理解为先修最短的路能不绕就不绕最后把所有村子连起来️3. 具体步骤用村庄举例列清单把所有两个村庄之间的公路长度全部列出来比如 A-B (1km)、B-C (2km)、A-C (3km)、C-D (4km)。排序按公路长度从短到长排好队1km → 2km → 3km → 4km。依次修路先修最短的 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 全部连通结束。结果修的公路总长度是 1247km是最短的方案。4. 关键知识点最小生成树最终修的这些公路刚好把所有村庄连通、总长度最短、没有环路就叫「最小生成树」。防环路用「并查集」来判断两个村庄是否已经连通如果已经连通就不用再修路了不然会形成环路。适用场景适合 ** 村庄多、公路少稀疏图** 的情况和 Prim 算法刚好互补。5. 和 Prim 算法的区别一句话总结Prim 算法从一个村庄出发每次找离这个连通圈最近的村庄修路慢慢扩大圈子。Kruskal 算法不管起点直接按路的长短排序从最短的路开始修避免环路直到全连通。Dijkstra 算法1. 先把问题变简单假设你有一张城市地图每个城市是一个「点」比如北京、上海、广州城市之间的高速公路是「边」高速的长度是「权值」比如北京到上海 1318 公里我们的目标从北京源点出发到其他所有城市的最短路线是什么Dijkstra 算法就是帮你找这个最短路线的方法。2. 算法的核心思路贪心思想它的逻辑特别像我们平时找路的思路初始化先假设从北京到所有城市的距离都是「无穷大」就是还没找到路只有北京到自己的距离是0用一个「已确定最短路线的城市列表」一开始只有北京找最近的邻居从「已确定」的城市出发看它们能直接到的、还没确定路线的城市算出到这些城市的距离选当前距离北京最近的那个城市把它加入「已确定」列表更新路线用这个刚加入的城市去更新它能到的其他城市的距离比如北京→上海→杭州可能比北京直接到杭州更近重复不断重复「找最近→更新」直到所有城市都加入「已确定」列表3. 用小例子走一遍比如有 4 个城市A北京、B、C、DA 到 B10 公里A 到 C无穷大没直达A 到 D30 公里B 到 C20 公里C 到 D5 公里步骤初始A (0)B (∞)C (∞)D (∞)已确定[A]从 A 出发A→B (10)A→D (30)最近的是 B → 已确定[A,B]从 B 出发B→C (102030)更新 C 的距离为 30现在未确定的是 C (30)、D (30)选任意一个比如 C→ 已确定[A,B,C]从 C 出发C→D (30535)比原来的 30 大不更新最后确定 D → 已确定[A,B,C,D]最终最短路线A→B (10)A→B→C (30)A→D (30)4. 堆优化是什么刚才的步骤里每次找「当前最近的城市」如果城市很多比如几百个一个个找会很慢。 小根堆优先队列就像一个「自动排序的待选列表」每次把「到 A 的距离」放进堆里堆会自动把最小的距离放在最上面我们直接拿最上面的就行不用一个个找速度就快很多了5. 小根堆优化普通 Dijkstra每次找最小要遍历所有点时间复杂度O(V2)V 是城市数量堆优化 Dijkstra用堆找最小 更新时间复杂度O((VE)logV)E 是高速路数量6. 一个重要限制Dijkstra 算法不能处理「负长度的路」比如B 到 C 是 - 10 公里相当于走这段路还能「倒贴」距离因为它是贪心的一旦确定路线就不会回头改负权会让它算错。Floyd1. 先把问题变简单假设你有一张全国城市的高铁线路图每个城市是一个「点」城市之间的高铁线路是「边」线路的耗时 / 里程是「权值」我们的目标算出任意两个城市之间的最短路线比如北京到广州、上海到成都…… 所有组合Floyd 算法就是帮你一次性算出所有点对之间最短路线的方法。2. Floyd 的核心思路「中转」思想Floyd 的逻辑特别简单从 A 到 B有没有可能先从 A 到 C再从 C 到 B这样总路程更短它会把每一个城市都当作 “中转站”挨个试一遍不断更新两个城市之间的最短路线。举个例子已知北京→上海1318 公里北京→南京1023 公里南京→上海301 公里用南京当中转站北京→南京→上海 1023301 1324 公里比直达 1318 公里长不更新再试其他中转站最终确定北京到上海的最短路线是直达 1318 公里3. 用大白话讲步骤先画一张初始表行和列都是城市格子里填「直达的距离」没有直达就填无穷大自己到自己填 0。挨个当中转站把每个城市 C 都当作中转站遍历所有城市 A、B计算「A→C C→B」的总距离如果总距离比原来 A→B 的直达距离短就更新表中的距离全部试完后表里的每个格子就是对应两个城市的最短路线。4. 结合你之前的题目Dijkstra 是从一个起点出发算到其他所有点的最短路线Floyd 是一次性算所有点对的最短路线。当 Dijkstra 已经算出所有点对的最短路线后dist 数组里已经是最短的结果了。Floyd 再执行一次会用每个点当中转站去试但因为已经是最短路线不会有更短的可能所以dist 数组不会发生任何改变对应题目选 B。5. 补充小知识Floyd 的时间复杂度是O(V3)V 是城市数量适合城市不多的情况。Floyd 可以处理有负权边的图只要没有负权环而 Dijkstra 不能处理负权边。✅ 一句话总结Floyd 就是把每个点都当中转站试遍所有可能算出所有点对的最短路线的算法。
