这篇讲的是连通分量，连通分量是深度优先搜索算法的一个应用。 每进行了一次dfs，就会找到一条连通分量。 定义如下的API {代码...} 具体实现如下： {代码...} 同样还能解决双色问题，即“能够用两种不同颜色将顶点着色，使得相邻的顶点颜色不同吗？等价于这个图是一个二分图吗？ {代码...}

上一篇讲了从一个顶点到另一个顶点是否存在路径，用的时深度优先搜索。那还有一个重要的问题就是，“从s到v是否存在一条路径，如果有找出其中最短的那条。”最短路径问题 当然这路考虑的是每条边的都是权值为1的情况。 解决这个问题的算法就是广度优先搜索算法 下面给出其实现代码，其中的使用了一个队列用来保存需要遍历...

在图中，我们很自然地会问这几个问题 从一个顶点s能否到达顶点v? 以s为顶点能到达的所有顶点? 解决能否到达问题的算法就是深度优先算法，使用深度优先算法获得的从s到v的路径的时间与路径的长度成正比。 {代码...} 这样通过调用pathTo(v)就可以知道到任意顶点v的路径。

无向图的数据结构 {代码...} 无向图的API {代码...} 实现很简单 {代码...} 既然实现了图这种数据结构，那么接下来可以考虑图的处理算法了。见下一篇

下午写了一下红黑树的插入操作，这样就可以构造一棵红黑树。红黑树在很多地方都非常重要。例如：给你上千万或上亿数据(有重复),统计其中出现次数最多的前 N 个数据 ，上千万或上亿的数据,现在的机器的内存应该能存下(也许可以,也许不可以)。 所以考虑采用 hash_map/搜索二叉树/红黑树等来进行统计次数。然后就是取出前 N...

常见的一个问题，寻求最小的K个数，或者top K问题。利用构建最大堆，可以在O(k+(n-k)logk) = O(n*logK)时间内实现。 顺便再来复习一下最大堆。

Boyer-Moore算法用于搜索匹配字符串，如Word中的查找功能，是一个十分巧妙高效的算法。下面是Moore教授自己给出的例子:[链接] 根据上面的例子来说一下算法思想： 假定被匹配的字符串为A”This is a simple Example" 搜索的字符串为B“Example” 与暴力匹配不同的是，这个算法从搜索字符串的结尾开始匹配，将A和B的头对齐。...

考虑任意节点，以该节点为根，相聚最远的两个节点为U,V与这个根的关系有两种情况： 1.如果路径经过root，U,V是属于不同子树的，而且是距离子树的根最远的节点 2.若不经过root，U,V一定是以root的子节点为root的某棵树中距离最远的节点

{代码...}

{代码...}