网站SEO优化

图基本算法(一)-搜索引擎

  • 时间:
  • 浏览:20185

本文是学习 Algorithms on Graphs 的笔记 。

图表示


邻接矩阵

邻接表

边链表

不同的表示方式决定了不同操作的时间复杂度  。

图遍历


问题:我们怎么能够找到 A 能够达到的所有顶点  ?

算法描述:

上面的算法还需要解决两个问题:

  1. 怎么记录哪些边 / 顶点已经访问过了  ?

  2. 以什么顺序来访问新加进来的顶点  ?

我们可以通过一个 map 来记录顶点是否访问过 ,而对于新增的顶点  ,我们采样深度优先的方案  ,一直访问下去  。

DFS


如果我们要访问图中所有的点  ,方法如下:

Previsit and Postvisit Functions

我们在 explore 节点的时候  ,加上 Previsit 和 Postvisit 功能:

根据这个功能我们就可以实现一个时钟:

连通性


问题

我们可以通过修改 DFS 来做

Directed Acyclic Graphs 有向非循环图


定义:

A source is a vertex with no incoming edges.

A sink is a vertex with no outgoing edges.

现在我们的目标是找到一个 Linear Ordering  ,什么叫 Linear Ordering ,看下图:

怎么找呢  ?根据 sink 的概念  ,我们先去找 sink

整个过程如下:

  • Find sink.

  • Put at end of order.

  • Remove from graph.

  • Repeat.

整个算法如下:

具体来说就是先按 DFS 访问图  ,然后再根据 Postvisit clock 排序从大到小就是我们需要求的值  。

因为 DFS 总是一直走到最深处  ,即先找到 sink 为 0 的节点  。

Strongly Connected Components


在无向图中有联通一说 ,在有向图中会更复杂点

定义

在有向图中 ,联通意味着集合里的点都能互相到达  ,画到一起就是下面这样子:

叫做 metagraph  ,也是一个 DAG  。

下面我们来描述如何计算一个 SCC(Strongly Connected Components) 。

SCC 计算

简单算法

另一种思路是跟找 sink 节点一样  ,此时我们找一个聚合的 sink  。

 ,但是怎么找到呢?

在无向图中  ,我们对 postOrder 进行排序  ,postOrder 小的就是 sink  ,在有向图中  ,我们有下面的理论:

因此有大的 postOrder 的是 source  ,但是我们需要的是 sink  ,因此我们可以做如下操作:

下面我们开始给出具体的算法 。

基本算法

上面做法就是不断通过 DFS 遍历  ,然后找到 postOrder 最大的顶点  ,从他开始找到所有能达到的点  ,然后删除  ,不断重复  。

下面是一个改进算法 ,不用每次都 dfs:

总结


本文是对 Algorithms on Graphs 第 1-2 周 课程的一个记录  ,笔记更多的是给自己复习时快速查阅用  。

你的鼓励是我继续写下去的动力  ,期待我们共同进步  。
    

猜你喜欢