🕸️ 图论算法及综合应用

把城市当「点」、道路当「线」，就得到一张图（Graph）。修路要省钱 → 最小生成树（Kruskal、Prim）；找最短的路 → 最短路径（Dijkstra、Floyd）。地图导航、修路规划、社交网络都靠这些算法！

考纲知识点：最小生成树的概念、kruskal 算法、prim 算法
最短路径的概念、dijkstra 算法、Floyd 算法
图论算法的综合应用与问题求解技巧

📖

考纲 · 知识点详述

摘自《CCF编程能力等级认证 C++&Python 认证标准》C++ 八级

(6)掌握图论算法及综合应用技巧。包括最小生成树的概念、kruskal 算法、prim 算法，掌握最短路径的概念、单源最短路径的dijkstra 算法、Floyd 算法等。理解实现同一功能的不同算法的比较，并可以灵活解决相关问题。

📚

先学一学

花 6 分钟读完下面 5 课，再去闯关就不慌啦

🕸️ 图 = 顶点 + 边

图（Graph）由顶点（点，画成圆圈）和边（连线）组成。城市是点、道路是边；人是点、朋友关系是边。

↔️ 有向 vs 无向

无向图的边没有方向（A—B，能来回走）；有向图的边带箭头（A→B，只能按方向走）。顶点的度就是连在它身上的边数；有向图还分入度（箭头进来）和出度（箭头出去）。

💡 口诀：点叫顶点、线叫边；无向能来回、有向看箭头；度 = 连着几条边。

🗄️ 图怎么存进电脑：邻接矩阵 vs 邻接表

n 个顶点的无向图，邻接矩阵是 n×n 的表，格子 [i][j] 记录 i 和 j 有没有边（占 n×n 格）。邻接表给每个点挂一条「邻居清单」，总边节点数：无向图每条边出现两次 = 2e；有向图每条边只出现一次 = e。点少边密用矩阵，点多边稀用邻接表省内存。

💡 口诀：矩阵 n×n 查得快但费格子；邻接表无向 2e、有向 e，邻居挂清单。

🌳 最小生成树：用最少的边把所有点连起来

给 n 个点修路，让它们都连通，还要总造价最低 → 选出的边要正好 n−1 条，不能有环，边权总和最小。这棵树叫最小生成树（MST）。

✂️ Kruskal（克鲁斯卡尔）：按边从小到大挑

把所有边按权从小到大排，从小的开始选，只要不形成环就收下，直到选满 n−1 条。判断「会不会成环」用并查集（集合合并）。

💡 口诀：Kruskal 排边序，小边先来不圈地（不成环就选）。

🌱 Prim（普里姆）：从一点往外长

从任意一个点出发，每次都从「已经连上的点」向外找一条最短的边把新点加进来，像小树慢慢长大，直到 n 个点都连上。Kruskal 和 Prim 都能求出最小生成树，总权值一样。

💡 口诀：Prim 从一点长树，每次挑最近的邻居；n 点树有 n−1 条边。

🧭 最短路径：怎么走最近

📍 Dijkstra（迪杰斯特拉）：一个起点到所有点

从起点出发，每次在还没确定的点里挑「当前距离最小」的点确定下来，再用它去更新邻居的距离（松弛）。要求边权不能为负。朴素实现 O(V²)，用小根堆/优先队列优化后 O((V+E)logV)。

💡 口诀：Dijkstra 单源最短路，每次挑最近的点敲定，再帮邻居更新距离。

🔄 Floyd（弗洛伊德）：任意两点之间

三层循环枚举「中间点 k」，看经过 k 会不会更近：dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])。能处理负权边，但不能有负权环。时间复杂度 O(n³)。

💡 口诀：Floyd 三层循环试中间点，O(n³) 求任意两点最短路。

💻 读代码：从邻接矩阵找最短距离

🗺️ 例子：4 个点的带权无向图

看得懂就好，不用背。weight[i][j] 表示 i 到 j 的边长，对称矩阵：

int weight[4][4] = {
  { 0, 1, 7, 100}, // 0 到各点：0、1、7、∞
  { 1, 0, 5, 15},
  { 7, 5, 0, 6},
  {100, 15, 6, 0}};

从 0 到 3：直接走要 100；0→1→3 = 1+15 = 16；0→2→3 = 7+6 = 13；0→1→2→3 = 1+5+6 = 12 最短。

🌟 会挑算法：先看题目要什么

🔍 选择口诀

「把全部点连通且边权和最小」→ 最小生成树（Kruskal/Prim）；「一个点到其它点的最短路」→ Dijkstra（非负权）；「任意两点最短路 / 有负权边」→ Floyd（无负权环）。

💡 口诀：连成一片找最小树；一个起点 Dijkstra；任意两点 Floyd。

🌟 行业实际

修高速、铺水管电网用最小生成树；地图导航用 Dijkstra（以及它的堆优化版）；航空公司排联程、社交网络找「六度分隔」用图算法。搜索引擎、物流调度全都是图的天下。

🎯

闯关小锦囊 · 考点提醒

邻接矩阵占 n×n；邻接表无向图共 2e 个边节点、有向图共 e 个边节点。
n 个顶点的连通图，生成树 / 最小生成树有 n−1 条边；连通图一定有生成树。
Kruskal：边按权排序，小边先选、不成环就收；Prim：从一点出发每次挑最近的边长大。
Dijkstra 求单源最短路（非负权），朴素 O(V²)，堆优化 O((V+E)logV)；Floyd 三层循环 O(n³) 求任意两点。
Floyd 允许负权边但不允许负权环；Dijkstra 遇到负权边会出错。
判断连通/判环：DFS、BFS 都可以，时间复杂度都是 O(V+E)。

🎮

学完了？来闯关！

下面 16 个小挑战，点一点就能玩

Demo 原型 · 每个知识点独立页面 · 暂不含真实编译与进度存储。