使用goto和数组模拟栈，双循环实现图的深度搜索

自从ACM比赛结束后，我很少再去社团训练了，很多东西都遗忘了，比如现在这个深度优先搜索。个人感觉深搜还是比广搜来的难得。大多数时候，深搜搜索的层数会很多，这时候如果使用递归和调用stl库的栈可能会出现栈溢出现象。于是我花了九个半小时研究了一下怎么避免栈溢出的情况，就有了这一篇专题。

进入今天正题：

深搜是基于栈的操作

无论是使用递归还是调用stl库的栈来实现深搜，都是使用到栈，这个大家应该都清楚。因此能不能找到一种方法，来模拟栈操作呢？

c/c++ 提供了一个goto 跳转，也就是你可以在程序段内跳转，重复执行某一块。使用goto和数组模拟栈，双循环实现图的深度搜索

变量说明

tmp 记录要进入邻接表第几行进行搜索

step[ i ] 标记 i 是否遍历过

cnt 记录搜索进入第几层

prev[ cnt ] 记录第cnt层前一个结点

vec[ i ][ j ] 图的邻接表

for(int i = 0 ; i < vec[root].size(); i ++){
        if(step[vec[root][i]] != 0) continue;
        step[vec[root][i]] = 1;
        prev[2] = root;
        tmp = vec[root][i];
        printf("1.in [%d] at [%d] find value =%d\n",root,i,vec[root][i]);
        l1: for(int j = 0 ; j < vec[tmp].size(); j ++){
            if(step[vec[tmp][j]] == 0) {
                printf("2.in [%d] at[%d] find value =%d \n", tmp, j, vec[tmp][j]);
                prev[++cnt] = tmp;
                step[vec[tmp][j]] = 1;
                tmp = vec[tmp][j];
                goto l1;
            }
        }
        if(cnt==0)
            break;
        tmp = prev[cnt];
        cnt--;
        goto l1;
    }

这一段是最关键的，第一层循环是遍历根结点的所有子节点，第二重循环是实现跳转

在第一重循环取得要遍历的子节点，由第二重循环搜索孙结点，只要找到一个入口，更改tmp，goto 跳转进入下一层，这样不会让第二重循环循环执行结束。当当前tmp找不到入口时，第二重循环结束，tmp回到上一层，cnt--，goto 跳转，当前tmp寻找下一层入口……如果一直找不到下一层的入口,cnt就会一直减下去，当cnt==0时，说明遍历完所有情况，直接break，或者return 都可以。

下面是图的深搜和广搜的具体代码。

input : n n个互联方式

下面的n行内需要输入a b

a b 结点a与结点b互联

example:

1 2

2 3

2 4

1 5

5 6

#include<bits/stdc++.h>
using namespace std;
#define  MAX  1024
vector<int>vec[MAX];int step[MAX];
void dfs(int root){
    int tmp;
    int prev[MAX],cnt = 2;
    prev[1] = 0;
    step[root] = 1;
    for(int i = 0 ; i < vec[root].size(); i ++){
        if(step[vec[root][i]] != 0) continue;
        step[vec[root][i]] = 1;
        prev[2] = root;
        tmp = vec[root][i];
        printf("1.in [%d] at [%d] find value =%d\n",root,i,vec[root][i]);
        l1: for(int j = 0 ; j < vec[tmp].size(); j ++){
            if(step[vec[tmp][j]] == 0) {
                printf("2.in [%d] at[%d] find value =%d \n", tmp, j, vec[tmp][j]);
                prev[++cnt] = tmp;
                step[vec[tmp][j]] = 1;
                tmp = vec[tmp][j];
                goto l1;
            }
        }
        if(cnt==0)
            break;
        cnt;
        tmp = prev[cnt];
        cnt--;
        goto l1;
    }
}
void bfs(){
    queue<int>que;
    step[1] = 1;
    printf("1 ");
    for(int i = 0 ; i < vec[1].size() ; i ++){
        que.push(vec[1][i]);
        step[vec[1][i]] = 1;
    }
    while(que.size()){
        int front = que.front();
        printf("%d ",front);
        for(int i = 0 ; i < vec[front].size() ; i ++){
            if(step[vec[front][i]] == 0){
                que.push(vec[front][i]);
                step[vec[front][i]] = 1;
            }
        }
        que.pop();
    }

}
int main(){
    int n,a,b,c;
    memset(vec,0,sizeof(vec));
    memset(step,0,sizeof(step));
    scanf("%d",&n);
    for(int i = 0 ; i < n ; i ++){
        scanf("%d %d",&a,&b);
        vec[a].push_back(b);
        vec[b].push_back(a);
    }
    //dfs(1);
    bfs();
}

使用goto和数组模拟栈，双循环实现图的深度搜索

深搜是基于栈的操作

相关推荐