正如可以通过将道路交通图模型化为有向图来找到从一个城市到另一个城市之间的最短路径,我们也可以将一个有 阅读更多…
(多源最短路径问题) 在本章中,我们考虑如何找到一个图中所有结点之间的最短路径,该问题在计算所有城市 阅读更多…
单源最短路径:给定一个图,我们希望找到从定源节点s到每个结点v的最短路径。 松弛操作:本章的算法需要 阅读更多…
最小生成树就是在一个图中找到一条树,这些树可以包括图中所有的点并且这些 边权重的代价是最低的。如下图 阅读更多…
1.图的表示 对于图G=(V,E),我们可以用两种标准方法表示。一种是邻接链表,一种是邻接矩阵。 如 阅读更多…
在摊还分析中,我们求数据结构的一个操作序列中所执行的所有操作的平均时间,来评价操作的代价。 1.聚合 阅读更多…
求解最优化问题的算法通常需要经过一系列的步骤,在每个步骤都面临多种选择。对于许多最优化问题,使用动态 阅读更多…
动态规划(dynamic programming)与分值方法相似,都是通过组合子问题的解来求解原问题 阅读更多…
上一章的二叉搜索树(平均时间复杂度O(n)),很容易在n个长度下形成高度为n-1的一条链,为了避免这 阅读更多…
1.什么是二叉搜索树 二叉搜索树:对任何结点x,其左子树中的关键字最大不超过x.key,其右子树的关 阅读更多…