DFS and BFS

DFS

以迷宫搜索为例说明DFS。

dfs.png

如图8-1，从起点开始前进，当碰到岔道口时，总是选择其中一条岔道前进（例如图中总是优先选择最右手边的岔道），在岔道上如果又遇到新的岔道口，任然选择新岔道口的其中一条岔道口前进，直到碰到死胡同才回退到最近的岔道口选择另一条岔路。也就是说，当碰到岔道口时，总是以“深度”作为前进的关键词，不碰到死胡同就不回头，因此把这种搜索的方式称为深度优先搜索。

从迷宫的例子还可以注意到，深度优先搜索会走遍所有路径，并且每次走到死胡同就代表一条完整路径的形成。就是说，深度优先搜索是一种枚举所有完整路径以遍历所有情况的搜索方法。

DFS可以使用栈来实现，因此使用递归可以很好地实现DFS。使用递归时，系统会调用一个叫系统栈的东西来存放递归中的每一层的状态，故使用递归实现DFS本质其实还是栈。

有n件物品，每件物品的重量为w[i]，价值为c[i]。现在需要选出若干件物品放入一个容量为V的背包中，使得在选入背包的物品不超过物品重量和不超过容量V的前提下，让背包中物品的价值之和最大，求最大值。

DFS.cpp

#include<cstdio>

const int maxn = 30;
int n, V, maxValue = 0;
int w[maxn], c[maxn];

void DFS(int index, int sumW, int sumC) {
    if(index==n) {
       return;
    }
    DFS(index+1, sumW, sumC); // 不选择第index件商品
    if(sumW + w[index] <= V) { // 不超重下选择第index件商品
        if(sumC + c[index] > maxValue) {
            maxValue = sumC + c[index];
        }
        DFS(index+1, sumW+w[index], sumC+c[index]);
    }  
}

int main() {
    scanf("%d%d", &n, &V);
    for(int i=0; i<n; i++) {
        scanf("%d", &w[i]);
    }
    for(int i=0; i<n; i++) {
        scanf("%d", &c[i]);
    }
    DFS(0, 0, 0);
    printf("\n%d\n", maxValue);
    return 0;
}

BFS

同样以迷宫搜索为例，广度优先搜索以广度作为第一关键词，当碰到岔路口时，总是先依次访问从该岔道口能够直接到达的所有结点，然后再按这些结点被访问的顺序去依次访问它们能直接到达的所有结点，以此类推，直到所有结点都被访问为止。

BFS一般由队列实现，且总是按层次的顺序进行遍历，其基本写法如下:

void BFS(int s) {
    queue<int> q;
    q.push(s);
    while(!q.empty()) {
        取出队首元素top;
        访问队首元素top;
        将队首元素出队;
        将top的下一层结点中未曾入队的结点全部入队，并设置为已入队;
    }
}

给定一个n*m大小的迷宫，其中“*”代表不可通过的墙壁，而“.”代表平地，S表示起点，T表示终点，如果当前位置是（x，y）（下标从0开始），且每次只能前往上下左右（x，y+1）、（x，y-1）、（x-1，y）、（x+1，y）四个位置的平地，求从起点S达到终点T的最少步数。

.....
.*.*.
.*S*.
.***.
...T*

上面的样例中，S的坐标为（2,2），T的坐标为（4,3）

本题中，由于求的是最小步数，而BFS是通过层次的顺序来遍历的，因此可以从起点S开始计数遍历层次，那么在到达终点T时的层数就是需要求解的起点S达到终点T的最少步数。

BFS.cpp

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;

struct node {
    int x, y;   // 位置（x，y）
    int step;   // step为起点到终点的最少步数
}S, T, Node;   // Node为临时结点
int X[]={1, -1, 0, 0};   // 增量数组
int Y[]={0, 0, 1, -1};
const int maxn=10;
int maxtri[maxn][maxn];   // 迷宫信息
int inq[maxn][maxn]={false};   // 记录位置（x，y）是否已入过队
int m,n; // m行n列

// 检测位置（x，y）是否有效
bool check(int x, int y) {
    if(maxtri[x][y]=='*') return false;   // 墙壁
    if(x<0 || x>=m || y<0 || y>=n) return false;   // 越界
    if(inq[x][y]==true) return false;   // 已入过队
    return true;
}

int BFS() {
    queue<node> q;
    q.push(S);
    while(!q.empty()) {
        node top = q.front();
        q.pop();
        if(top.x==T.x && top.y==T.y) {
            return top.step;
        }
        for(int i=0; i<4; i++) {
            int newX = top.x + X[i];
            int newY = top.y + Y[i];
            if(check(newX, newY)) {
                Node.x = newX;
                Node.y = newY;
                Node.step = top.step + 1;
                inq[newX][newY] = true;
                q.push(Node);
            }
        }
    }
    return -1;   // 无法达到终点T时返回-1
}

int main() {
    scanf("%d%d", &m, &n);
    for(int i=0; i<m; i++) {
        getchar();
        for(int j=0; j<n; j++) {
            maxtri[i][j]=getchar();
        }
        maxtri[i][n+1]='\0';
    }
    scanf("%d%d%d%d", &S.x, &S.y, &T.x, &T.y);
    for(int i=0; i<m; i++) {
        for(int j=0; j<n; j++) {
            printf("%c ", maxtri[i][j]);
        }
        printf(" \n");
    }
    S.step = 0;   // 初始化起点的层数为0，即S到S的最少步数为0
    int sp = BFS();
    printf("%d\n", sp);
    return 0;
}