Processing math: 100%

【算法题】《图论和搜索》复习笔记

作者： 作者的头像   FanXY ,  2022-04-29 03:05:02 ,  所有人可见 ,  阅读 565

2


3

【算法题】《图论和搜索》复习笔记

我的网站=> 分享了我关于前后端的各种知识和生活美食~

我于Acwing平台分享的零散刷的各种各样的题

分类题单

每道题题解部分给出了我对这道题的详细解析和理解，如果有不对的地方，欢迎指正

1.搜索问题

1.DFS深度搜索

1.1 DFS模板

题目 题解
1. N皇后问题 （数的字典序升级版） 题解
2. 树的重心 （树的深度优先遍历——深入理解递归） 题解
3. 电话号码的字母组合 leetcode17 dfs 字符串 题解
4. 括号生成 leetcode 22 dfs单种括号 题解
5. 解数独 leetcode 37 dfs格点分组 题解
6. 组合总和 leetcode 39 dfs完全背包 题解
7. 组合总和2 leetcode40 dfs 多重背包 题解
8. 全排列I leetcode 46 dfs排列型枚举 题解
9. 全排列II leetcode 47 dfs排列型枚举 题解
10. 单词搜索 leetcode 79 网格搜状态路径 题解
11. 复原IP地址 leetcode 93 dfs搜索合法分隔数字 题解
12. 题解
13. 题解
14. 题解
15. 题解
16. 题解
17. 题解
18. 题解
19. 题解

1.2 DFS之连通性

题目 题解
1. 迷宫 题解
2. 红与黑 题解
7. 题解
8. 题解
9. 题解
10. 题解
11. 题解

1.3 DFS之搜索顺序

题目 题解
1. 马走日 题解
2. 单词接龙 字符串子串判断融合dfs 题解
3. 分成互质组 融合组合型枚举 + 剪枝优化 题解
4. 题解
5. 题解
7. 题解
8. 题解
9. 题解
10. 题解
11. 题解
----------

1.4 DFS之剪枝

题目 题解
1. 小猫爬山 题解
7. 题解
8. 题解
9. 题解
10. 题解
11. 题解

1.5 DFS之迭代加深

题目 题解
1. 加成序列 题解
2. 题解
7. 题解
8. 题解
9. 题解
10. 题解
11. 题解

1.6 DFS之双向搜索

题目 题解
1. 送礼物 题解
2. 题解
7. 题解
8. 题解
9. 题解
10. 题解
11. 题解

2.BFS广度搜索

2.1 BFS模板

题目 题解
1. 走迷宫 题解
2. 八数码 （最短步数模型：一维和二维数组的坐标转换） 题解
3. 图中点的层次 （树的宽度优先遍历） 题解
4. 拓扑排序 (入度和环的判断) 题解
5. 矩阵距离 多源bfs 题解
6. 魔板 八数码升级版-最小步数模型 题解
7. 题解
8. 题解
9. 题解
10. 题解
11. 题解

2.2 Flood Fill

题目 题解
1. 池塘计数 题解
2. 城堡问题 题解
3. 山峰和山谷 题解
4. 题解
5. 题解
7. 题解
8. 题解
9. 题解
10. 题解
11. 题解

2.3 双端队列广搜

题目 题解
1. 电路维修 题解
2. 通信线路双端+二分 题解
7. 题解
8. 题解
9. 题解
10. 题解
11. 题解

2.4 双向广搜模型

题目 题解
1. 字串变换 题解
2. 题解
8. 题解
9. 题解
10. 题解
11. 题解

2.5 A star

题目 题解
1. 第K短路 题解
2. 八数码操作记录版 题解
7. 题解
8. 题解
9. 题解
10. 题解
11. 题解

2.图论问题

2.1 最短路问题 模板题

题目 题解
1. Djkstra 稠密图 题解
2. Djkstra 稀疏图 (堆优化) 题解
3. Bellman-ford 有边数限制负权边的最短路 题解
4. SPFA 求最短路 题解
5. SPFA 判断负环 题解
6. Floyd 求最短路 题解
7. 题解
8. 题解
9. 题解
10. 题解

2.1.1 单源最短路的建图方式

题目 题解
1.热浪 题解
2.信使 多源解单源 题解
3.香甜的黄油单源做n次 题解
4. 迷宫问题 迷宫求方案 题解
5. 武士风度的牛 题解
6. 抓住那头牛 题解
7. 最小花费乘积边权抽象为最短路 题解
8. 最优乘车 线路图转化节点图 题解
8. 题解
9. 题解
10. 题解
11. 题解

2.1.2 单源最短路的综合题

题目 题解
1. 新年好就是做多次最短路然后打表dfs 题解
2. 通信线路双端+二分 题解
3. 道路与航线拓扑图+Dijkstra 题解
4. 最优贸易dp+反向图解决复杂度 题解
5. 题解
6. 题解
7. 题解
8. 题解
9. 题解
10. 题解
11. 题解

2.1.3 单源最短路的扩展应用

题目 题解
1. 选择最优线多源最短路 题解
2. 最短路计数最短路和拓扑结构 题解
3. 题解
4. 题解
5. 题解
6. 题解
8. 题解
9. 题解
10. 题解
11. 题解
----------

2.1.4 Floyd综合题

题目 题解
1. 牛的旅行因求最小引发的R1和R2边界 题解
2. 排序floyd解决不等式连接 题解
3. 观光之旅floyd解决最小环 题解
4. 题解
5. 题解
6. 题解

2.1.5 负环

题目 题解
1. 黑洞模板题 题解
2. 观光奶牛spfa边权转化 题解
3. 题解
4. 题解
5. 题解
6. 题解
8. 题解
9. 题解
10. 题解
11. 题解
----------

2.2 最小生成树

2.2.1 最小生成树模板

题目 题解
1. Prim 最小生成树 题解
2. Kruskal 最小生成树 题解
3. 题解
4. 题解
8. 题解
9. 题解
10. 题解
11. 题解

2.2.2 最小生成树综合题

题目 题解
1.最短网络prim模板题 题解
2.局域网kruskal多树 题解
3.繁忙的都市最小生成树的性质 题解
4.联络员kruskal处理必选边 题解
5.连接格点二维格点化一维 题解
6. 题解
7. 题解
8. 题解
9. 题解
10. 题解
11. 题解

2.2.3 最小生成树拓展应用

题目 题解
1.新的开始虚拟源点 题解
2.北极通讯网络连通块的数量 题解
3. 题解
4. 题解
5. 题解
6. 题解
7. 题解
8. 题解

2.3 二分图

题目 题解
1. 染色法判定二分图 题解
2. 匈牙利算法——二分图的最大匹配（渣男算法） 题解
8. 题解
9. 题解
10. 题解
11. 题解

2.4

题目 题解
8. 题解
9. 题解
10. 题解
11. 题解
8. 题解
9. 题解
10. 题解
11. 题解

0 评论

1024
x