加载中...
avatar
文章
38
标签
5
分类
5
首页
文章
  • 归档
  • 标签
  • 分类
休闲
  • 影院
  • 游戏
工具箱
  • 画廊
  • 工具
留言版
友链
  • 良师益友
个人
  • 关于
水货不水
首页
文章
  • 归档
  • 标签
  • 分类
休闲
  • 影院
  • 游戏
工具箱
  • 画廊
  • 工具
留言版
友链
  • 良师益友
个人
  • 关于

w12-15图论

发表于2024-12-18|更新于2025-01-01|Algorithm
|阅读量:
文章作者: Fat1ger
文章链接: http://seafoodfat1ger.github.io/2024/12/18/Algorithm/%E5%9B%BE%E8%AE%BA/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 水货不水！
Algorithm
cover of previous post
上一篇
w16 P NP NPC
cover of next post
下一篇
BUAA_OOP_2024_碎碎念总结
相关推荐
cover
2024-12-22
w1-w3 预备知识
cover
2024-12-24
w11 贪心
cover
2024-12-18
w16 P NP NPC
cover
2024-12-22
w4-w5 分而治之
cover
2024-12-23
w7-w10 动态规划
avatar
Fat1ger
燕子不归春事晚,一汀烟雨杏花寒
文章
38
标签
5
分类
5
github地址
公告
This is my Blog
目录
  1. 1. 图算法
    1. 1.1. 图的概念
    2. 1.2. BFS
      1. 1.2.1. 算法
        1. 1.2.1.1. 辅助数组
    3. 1.3. DFS
      1. 1.3.1. 算法
        1. 1.3.1.1. 辅助数组
      2. 1.3.2. 后向边/树边
        1. 1.3.2.1. 无向图
        2. 1.3.2.2. 有向图
      3. 1.3.3. 括号化定理
      4. 1.3.4. 白色路径定理
    4. 1.4. 环路判定（有向图）
    5. 1.5. 拓扑排序（DAG）
      1. 1.5.1. BFS
      2. 1.5.2. DFS
      3. 1.5.3. 证明
    6. 1.6. 强连通分量（有向图）
      1. 1.6.1. 算法
        1. 1.6.1.1. 算法框架
      2. 1.6.2. 证明
    7. 1.7. Prim 最小生成树（无向图）
      1. 1.7.1. 概念
      2. 1.7.2. 安全边辨识定理
      3. 1.7.3. 算法
        1. 1.7.3.1. 算法框架
        2. 1.7.3.2. 辅助数组
        3. 1.7.3.3. 原始算法
        4. 1.7.3.4. 优先队列
    8. 1.8. Kruskal 最小生成树（无向图）
      1. 1.8.1. 证明
      2. 1.8.2. 算法
        1. 1.8.2.1. 并查集
    9. 1.9. BFS 单源最短路径问题
    10. 1.10. Dijkstra 单源最短路径问题
      1. 1.10.1. 算法
        1. 1.10.1.1. 辅助数组
        2. 1.10.1.2. 算法框架
        3. 1.10.1.3. 原始算法
        4. 1.10.1.4. 优先队列
      2. 1.10.2. 证明
    11. 1.11. Bellman-Ford 单源最短路径问题
      1. 1.11.1. 算法
        1. 1.11.1.1. 辅助数组
        2. 1.11.1.2. 算法
    12. 1.12. Floyd 所有点对最短路径问题
      1. 1.12.1. 动态规划
      2. 1.12.2. 算法
    13. 1.13. 二分图
      1. 1.13.1. 判定
      2. 1.13.2. 最大匹配
    14. 1.14. 最短路径计数问题
  2. 2. 往年题1
    1. 2.1. 哈密顿路径(topo)
    2. 2.2. 路径统计问题(topo)
    3. 2.3. 货物运输(topo 反向建图)
    4. 2.4. 食物链计数(topo 24)
    5. 2.5. 马的遍历（BFS）
    6. 2.6. 灯塔照明问题（SCC 2-SAT）
    7. 2.7. Party（SCC 2-SAT）
    8. 2.8. 交通建设问题（MST）
    9. 2.9. 迷宫逃离问题（24 BFS状态拓展）
    10. 2.10. 老城区改造（SCC DFS）
    11. 2.11. MST贪心
    12. 2.12. 无向图定向问题（DFS）
  3. 3. 往年题2
    1. 3.1. 节点寻找（SCC缩点/反向建图）
    2. 3.2. 二分图判定（DFS/BFS染色）
    3. 3.3. 道路改建（Kruskal）
    4. 3.4. 新最短路径（分层图）
    5. 3.5. 班委评选(SCC缩点)
    6. 3.6. 最小点集（24 SCC 缩点）
    7. 3.7. 最小环（24 Floyd）
    8. 3.8. 连通性计数问题（SCC 缩点）
    9. 3.9. 观光计划（二分图最大匹配）
    10. 3.10. 颜色交错最短路（BFS状态拓展）
    11. 3.11. 闭合子图（SCC缩点）
    12. 3.12. 景区限流（二分图最大匹配）
    13. 3.13. 文件传送问题 (SCC缩点)
    14. 3.14. 传递闭包（Floyd？？？？）
    15. 3.15. 骨牌覆盖（二分图最大匹配）
    16. 3.16. 项目排序问题（topo）
    17. 3.17. 方程式求解（BFS）
    18. 3.18. 字母顺序（topo）
    19. 3.19. 删边问题（Kruskal）
    20. 3.20. 最小生成树性质的证明
    21. 3.21. 影响传播问题（BFS）
最新文章
Chapter8 WLAN
Chapter8 WLAN2025-06-01
Chapter7 IPv6
Chapter7 IPv62025-06-01
Chapter6 应用层
Chapter6 应用层2025-05-31
Chapter5 传输层
Chapter5 传输层2025-05-30
Chapter4 网络层
Chapter4 网络层2025-05-27
©2024 - 2025 By Fat1ger
框架 Hexo|主题 Butterfly
I wish you to become your own sun, no need to rely on who's light.