DFS(深度优先搜索)的非递归实现

突然想起来搜索是属于图论的,那么在解决图论的过程中把搜索解决掉。没想到非递归实现一下就搞了两天。虽然有些疑问还没有解决,但感觉已经可以写总结了,与其说总结,不如说一次尝试的记录(因为有个题最后还是TLE嘛)。(求规范代码!!!@啸爷)

众所周知,DFS的常规写法是递归实现,但递归普遍慢所以可以用模拟递归栈来循环实现。这样做有两个好处,一个是循环实现要比递归实现更快,第二个是因为模拟的栈是在程序中手动开的存储空间而不是通过递归用的计算机本身的栈,相当于外挂栈,在数量巨大的DFS的过程中不会爆栈。

当然,这是传统这么认为的,第二点没什么好说的,全局变量开的数组的确可以比递归用的栈大,所以更能有效的防止爆栈。但是关于第一点,我觉得还是有待考虑的。原因是我写的两种DFS非递归实现一个超时,一个和递归实现用时一样= =。我现在还不认为是我的代码有问题,如果大家发现问题请留言,感激不尽。

先说那个和递归实现一样的那个。

因为DFS基本上就分两种,一种是以遍历全图为目的的,需要边走边标记,而回退之后不用清除标记。目的是遍历全图嘛,标记正记录了走过的位置而方便找没有走过的位置。一种以搜索路径为目的,最短路也好,恰好到达也好,找的是一条路径问题,而最大的区别就是如果发生退栈,要进行清除标记,因为退栈后,可能存在别的路径依然会访问到这个结点。

这种DFS以POJ1562为例:

先看效果,我第一次提交是用DFS的递归实现,第二次是用非递归实现,虽然两个用时一样,但是我们还是能确定非递归实现不一定要比递归慢(我只能精确到这了TAT,我目前还没遇到递归TLE,非递归过的题目,但的确遇到了非递归TLE,递归过的题目= =)。

递归代码:

#include <iostream>
#include <cstring>

using namespace std;

char mp[150][150];
int chx[] = {1,0,-1,0,1,-1,1,-1};
int chy[] = {0,1,0,-1,1,-1,-1,1};
bool bj[150][150];

void dfs(int x,int y,int n,int m)
{
    for(int i = 0;i < 8;i++)
    {
        int tx = x + chx[i];
        int ty = y + chy[i];

        if(tx >= 0 && ty >= 0 && tx < n && ty < m)
        {
            if(bj[tx][ty] == 0)
            {
                bj[tx][ty] = 1;
                if(mp[tx][ty] == '@')
                {
                    dfs(tx,ty,n,m);
                }
            }
        }
    }
}

int main()
{
    int n,m;

    while(cin >> n >> m,n)
    {
        memset(bj,0,sizeof(bj));
        for(int i = 0;i < n;i++)
            cin >> mp[i];

        int ans = 0;
        for(int i = 0;i < n;i++)
        {
            for(int j = 0;j < m;j++)
            {
                if(bj[i][j] == 0 && mp[i][j] == '@')
                {
                    dfs(i,j,n,m);
                    ans++;
                }
            }
        }

        cout << ans << endl;
    }
    return 0;
}

很常规的写法,我们根据题目要求,找到‘@’就向下搜索,直到把相连的@全部标记完成,统计有几块不相连的@。

其中遇到相连的@便进入递归直到没有找到@再回退,换一个方向继续向下搜索。

而非递归实现就是模拟这个过程:

#include <iostream>
#include <cstring>

using namespace std;

struct Stack
{
    int x,y;
}s[100000];

char mp[150][150];
int chx[] = {1,0,-1,0,1,-1,1,-1};
int chy[] = {0,1,0,-1,1,-1,-1,1};
bool bj[150][150];

void dfs(int x,int y,int n,int m)
{
    int t = 0;
    Stack now,tmp;
    now.x = x;
    now.y = y;
    s[t++] = now;
    bj[x][y] = 1;
    while(t > 0)
    {
        now = s[t - 1];
        int flag = 0;
        for(int i = 0;i < 8;i++)
        {
            tmp.x = now.x + chx[i];
            tmp.y = now.y + chy[i];

            if(tmp.x >= 0 && tmp.y >= 0 && tmp.x < n && tmp.y < m)
            {
                if(bj[tmp.x][tmp.y] == 0)
                {
                    bj[tmp.x][tmp.y] = 1;
                    if(mp[tmp.x][tmp.y] == '@')
                    {
                        s[t++] = tmp;
                        flag = 1;
                        break;
                    }
                }
            }
        }

        if(flag)
            continue;
        t--;
    }
}

int main()
{
    int n,m;

    while(cin >> n >> m,n)
    {
        memset(bj,0,sizeof(bj));
        for(int i = 0;i < n;i++)
            cin >> mp[i];

        int ans = 0;
        for(int i = 0;i < n;i++)
        {
            for(int j = 0;j < m;j++)
            {
                if(bj[i][j] == 0 && mp[i][j] == '@')
                {
                    dfs(i,j,n,m);
                    ans++;
                }
            }
        }

        cout << ans << endl;
    }
    return 0;
}

我们手动创建了一个栈,如果找到‘@’就更新栈顶,然后跳出各个方向的向下遍历,因为如果不跳出,就成以这个点为起点向周围各个方向搜索的类似BFS的东西了。

更新栈顶之后便以栈顶为起点继续向下搜索,但是如果向下没有找到‘@’,也就是说没法继续更新栈顶,那只能做回退处理。但是这里有个问题,当然在这种类型的DFS中并不是问题,但是再第二个类型的DFS中需要特殊处理,那就是在递归中我们可以很好实现当回退之后,换个方向继续搜索,因为刚才的路径、方向都已经在递归栈中保存了,相当于挂起,但循环模拟却没有对之前的状态进行保存处理,举个例子:从A以第1个方向走到B(并作标记),在B没有找到下路,需要回退到A,然后A重新成为栈顶继续向下遍历,理论上应该是从第2个方向继续遍历,而循环实现依旧是从第1个方向开始,原因很好理解。至于怎么改善,讲第二种DFS的时候再做叙述。

第二种DFS,以搜索路径为目的,最短路也好,恰好到达也好,找的是一条路径问题,而最大的区别就是如果发生退栈,要进行清除标记,因为退栈后,可能存在别的路径依然会访问到这个结点。我们以ZOJ2110为例,我昨天这个题卡了一下午,递归实现很顺利就A掉了,但是非递归实现到现在还是TLE,十分费解(坏了,留下阴影了,再也不会爱了TAT)。

还是先看交题记录

因为第一次写这种类型的DFS,开始的那几个WA大家请忽视= =。

其中有个AC是我实在怀疑非递归了(一开始就是用非递归写的),然后用递归写了一下,一下就A掉了,简直醉了。

这个题目需要剪枝,其实就是深度优先搜索(DFS)的奇偶剪枝那篇文章的例题,如果想看递归实现和剪枝优化,请左转那篇之前写的文章,下面只说非递归实现。代码:

#include <iostream>
#include <algorithm>
#include <cstring>
#include <math.h>

using namespace std;

char map_[10][10];
bool bj[10][10];
int chx[] = {0,1,0,-1};
int chy[] = {1,0,-1,0};

struct Stack
{
    int x,y,t;
    int n;
} s[100000];
int main()
{
    int n,m,tim;

    while(cin >> n >> m >> tim,n)
    {
        for(int i = 0; i < n; i++)
        {
            cin >> map_[i];
        }

        int x = -1,y = -1;
        int fx = -1,fy = -1;
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < m; j++)
            {
                if(map_[i][j] == 'S')
                {
                    x = i;
                    y = j;
                }
                if(map_[i][j] == 'D')
                {
                    fx = i;
                    fy = j;
                }
            }
        }

        if(x == -1 || fx == -1)
        {
            cout << "NO" << endl;
            continue;
        }

        memset(bj,0,sizeof(bj));

        int t = 0;
        s[t].x = x;
        s[t].y = y;
        s[t].t = 0;
        s[t].n = 0;
        t++;
        bj[x][y] = 1;

        bool flag = 1;
        Stack tmp,now;
        while(t > 0)
        {
            now = s[t - 1];

            if(now.x == fx && now.y == fy)
            {
                if(now.t == tim)
                {
                    cout << "YES" << endl;
                    flag = 0;
                    break;
                }
            }

            int pdtmp = tim - now.t - fabs(fx - now.x) - fabs(fy - now.y);
            if(pdtmp < 0 || pdtmp % 2)
            {
                t--;
                if(t == 0)
                    break;
                s[t - 1].n++;
                bj[s[t].x][s[t].y] = 0;
                continue;
            }

            int tf = 0;
            for(int i = now.n; i < 4; i++)
            {
                tmp.x = now.x + chx[i];
                tmp.y = now.y + chy[i];
                tmp.t = now.t + 1;
                tmp.n = 0;
                now.n = i;

                if(tmp.x >= 0 && tmp.y >= 0 && tmp.x < n && tmp.y < m)
                {
                    if(map_[tmp.x][tmp.y] != 'X')
                    {
                        if(bj[tmp.x][tmp.y] == 0)
                        {
                            bj[tmp.x][tmp.y] = 1;

                            s[t++] = tmp;
                            tf = 1;
                            break;
                        }
                    }
                }

            }

            if(!tf)
            {
                t--;
                if(t == 0)
                    break;
                s[t - 1].n++;
                bj[s[t].x][s[t].y] = 0;
            }
            
        }

        if(flag)
            cout << "NO" <<endl;
    }
    return 0;
}

看栈结构体,除了常规的x,y,t之外,还有个n变量,他就是用来保存他的下一步遍历方向,然后在回退的时候注意不再走之前走过的路。因为回退的时候会清标记,所以如果能走之前走过的路,将会进入死循环。

也就是这个原因,在回退的时候不仅需要注意吐栈顶,还有注意更改之前元素的方向,已经清楚退出元素的标记,所以在继续遍历的时候一定要避开。

2015-02-12

最后,啸爷终于给我了他写的手写递归栈,居然过了。。。。研究一个下午也不明白他是怎么过的,算了以后就这么写吧。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <cmath>
#include <stack>
#include <map>

#pragma comment(linker, "/STACK:1024000000")
#define EPS (1e-8)
#define LL long long
#define ULL unsigned long long
#define _LL __int64
#define INF 0x3f3f3f3f
#define Mod 100007

using namespace std;

int jx[] = {-1, 0, 1, 0};
int jy[] = { 0,-1, 0, 1};

bool vis[10][10];

char Map[10][10];

struct N
{
    int x,y,c,dir;
}st[55*10*10],f,t;

bool Judge(int x,int y,int n,int m)
{
    return (1 <= x && x <= n && 1 <= y && y <= m && Map[x][y] != 'X');
}

int main()
{
    int i,j,n,m,k;

    while(scanf("%d %d %d",&n,&m,&k) && (n||m||k))
    {
        for(i = 1;i <= n; ++i)
            scanf("%s",Map[i]+1);

        int sx = -1,sy = -1,ex = -1,ey = -1;

        for(i = 1;i <= n; ++i)
        {
            for(j = 1;j <= m; ++j)
                if(Map[i][j] == 'S')
                    sx = i,sy = j;
                else if(Map[i][j] == 'D')
                    ex = i,ey = j;
        }

        if(sx == -1 || ex == -1 || (abs(ex-sx) + abs(ey-sy))%2 != k%2 )
        {
            puts("NO");
            continue;
        }

        memset(vis,false,sizeof(vis));

        vis[sx][sy] = true;
        st[0] = (N){sx,sy,0,-1};
        int Top = 0,site;

        while(Top > -1)
        {
            f = st[Top];
            site = Top;

            if(Map[f.x][f.y] == 'D' && f.c == k)
                break;

            if(f.dir == 3 || f.c > k)
            {
                Top--;
                vis[f.x][f.y] = false;
                continue;
            }

            st[site].dir = ++f.dir;

            t.x = jx[f.dir] + f.x;
            t.y = jy[f.dir] + f.y;
            t.c = f.c + 1;
            t.dir = -1;

            if(Judge(t.x,t.y,n,m) == false || vis[t.x][t.y])
                continue;

            vis[t.x][t.y] = true;

            st[++Top] = t;
        }

        if(Top > -1)
            puts("YES");
        else
            puts("NO");

    }


    return 0;
}
2015/2/11 posted in  算法&数据结构

汉密尔顿图

2015/2/6 posted in  算法&数据结构

佛罗莱(Fleury)算法

今天被这个叫Fleury算法的东西折磨了一下午,这个算法是解决欧拉回路问题的,其实已经被欧拉回路折磨两天了。

图论这本书本是打算一个寒假解决掉的,最初的时候认为会卡到第六章网络流部分,没想到在第五章可行性遍历就卡了。

首先是欧拉图,然后就是DFS解决欧拉图顺序问题,今天又卡到了佛罗莱算法,简直了。

佛罗莱算法是用来求欧拉回路的,判断欧拉回路十分简单,但是求欧拉回路一般是用DFS解决,但是DFS时间复杂度有些高,而佛罗莱算法能把时间复杂度压缩到O(e * e),e是边的数量。

原理:

任取v0∈V(G),令P0=v0;

设Pi=v0e1v1e2…ei vi已经行遍,按下面方法从中选取ei+1:

(a)ei+1与vi相关联;

(b)除非无别的边可供行遍,否则ei+1不应该为Gi=G-{e1,e2, …, ei}中的桥(所谓桥是一条删除后使连通图不再连通的边);

(c)当(b)不能再进行时,算法停止。

可以证明,当算法停止时所得的简单回路Wm=v0e1v1e2….emvm(vm=v0)为G中的一条欧拉回路。

当然,这个“可以证明”我还暂时证明不出来= =。

佛罗莱算法还是使用了DFS,其中这DFS的目的在于找出“桥”,当删掉一些边后整个图不连通,而最后删掉恰好不连通的那个边正是桥。

然后遇到桥之后栈回退不走桥(保证为走过的图还是连通)然后选择其他非桥的路进行继续入栈保存并继续DFS删边找桥。

有一点需要注意,就是栈里存储了什么,开始的时候我以为是路线,所以对这个算法一直想不明白,就在刚才我突然想到,我们找的是欧拉回路,也就是说起点就是终点,而对于桥的两个点都是两个回路,我们大可放心把桥的一段压在栈里不打印而继续都是把桥的另一端搜索完再打印,效果是一样的。

比如图:

如果以2开始,进行2 3 4 5 3 2 8 2的顺序进行遍历,在8到2的时候进入了死胡同,正是因为在8的时候进入桥(e9让2和其他结点断开)

如果在8的时候转向,开始9或7的继续遍历边解决这个问题,但是我的疑惑便是,因为刚开始的遍历到8为止,所有路线都存储在栈里,而退出的过程需要打印8,也就是说打印完8之后就不管之前入栈的结点而继续向下遍历,为什么还能保证正确。

因为8换方向遍历然后入栈的依然是(子图的)欧拉回路,也定将以8结束来上(刚才留下的)桥进行最后的遍历。而所谓的最后遍历也就是刚才已经留在栈中的结点。

因此栈是存储的路径但不是遍历路径而是存储了一个保证正确但不保证和遍历顺序相同的路径(在遇到桥的时候可能会导致最后退栈逆序)。

Fleury实现:

#include <iostream>
#include <math.h>
#include <algorithm>
#include <cstring>
#include <stack>

#define INF 100000

using namespace std;

int G[100][100];
int n;
stack<int> s;

void dfs(int x)
{
    s.push(x);

    for(int i = 1; i <= n; i++)
    {
        if(G[i][x] > 0)
        {
            G[x][i] = 0;
            G[i][x] = 0;
            dfs(i);
            break;
        }
    }
}

void fleury(int x)
{
    int b;
    s.push(x);

    while(!s.empty())
    {
        b = 0;
        for(int i = 1; i <= n; i++)
        {
            if(G[s.top()][i] > 0)
            {
                b = 1;
                break;
            }
        }
        if(b == 0)
        {
            cout << s.top() << " ";
            s.pop();
        }
        else
        {
            int t = s.top();
            s.pop();
            dfs(t);
        }
    }
}

int main()
{
    int m;
    while(cin >> n >> m,n)
    {
        while(!s.empty())
            s.pop();
        memset(G,0,sizeof(G));
        for(int i = 0; i < m; i++)
        {
            int a,b;

            cin >> a >> b;
            G[a][b] = 1;
            G[b][a] = 1;
        }
        int num = 0;
        int start = 2;
        for(int i = 1; i <= n; i++)
        {
            int d = 0;
            for(int j = 1; j <= n; j++)
                d += G[i][j];
            if(d % 2 == 1)
            {
                start = i;
                num++;
            }
        }

        if(num == 0 || num == 2)
            fleury(start);
        else
            cout << "No Euler path" << endl;
    }
    return 0;
}
2015/2/5 posted in  算法&数据结构

欧拉回路

概念

对于无向图

  1. 设G是连通无向图,则称经过G的每一条边并且仅一次的路径为欧拉通路
  2. 如果欧拉通路是回路(起点和终点是同一个顶点),则称此回路为欧拉回路
  3. 具有欧拉回路的无向图G称为欧拉图

对于有向图

  1. 设D是有向图,D的基图(有向图对应的无方向的无向图)相连通,则称经过D的每一条边并且仅一次的有向路径为有向欧拉通路
  2. 具有有向欧拉通路是有向回路,则称此有向回路为有向欧拉回路。
  3. 具有有向欧拉回路的有向图D称为有向欧拉图。

定理

定理1:无向图G存在欧拉通路的充要条件是:G为连通图,并且G仅有两个奇度节点(度数为奇数的顶点)或者无奇度结点。

推论1

  1. 当G是仅有两个奇度结点的连通图时,G的欧拉通路必以此两个顶点为端点、
  2. 当G是无奇度结点的连通图时,G必为欧拉回路。
  3. G为欧拉图(存在欧拉回路)的充分必要条件是G为无奇度结点的连通图、

定理2:有向图D存在欧拉通路的充要条件是:D为有向图,D的基图连通,并且所有顶点的出度和入度都相等;或则除两个顶点外,其余顶点的出度与入度都相等,而这两个顶点中的一个顶点的出度和入度只差为1,另一个顶点的出度与入度之差为-1。

推论2

  1. 当D除出入度只差为1,-1的两个顶点之外,其余顶点的出度入度都相等时,D的有向欧拉通路必以出入度之差为1的顶点作为始点,以出入度之差为-1的顶点作为终点。
  2. 当D的所有顶点的出入度都相等时,D中存在有向欧拉回路。
  3. 有向图D为有向欧拉图的充分必要条件是D的基图为连通图,并且所有顶点的出入度都相等。

 判断

判断欧拉通路

无向图:

  1. 判断是否连通
  2. 统计出度入度
  3. 统计奇度点(有则仅有2个或一个没有)

有向图:

  1. 判断基图连通
  2. 统计所有顶点的出度入度
  3. 所有顶点的出度入度相等或出两个顶点外其余顶点的出度或入度都相等,而这两个顶点中一个出度与入度只差为1,另一个人为-1

判断欧拉回路

无向图

  1. 先判断是不是欧拉通路
  2. 保证没有奇度点

有向图

  1. 先判断是否是欧拉通路
  2. 保证所有顶点的出、入度相等
2015/2/2 posted in  算法&数据结构

说说弗洛伊德算法

弗洛伊德算法,是当时集训的时候学最短路问题的第一个算法(去年寒假),当时学长直说这个算法好写、时间复杂度高,至于这个算法是什么原理却没有讲。学长说,照着敲就可以,循环敲对了,就那么神奇的对了,循环顺序错了,就神奇的WA了。

今年寒假,我也是学长了,逗比硕把最短路给我了,就变成这一周我要讲搜索和最短路。

搜索有BFS和DFS两个算法,或者说是思想,而最短路有4个算法。开始重点看搜索和最短路,翻来覆去好几遍。然后对搜索和走最短路的各个算法都有了进一步的理解,对这几种东西不再仅仅是限于会用模板了。

在与学弟的交流并解决学弟的疑问的同时,也让我看到的搜索和最短路那些只抄模板很容易忽略的地方。其实和学弟交流也能让自己发现并学到之前自己没有注意到的东西。

好了,主要说弗洛伊德的思想。之前最短路的总结就写过弗洛伊德。但没有解释弗洛伊德,这篇文章主要解释弗洛伊德原理。

摆出弗洛伊德的代码:

int fld (int n,int s,int e)
{
    int d[200][200];
    int i,j,k;
    memcpy(d,G,sizeof (G));

    for (k = 1;k <= n;k++)
        for (i = 1;i <= n;i++)
            for (j = 1;j <= n;j++)
                d[i][j] = qmin (d[i][j],d[i][k] + d[k][j]);

    return d[s][e];
}

首先,要明确,弗洛伊德是求任意两点之间的最短路。而他记录任意两点之间的距离是靠一个二维数组实现的。

然后说弗洛伊德是怎么实现的。

开始的时候,有个d数组(见上方代码),开始的时候是复制的G(一个邻接矩阵),我们可以认为,这个d开始的时候是两个点之间相连的距离。

换句话说,就是如果两个点有相连的边,就有距离,否则就是正无穷。

然后进入循环,从k = 1开始,也就是从1号点开始,对于任意两个点做一个尝试:能不能把1号点放入他们中间。

那么d数组就不是之前的d数组了,现在的d数组可以理解为任意两点之间中间点不超过1个的最短路。

为什么是不超过一个呢?因为刚才把1号点尝试放入任意两个点中间,有的发现如果放入就会更新最短路,换句话说,如果A到B的距离大于A到C然后到B的距离,那么,这个C点就可以放入最短路。与此相同,如果有的可以放入1号点,有的放入对最短路没有改善,那么d数组就是存储的任意两个点之间的最短路。

然后循环继续k = 2,那么,又开始在任意两个点之间尝试吧2号点放入最短路,依然是,有的可以,有的不可以。但是,因为刚才d数组已经不是开始的d数组了,开始的d数组是任意两个点直接相连的最短路,现在的是不超过1个点的最短路。而尝试把2号点放入则会让d数组变成任意两个点的中间点不超过2的最短路。

以此类推,知道把所有点循环完,就认为d数组是存储的任意两个点之间中间点不超过n个点的最短路,实际上,这时候的d已经是站在全局上考虑的d了,而且对于一个n个点的图来说,他的最短路的中间点一定小于n,那么我们就认为,这时候的任意两个点的最短路就是实际上要求的任意两个点的最短路。

算法的魅力不在于用这个算法A掉了一个或更多的题目,而是这个算法本身!

2015/2/1 posted in  算法&数据结构