c++图论
信奥图论入门知识体系
一、什么是图论？
简单比喻：
图就像一张关系地图，用“点”表示事物，用“线”表示事物之间的关系。
比如：
- 点可以是你和你的朋友们
- 线表示你们之间是不是好朋友（连线就是好朋友，不连线就是还不认识）
二、图的基本组成部分（像搭积木一样简单）
1.顶点（Node/Vertex）
- 也叫“点”，用圆圈表示
- 例子：每个城市、每个同学、每个地铁站
2.边（Edge）
- 点与点之间的连线
- 例子：城市之间的公路、同学之间的友谊、地铁站之间的轨道
3.权重（Weight）（可选）
- 给边加上“数字标签”
- 例子：公路的长度、坐地铁需要的时间
三、图的三种常见类型（就像不同种类的网络）
1.无向图
- 边没有方向，像双向街道
- 例子：微信好友关系（互为好友）
A — B 表示 A 和 B 是朋友2.有向图
- 边有箭头，像单行道
- 例子：微博关注（你关注他，但他不一定关注你）
A → B 表示 A 关注了 B3.带权图
- 边上标有数字
- 例子：地图上的距离
A --5-- B 表示从 A 到 B 要走 5 公里四、图论里的“好朋友”关系（重要概念）
1.邻居（邻接点）
- 如果两个点直接有边相连，它们就是邻居
- 例子：你的同桌就是你的“邻居同学”
2.路径
- 从一个点到另一个点走过的路线
- 例子：从家到学校的路线：家 → 公交站 → 学校
3.环
- 起点和终点是同一个点的路径
- 例子：绕操场跑一圈回到起点
五、两种存储图的“记事本方法”（编程时会用到）
方法1：邻接矩阵（像课程表）
- 画一个表格，行和列都是所有点
- 如果点 i 和点 j 有边，就在表格(i,j)位置写 1（无向图要写两次）
- 适合边比较多的图
例子（三个同学 A、B、C 的关系）：
A B C A 0 1 1 ← A 和 B、C 都是朋友 B 1 0 0 ← B 只和 A 是朋友 C 1 0 0 ← C 只和 A 是朋友方法2：邻接表（像通讯录）
- 给每个点建一个“好朋友名单”
- 只记录真正有边连接的点
- 适合边比较少的图
例子：
A的好友列表：B, C B的好友列表：A C的好友列表：A六、三个经典图论问题（像闯关游戏）
关卡1：走迷宫问题（图的遍历）
任务：访问图中的每一个点，不能漏掉
两种走法：
- 深度优先搜索（DFS）：像走迷宫，一条路走到黑，走不通再回头
- 广度优先搜索（BFS）：像水波纹扩散，一圈一圈往外走
现实例子：
- DFS：玩密室逃脱，先探索一条路到底
- BFS：找人帮忙，先问所有直接朋友，再问朋友的朋友
关卡2：最短路径问题
任务：找到两点之间最短的路线
现实例子：
- 地图导航找最短路线
- 传悄悄话，找传递次数最少的路径
简单算法：Dijkstra算法（像“贪心的小蚂蚁”）
步骤： 1. 从起点开始，标记到起点的距离为0 2. 每次选一个最近的点，更新它邻居的距离 3. 重复直到找到终点关卡3：最小生成树问题
任务：用最少的边连接所有点，让总长度最小
现实例子：
- 给几个村庄修路，让所有村庄连通，且总公路长度最短
- 用最少的网线连接所有电脑
简单算法：Kruskal算法（像“拼拼图”）
步骤： 1. 把所有边按长度从小到大排序 2. 从最短的边开始选，如果选了不会形成环，就加入 3. 直到选了 n-1 条边（n 是点数）七、学习建议
1.先画图，再想算法
- 把问题画成点线图
- 在图上模拟算法步骤
2.从生活例子入手
- 用朋友关系理解无向图
- 用微博关注理解有向图
- 用地图距离理解带权图
3.编程实践顺序
第1步：学习用数组存图（邻接矩阵） 第2步：实现 DFS/BFS 遍历 第3步：解决简单的最短路径问题 第4步：尝试最小生成树4.推荐练习题目
- 数一数图中有多少个连通块（像数有几个小岛）
- 找两个点之间有没有路径
- 计算从起点到每个点的最短距离（边权都是1）
- 判断图中是否有环
5.常见困惑与解答
问：为什么要有两种存图方法？
答：就像记笔记，有时候用表格清楚，有时候用列表方便问：DFS和BFS哪个更好？
答：要看任务！DFS适合找“有没有解”，BFS适合找“最短步数”
附：知识点思维导图
图论入门 ├── 基本概念（点、边、权） ├── 图的三兄弟 │ ├── 无向图（双向朋友） │ ├── 有向图（单向关注） │ └── 带权图（有距离） ├── 存储方法 │ ├── 邻接矩阵（课程表法） │ └── 邻接表（通讯录法） └── 三大问题 ├── 遍历问题（走迷宫） ├── 最短路径（找最近的路） └── 最小生成树（用最少的路连所有人）