BFS,即 Breath First Search(广度优先搜索)

DFS,即 Deep First Search (深度优先搜索)

图的搜索是对于连通图的一种遍历策略,常用于走迷宫的问题

本文的算法基于C语言编写,过几天会使用Java重写这两个算法

另外本文的算法是对基于数组的图进行搜索,基于链表的搜索暂时未弄 (逃

1.BFS

广度优先搜索顾名思义,就是在广范围进行搜索,从一个顶点V0开始,辐射状地优先遍历其周围较广的区域

算法的基本思路

在广搜中不需要记录节点是否走过,但是要记录上一个节点的位置,若将整个过程画成树,即可观察到广搜是一层一层进行遍历的(这里就不画图了,逃),这时若要搜索下一层节点就需要读取上一层节点的位置,并对父节点的所有节点逐个进行搜索,将符合要求的子节点逐个存入下一层节点,直到判断到达终点即停止搜索

基础算法采用递归,存储搜索各层节点采用队列,但由于C语言中没有队列所以采用结构体数组代替,使用二维结构体数组,其中一维对应层数,另一维存储该层的节点,另外若要使广搜拥有寻迹功能,即可以输出行进路程中每一步,就需要在结构体中增加一个结构体指针指向父节点,然后记录最后一个节点的地址,通过访问指针来访问父节点,直到到达起点

算法的实现

#include <stdio.h>
//广度优先搜索 - 可寻迹

//地图数组
int map[100][100];
//地图的个数
int n;
//定义起点和终点
int begin_x = 0, begin_y = 0, end_x = 4, end_y = 4;
//能到达终点的最后一个节点的指针
struct POINT *end_p = NULL;
//步进存储结构体
struct POINT
{
    int x; //X轴坐标
    int y; //Y轴坐标
    int is = 0; //是否是达到需求的节点,作为下一轮搜索的索引
    struct POINT *prev;
} po[100][100]; //po[轮数][不同节点存储,逐个存储]

int next[4][2] = {
    {0, 1},  //向右走
    {1, 0},  //向下走
    {0, -1}, //向左走
    {-1, 0}  //向上走
};

//首节点应传入-1
int BFS(int u)
{
    //重置定位个数用的索引
    int i = 0;
    //判断是否是起点,若是只需要将起点存入即可,同时将轮数索引加 1
    if (u == -1)
    {
        po[u + 1][0].x = begin_x;
        po[u + 1][0].y = begin_y;
        po[u + 1][0].is = 1;
        //再次调用进行下一轮搜索
        return BFS(u + 1);
    }
    //重置下一轮搜索的索引
    int j = 0;
    //判断父节点是否取尽
    while (po[u][i].is == 1)
    {
        //搜索部分
        int x = po[u][i].x;
        int y = po[u][i].y;
        //判断是否已经到达终点,若是则返回最短步数
        if (x == end_x && y == end_y)
        {
            end_p = &po[u][i];
            return u+1;
        }
        //将父节点设为不符合条件的节点,防止重复
        map[x][y] = 1;

        int k;
        //循环搜索各方向
        for (k = 0; k < 4; k++)
        {
            //定义临时x的坐标
            int tx = x + next[k][0];
            //定义临时y坐标
            int ty = y + next[k][1];
            //判断临时坐标是否到达边界,若是则尝试下一组
            if (tx < 0 || tx >= n || ty < 0 || ty >= n)
            {
                continue;
            }
            //判断该节点的数据是否符合要求,若符合就将该节点存入队列
            if (map[tx][ty] == 0)
            {
                //存入队列操作
                po[u + 1][j].x = tx;
                po[u + 1][j].y = ty;
                //将存在数据的队列节点标记,方便遍历队列,省去传递队列个数的操作
                po[u + 1][j].is = 1;
                //定位上一个节点
                po[u + 1][j].prev = &po[u][i];
                //将子节点的索引递增一,防止下一个子节点覆盖上一个子节点
                j++;
            }
        }
        //将父节点的索引递增一,进行下一轮子节点的搜索
        i++;
    }
    //当前父节点的所有子节点都已经搜索完毕,再次调用搜索函数,将当前所有子节点当成父节点,进行下一轮搜索
    return BFS(u + 1);
}

int main(int argc, char const *argv[])
{
    //输入图
    int i, j;
    printf("输入要输入图的长宽\n");
    scanf("%d", &n);
    printf("输入数据\n");
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < n; j++)
        {
            scanf("%d", &map[j][i]);
        }
    }
    // 定义存储输出轨迹的数组
    int foot[100][2];
    // 通过广度搜索返回最短步
    int k=BFS(-1);
    // 将每一步存入输出数组
    for(i=0;i<k;i++)
    {
        foot[i][0] = end_p->y;
        foot[i][1] = end_p->x;
        // 重新定位指针
        end_p = end_p->prev;
    }
    // 循环输出路径
    for(i=k-1;i>0;i--)
    {
        printf("(%d, %d)->",foot[i][0],foot[i][1]);
    }
    printf("(%d, %d)\n",foot[i][0],foot[i][1]);
    return 0;
}

本算法由于要进行寻迹操作,所以保留了每一层的数据,若不需要寻迹建议只保留两个队列,即两个一维结构体数组

2.DFS

深度优先搜索类似于广度优先搜索,也是一种图的搜索算法,但是不同于广度优先搜索,广搜注重范围,而深搜注重深度,通俗来说,广搜就是广撒网,深搜就是一路走到黑,不撞南墙不回头\( ̄︶ ̄\))

算法的基本思路

深搜需要定义一个跟原图相同的数组,然后通过该数组对数据进行标记,若已经走过就标记,回到父节点时将父节点的标记取消,基础算法依旧使用递归

算法的实现

#include <stdio.h>
#include <limits.h>
//深度优先搜索

//地图数组
int map[100][100];
//标记数组,用于标记是否已经搜索过
int book[100][100];
//地图的个数,最短的步数
int n, min = INT_MAX;
//定义起点和终点
int begin_x = 0, begin_y = 0, end_x = 4, end_y = 4;

int next[4][2] = {
    {0, 1},  //向右走
    {1, 0},  //向下走
    {0, -1}, //向左走
    {-1, 0}  //向上走
};

void DFS(int x, int y, int step)
{
    //判断是否已经到达终点,若是则比较目前的步数是否是最短的,若是则将当前步数赋给min,同时退出函数
    if (x == end_x && y == end_y)
    {
        min = min < step ? min : step;
        return;
    }
    int k;
    if(x==0&&y==0) book[0][0] = 1;
    //循环搜索各方向
    for (k = 0; k < 4; k++)
    {
        //定义临时x的坐标
        int tx = x + next[k][0];
        //定义临时y坐标
        int ty = y + next[k][1];
        //判断临时坐标是否到达边界,若是则尝试下一组
        if (tx < 0 || tx >= n || ty < 0 || ty >= n)
        {
            continue;
        }
        //判断该坐标的数据是否符合条件,若符合并且该数值之前没有被搜索到,就进行下一步搜索
        if (map[tx][ty] == 0 && book[tx][ty] != 1)
        {
            //将该坐标标记为已经搜索过
            book[tx][ty] = 1;
            //进行下一步搜索,即向深层次搜索
            DFS(tx, ty, step + 1);
            //取消坐标标记,因为该坐标的子节点已经在上方的递归中搜索完毕
            book[tx][ty] = 0;
        }
    }
    return;
}

int main(int argc, char const *argv[])
{
    int i, j;
    printf("输入要输入图的长宽\n");
    scanf("%d", &n);
    printf("输入数据\n");
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < n; j++)
        {
            scanf("%d", &map[j][i]);
        }
    }
    end_x = n-1;
    end_y = n-1;
    DFS(begin_x, begin_y, 0);
    //打印最短的步数
    printf("%d", min);
    return 0;
}

两种算法的比较

广搜由由于需要维护多条路径,同时存储多条路径,所以在正常情况下广搜使用的内存会比深搜多,编写也相对复杂,但是由于广搜一般是采用队列来存储路径所以没有爆栈的危险(C语言不适用),而深搜是使用栈进行存储的,由于系统分配给程序的栈是有限的,所以当深度过高时深受可能会出现爆栈。

一般来说用DFS解决的问题都可以用BFS来解决。DFS多用于连通性问题因为其运行思想与人脑的思维很相似,故解决连通性问题更自然。BFS多用于解决最短路问题,其运行过程中需要储存每一层的信息,所以其运行时需要储存的信息量较大,资源的消耗也较多。但是在不同问题中两者占优的情况是不同的,当图较为复杂二者其实差别不大。

说点什么
好耶,沙发还空着ヾ(≧▽≦*)o
Loading...