Content
11 Lessons • 0 Quizzes • 0 Challenges
简介
- 1
本课程是关于什么的？
复习：渐近符号与数学基础
- 1
开始学习对数
- 2
思考一下：运行时间
- 3
运行时间与输入规模的关系
- 4
比较运行时间
- 5
大O表示法
- 6
关于大O表示法中的常数项的思考
- 7
一些有用的事实
- 8
一个大O复杂度练习
- 9
利用反证法技巧
- 10
练习：增长量级
- 11
测验：大O表示法
图的使用
- 1
图
- 2
邻接矩阵
- 3
邻接表
- 4
有向图
- 5
加权图
- 6
子图、路径、环路和连通分量
- 7
树
- 8
二分图
- 9
测验：图的处理
深度优先搜索及其应用
- 1
深度优先搜索
- 2
有向图中的边分类
- 3
练习：对有向图的边进行分类
- 4
无向图中的边分类
- 5
练习：对无向图的边进行分类
- 6
识别割点
- 7
练习：识别割点
- 8
拓扑排序
- 9
练习：按拓扑顺序对顶点进行排序
- 10
思考练习：在有向图中检测环
- 11
强连通分量的特征分析
- 12
Tarjan 算法
- 13
练习：实现 Tarjan 算法
- 14
Kosaraju-Sharir 算法
- 15
练习：实现Kosaraju-Sharir算法
- 16
测验：深度优先搜索及其应用
前情提要：最短路径
- 1
最短路径问题
- 2
关于最短路径的思考
- 3
测验：最短路径术语
- 4
广度优先搜索
- 5
无权有向图中的最短路径
- 6
练习：打印最短路径
- 7
测验：广度优先搜索与最短路径
加权有向图中的单源最短路径
- 1
单源最短路径问题
- 2
练习：路径松弛
- 3
DAG的即时算法
- 4
思考练习：有向无环图中的最长路径
- 5
练习：有向无环图中的最短路径
- 6
迪杰斯特拉算法
- 7
练习：迪杰斯特拉算法
- 8
思考练习：负权重
- 9
贝尔曼-福特算法
- 10
练习：贝尔曼-福特算法
- 11
思考练习：贝尔曼-福特算法
- 12
测验：单源最短路径
所有点对之间的最短路径
- 1
约翰逊算法
- 2
练习：约翰逊算法
- 3
弗洛伊德-沃舍尔算法
- 4
练习：弗洛伊德-沃舍尔算法
- 5
测验：所有点对之间的最短路径
最小生成树
- 1
最小生成树（Minimum Spanning Tree）
- 2
测验：最小生成树
- 3
思考练习：唯一性
- 4
普里姆算法
- 5
练习：按照普里姆算法选择边
- 6
练习：普里姆算法
- 7
克鲁斯卡尔算法
- 8
并查集数据结构的实现
- 9
练习：按照克鲁斯卡尔算法选择边
- 10
练习：克鲁斯卡尔算法
- 11
思考练习：最小生成树与最短路径
- 12
测验：最小生成树
流
- 1
网络流
- 2
福特-福克森算法的核心思想
- 3
福特-福克森算法：细节说明
- 4
思维练习：有理数容量
- 5
练习：福特-福克森算法
- 6
测验：网络流
匹配与顶点覆盖
- 1
匹配
- 2
二分图中的最大匹配
- 3
练习：二分图中的最大匹配
- 4
最小顶点覆盖的对偶问题
- 5
二分图中的最小顶点覆盖
- 6
练习：二分图中的最小顶点覆盖
- 7
Gale-Shapley 算法
- 8
证明盖尔-沙普利算法对提议者更有利
- 9
思考练习：Gale-Shapley 算法中的不对称性
- 10
练习：寻找稳定匹配
- 11
测验：匹配与顶点覆盖
结论
- 1
最后的总结
Certificate of Completion
Showcase your accomplishment by sharing your certificate of completion.
Course Author:Anonymous User