Algorithm

在简单的无向图模型中，我们使用 广度优先搜索 可以找到一个顶点到另一个顶点的最短路径（含顶点最少）。但是在加权图中情况有了很大的不同，需要考虑边的权重，这也更贴合许多实际问题。在加权图中的最短路径又可以理解为：找到从一个顶点到达另一个顶点的成本最小的路径。 为了能够解决更多的实际问题，方便提取问题的 …

讨论最小生成树要基于一种叫 加权图 的图模型。加权图的 加权 的含义是为图的每一条边关联一个权值或是成本。这种图相比于无向图可以更细致的描述问题。在一幅航空图中，边表示航线，权值则可以表示距离或是费用。在一幅电路图中，边表示导线，权值则可能表示导线的长度即成本，或是信号通过这条线路所需的时间。我们可 …

有向图中的有向是指图中每一条边都是有向的，每一条边连接的两个顶点都是一个有序对，它们的邻接性是单向的。能从 v->w ，不一定能从 w->v。这是有向图与无向图的本质区别，这种区别导致了两种图处理算法上的巨大差异。 1. 术语表 学习有向图的处理算法我们，需要了解一些定义和术语。如下表： …

图是由一组顶点和一组能够将两个顶点相连的边组成的逻辑结构，一般情况下为了和其他的图模型相互区别，又称图为无向图。在现实中的许多问题都可以抽象为一张图，结合优秀的算法，许多困难的问题都可以迎刃而解。 1. 术语表 和图有关的术语，定义非常多，其一部分内容如下： 术语 条件（释义） 顶点相邻 两个顶点通 …

使用基于红黑二叉查找树实现的查找算法，在平均情况下可以达到logN的效率。算法时间复杂度中，最小最优的就是常数级别的复杂度。有没有一种算法可以突破logN的查询复杂度到达常数级别的效率？答案就是散列表（Hash-Tables） 使用散列表需要将键转化为数组的索引，进而使用这个索引实现对数组中键值对的 …

我们都知道在一定程度上，程序 = 算法 + 数据结构。抛开数据结构说算法；抛开算法说数据结构，都是不太妥当的。而衡量一种数据结构的优略，一是看具体的问题需求，二是看其插入，删除排序等各个方面的性能。 在二分查找中我们使用的经典的数组实现，在查询的效率上直接达到了 lgN 对数级别的效率。但是数组这种 …

基于二叉查找树的查找和插入算法已经可以应用在许多的用例特定的应用程序上，但是在最坏的情况下，其结构退化为链表的性能急剧降低。这是让人无法容忍的。 由于二叉查找树的查询性能依赖于树的形态，如果可以找到一种方法可以让二叉查找树无论如何构造，都可以处于一个平衡的状态。我们就可以在更多的情况下应用二叉查找树 …

二分查找也称为折半查找（Binary Search），是一种效率较高的查找方法。它的一般查找过程为：首先，需要将待查的线性表按关键字排序，然后将表中间位置的元素的关键字与查找关键字比较。如果二者相等，则查找成功。如果不相等，则使用表的中间位置元素将表分为左右两个子表，查找关键字大于中间位置元素的关键 …

1. 优先队列 学习堆排序前，需要先了解优先队列是什么东西，引出数据结构：堆，最后学习堆排序。优先队列和普通的队列一样是一种数据结构，普通队列遵循的原则就是先进先出（FIFO）。而优先队列则是无论入队顺序，当前队列中优先级最高的元素先出。谈到优先级就有两种确定优先级的策略，一是值小的优先级高，二是值 …

快速排序算法可能是应用最为广泛的算法，它的实现较为简单而且排序效率比大多数算法都要高。仅需要一个辅助栈就可以实现在原数组上原地排序。但是快速排序算法稳定性不高，如果使用不当经常可能使算法的时间复杂度提升至 O(n^2) 级别。如何正确使用和优化快速排序是使用它之前必须研究的问题。 1. 基本实现 快 …