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适合找“最短步数”附知识点思维导图图论入门 ├── 基本概念点、边、权 ├── 图的三兄弟 │ ├── 无向图双向朋友 │ ├── 有向图单向关注 │ └── 带权图有距离 ├── 存储方法 │ ├── 邻接矩阵课程表法 │ └── 邻接表通讯录法 └── 三大问题 ├── 遍历问题走迷宫 ├── 最短路径找最近的路 └── 最小生成树用最少的路连所有人