各位如果看到博客内有广告,可以动手点一点,谢谢

MENU

搜索(2)

June 24, 2018 • Read: 387 • 算法

上一节我们以图的遍历为例讲了深度优先搜索算法和实现程序。上一节中的深度优先算法可以算是基本款,很多深度优先搜索的题目就是在这个基本款的程序上进行修改

DFS

加强版DFS首先增加或者说变化的一点是顶点颜色。我们在基本款代码里使用visited数组来区分顶点,也就是visited[x=true表示x顶点已经访问过,visited[x]=false表示还没访问过x顶点。加强版中使用”颜色”来区分顶点
image
一开始所有顶点都是白色的,白色代表顶点还没有被访问过。当我们第一次遍历到一个顶点x时,会把顶点x染成灰色。灰色代表该顶点x已经被访问过(调用过DFS(x)),但是还没有访问结束(DFS(x)退出回溯),当前正在遍历的顶点还是经过x到达的

如果顶点x的所有相连的顶点都访问过了,马上要退出DFS(x)向上一层回溯。我们会将x的颜色染成黑色。黑色代表这个顶点的遍历已经结束,之后我们再也不会访问这个顶点。上面这个图就是我们已经遍历了1->2->3->4,并且在4号顶点发现无路可走,回溯到3号顶点时的状态。123是灰色,4是黑色,56是白色

除了用三种颜色区分顶点的状态,算法导论加强版还给“开始遍历一个顶点”事件和”结束遍历一个顶点 “事件都打上了一个时间戳。所谓时间戳就是一个自增的整数,比如从1开始遍历的时间戳是1。然后1->2开始遍历2号节点,时间戳就是2。如果2再往后找不到新的顶点,那么2就要回溯,在回溯前会被标记为时间戳=3……
image
上面这个图描述的是,我们已经遍历了1->2->3->4,并且在4号顶点发现无路可走,回溯到3号顶点时的状态。注意顶点里的数字是时间戳,斜杠左边是开始时间戳,右边是结束时间戳;顶点编号被省略了。灰色顶点123有开始的时间戳,分别是123;黑色4号顶点开始/结束时间戳都有,是4/5。白色顶点56由于还没有被遍历到,所以没有时间戳

直到整个图遍历结束,每个访问到的顶点都会被打上了两个时间戳。一个是DFS(x)开始的时候,时间戳是D(x);另一个是DFS(x)要结束前,时间戳是F(x)

下面以上图为例,我们看一下有颜色标记和时间戳的加强版DFS的过程:
image
红色的边表示沿着这条边到达了一个白色的顶点,也就是还未遍历到的新顶点。虚线边表示沿着这条边到达了一个灰色节点。黑色边表示当前顶点已经遍历结束,沿着之前的红色边回溯到上一个顶点

图中这个DFS的时间戳是很有意思的,有的地方叫做DFS序号。如果我们把每个顶点的时间戳看成区间,左端点是D(x),右端点是F(x),那么这些区间会有像括号一样的嵌套关系,如下图:
image
我们可以看出来任意两个顶点的区间只可能有2种关系:(1)两个区间相离;(2)一个区间包含另一个区间。换句话说,不会出现像[1, 10], [4, 13]这样两个区间互相跨立的情况。这种关系可以形象的看成是一个匹配合法的括号序列

例1 蓝桥杯——版本分支

image
题目大意就是给定一个包含N个顶点的树,顶点编号1~N,其中1是根节点。然后有Q个询问,每次询问x是不是y的祖先节点,是输出YES不是输出NO。特别的,根据样例里询问x=1,y=1时输出YES,我们知道自己也算自己的祖先

思路1 暴力

这道题一个最直观暴力的做法就是对于每一个询问,从y一直向上找父节点,如果遇到x那么就输出YES;如果一直找到根节点也就是1号节点还没遇到x,那么就输出NO。伪代码如下:

Query(x,y)
{
    while y != x AND y !=1
        y = y.parent
    return x == y
}

这个算法对于每一个询问的时间复杂度是O(N)的,所以总的时间复杂度是O(NQ)的,大约可以通过30%的数据。想拿到满分,一种做法就是利用刚才我们讲到的DFS时间戳区间

思路2 DFS时间戳

我们从1号节点开始DFS,同时求出每个节点的时间戳D(x)和F(x)。例如对于样例,我们可以得到如下图所示的结果:
image

也就是1~6号节点对应的区间依次是[1, 12], [2, 5], [6, 11], [7, 8], [3, 4], [9, 10]。根据我们之前的结论:区间只可能有相离和包含两种关系,我们可以发现x是y的祖先版本当且仅当x的区间包含y的区间

例如在上图中[2, 5]包含[3, 4]; [6, 11]包含[7, 8]和[9, 10];根节点[1, 12]包含所有

在我们经过DFS得到时间戳D(x)和F(x)之后,再利用时间戳判断x是不是y的祖先节点就非常简单了:

Query(x,y)
{
    return D(x) <= D(y) AND F(y) <= F(x)
}

只需判断D(x)D(y)F(x)F(y)的大小关系,时间复杂度是O(1)的。所以Q个询问的时间复杂度是O(Q)的。再加上DFS的时间复杂度O(N) (因为是树所以边数也是O(N)的),算法总体的时间复复杂度是O(N+Q)的。很明显比之前的O(NQ)快很多

下面我们来看一下这道题目的完整代码:

#include<iostream>
#include <vector>
using namespace std;
int n,q,ts = 0;
vector<int> g[100001];
int d[100001],f[100001];
void dfs(int x)
{
    ts++;
    d[x] = ts;
    for(int i = 0;i < g[x].size();i++)
    {
        int y = g[x][i];
        dfs(y);
    }
    ts++;
    f[x] = ts;
    return;
}
int main() 
{
    cin >> n >> q;
    for(int i = 2;i <= n;i++)
    {
        int u,v;
        cin >> u >> v;
        g[u].push_back(v);
    } 
    dfs(1);
    while(q--)
    {
        int x,y;
        cin >> x >> y;
        if(d[x] <= d[y] && f[y] <= f[x])
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
    return 0;
}

第21~27行是在读入树的边。注意这里我们虽然还是用数组套vector的g来保存边。但是这个g和上一节我们讲的邻接表有些不一样。这道题由于是有根树,我们知道谁是谁的父节点,所以我们g[x]保存的是x的所有子节点。与邻接表相比,g[x]没有保存x的父节点

第7~18行是DFS函数,参数x是当前访问的节点编号。Ts是一个全局变量,表示全局的时间戳,初始值是0。在第8行刚一进入DFS(x)函数,也就是开始访问x节点时,ts要累加1;以及在16行遍历完x的所有邻居节点,要退出DFS(x),结束对x的遍历时,ts也要累加1

第10行是我们把当前的时间戳ts的值赋给d[x],也就是计算x的开始时间戳。第11~15行是在处理所有x的子节点i,递归调用DFS(i)进行遍历。注意给定的图是一棵有根树,并且g[x]保存的是x的子节点。所以我们在这里可以确定i还没有被遍历过,不需要用visited数组来辅助判断

最后在第17行,要退出dfs(x)之前,我们计算x的结束时间戳,也是当前的ts的值。第29行执行完以后,我们就完成了对这棵树的深度优先搜索,每个节点的开始时间戳和结束时间戳也都求出来了。第31~38行就是在处理每一个询问,对于询问x是不是y的祖先,我们只要判断一下时间戳区间的包含关系即可确定答案

Archives Tip
QR Code for this page
Tipping QR Code
Leave a Comment