图的表示方法

我觉得去理解数据结构的时候,需要注意到它其实包含两个层面。一个层面是高一级的,从功能、接口的角度去理解,比如说堆,有什么功用,都有怎样的 API;另一个层面是低一级的,从结构和实现的角度去理解,比如堆的实现,可以用数组实现,也可以用单独的节点对象+指针实现。上面一层相同,但是下面一层不同,功能上可能基本一致,但是性能上针对不同的应用场景就可以天差地别。

图就是另外一个典型例子,无向图也好,有向图也好,这是从功能上说的,但它们各自的实现,或者说基于的 “表示方法” 有多种。我记得在学习数据结构早期,基本上没有比较系统地去比较它们,那今天就把这一课补上。

比如上面这个有向图,四个顶点

[……]阅读全文

Google 矩阵

google matrix 使用一款搜索引擎,我们希望搜索结果能够拥有最佳的排序,Google 为它最核心的排序算法 PageRank 申请了专利。在 PageRank 以前,排序大多依靠对搜索关键字和目标页的匹配度来进行的,这种排序方式弊端明显,尤其对于善于堆砌关键字舞弊的页面,很容易就跳到了搜索结果的首页。Larry Page 和 Sergey Brin 开始着手解决这个问题,Google 排序的继承来自于互联网上网页之间的链接关系。一张网页被其它网页引用的次数越多,可以简单地认为这样的网页越受欢迎,当然在结果列表中应该越靠前。

前面提到了目标网页被引用网页的“ 数量”,另一条重要的判定 PageRank 级别的

[……]阅读全文

back to top