dfs深度优先搜索

发布时间:2024年01月23日

可以使用DFS的抽象场景:

1. 树和图的遍历。
2. 解决迷宫、棋盘等问题,比如寻找最短路径、是否存在路径等。
3. 解决连通性问题,比如求连通块的个数、检测一个无向图是否为一棵树等。
4. 深度限制搜索,比如生成所有长度为m的字符串、组合等。
5. 用于寻找隐式图或状态空间搜索,比如经典的八数码等。

使用DFS时需要注意的事项:

1. 防止重复访问。在搜索过程中,需要使用visited数组等方式来确保每个节点被访问一次,避免重复访问。
2. 防止死循环。需要避免重复访问同一个节点,否则可能会出现死循环的情况。
3. 选择好邻居节点。在DFS搜索过程中,需要选择好的邻居节点来递归进行搜索,以提高搜索效率。
4. 理清搜索过程。需要将搜索过程中的状态变化、递归调用等步骤清楚地理解清楚,以便正确地实现算法。

DFS算法步骤:

1. 判断当前节点是否符合条件,如是否已经访问过、是否在矩阵范围内、是否匹配需要找的单词、是否为目标节点等。
2. 如果当前节点符合条件,进行相应的状态变化,然后递归搜索邻居节点。
3. 在递归搜索邻居节点时,需要注意防止死循环和重复访问的情况。
4. 如果找到了目标节点或者匹配成功,返回相应的结果。
5. 如果搜索结束仍然没有找到目标节点或者匹配失败,返回相应的结果。

// DFS算法,全称为深度优先搜索,也称为深搜。
// 它是一种通过搜索所有可能的分支来实现的图形遍历算法,基于树或图的数据结构。
// 在DFS搜索过程中,访问到每个节点后,首先将该节点标记为已访问过,然后递归访问该节点的所有未访问过的邻居。

// dfs算法模型--走迷宫
// 在一个矩阵形式的迷宫中,DFS算法可以用来寻找从起始点到终点的路径。
// 在搜索过程中,每次只从当前节点的未访问过的邻居中选择一条路径继续进行搜索,
// 如果到达了终点则返回成功,否则将回溯到上一个节点进行新的搜索。

#include <stdio.h>

#define ROWS 5
#define COLS 5

int maze[ROWS][COLS] = {
    {0, 0, 0, 0, 0},
    {0, 1, 1, 0, 0},
    {0, 1, 0, 0, 0},
    {0, 0, 1, 1, 0},
    {0, 0, 0, 0, 0}
};

// 使用了一个visited数组来记录每个节点的访问状态,
// 如果一个节点已经被访问过,则将visited数组中相应位置的值置为1,避免出现重复访问的情况。
int visited[ROWS][COLS] = {0};

int dfs(int x, int y)
{
    // 如果在访问一个节点时,发现该节点不符合求解条件(比如在外部边缘,迷宫中存在障碍物,节点已经访问过),则直接返回 0。
    if (x < 0 || y < 0 || x >= ROWS || y >= COLS || maze[x][y] == 1 || visited[x][y] == 1) {
        return 0;
    }
    // 标记节点已经访问过
    visited[x][y] = 1;
    // 标记处查找路径中的访问节点
    printf("%d %d\n", x, y);

    // 如果到达目的节点,则返回1,退出递归搜索
    if (x == 4 && y == 4) {
        return 1;
    }
    // 否则尝试向上下左右4个方向遍历下一个位置
    if (dfs(x+1, y) || dfs(x, y+1) || dfs(x-1, y) || dfs(x, y-1)) {
        return 1;
    }
    visited[x][y] = 0;
    return 0;
}

int main()
{
    dfs(1, 0);
    return 0;
}

// dfs 2. 棋盘游戏
// 在一些棋盘游戏中,DFS算法可以用来查找获得胜利需要的最短步数。
// 在搜索过程中,每次只从当前节点的未访问过的邻居中选择一条路径,
// 然后递归访问下一个节点,直到到达目标位置,然后逆行回溯,更新步数。
// 请使用c语言递归算法实现以上需求,并对编写的实例代码进行详细讲解

// 以下是基于递归实现的C语言代码实例:
// 在这个代码实例中,我们使用递归来实现DFS算法,找出从棋盘左上角到右下角的最短路径。
// 在DFS的实现中,我们使用visited数组来标记已经访问过的节点,避免出现重复访问的情况。
// steps数组用来记录到达每个节点的最短步数。
// 在遍历每个节点的邻居时,只需要递归调用dfs函数,并将步数加1即可。
// 最外层的main函数调用dfs函数来开始在整个棋盘上进行DFS搜索。只要到达终点(右下角),则直接返回。
// 在回溯时,将visited数组中相应位置的值置为0,以便下一次访问。
// 最后,输出steps[ROWS-1][COLS-1],即终点的最短步数。本例算法的时间复杂度是O(n^2),其中n指的是棋盘的边长。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define ROWS 5
#define COLS 5

int board[ROWS][COLS] = {
    {0, 0, 0, 0, 0},
    {0, 1, 0, 1, 0},
    {0, 1, 0, 0, 0},
    {0, 1, 1, 1, 0},
    {0, 0, 0, 0, 0}
};

int visited[ROWS][COLS] = {0};
int steps[ROWS][COLS] = {0};

void dfs(int i, int j, int step)
{
    if (i < 0 || j < 0 || i >= ROWS || j >= COLS || board[i][j] == 1 || visited[i][j] == 1) {
        return;
    }
    visited[i][j] = 1;
    steps[i][j] = step;
    if (i == ROWS - 1 && j == COLS - 1) {
        return;
    }
    dfs(i+1, j, step+1);
    dfs(i, j+1, step+1);
    dfs(i-1, j, step+1);
    dfs(i, j-1, step+1);
    visited[i][j] = 0;  // 回溯,释放当前节点
}

int main()
{
    dfs(0, 0, 0);
    printf("%d\n", steps[ROWS-1][COLS-1]);
    return 0;
}


// dfs 词语搜索
// 在一个由大量单词组成的矩阵中,DFS算法可以用来查找指定的单词。
// 在搜索过程中,每次只从当前位置的未访问过的邻居中选择一个字符,
// 继续递归访问下一个位置,直到所有的字符都被匹配到,或者匹配失败后回溯。
// 请使用c语言dfs算法模型编写实例代码实现以上需求,并对代码进行详细讲解

// 以下是基于DFS算法的C语言代码实例:
// 在这个代码实例中,我们使用DFS算法来在一个字符矩阵中查找指定的单词是否存在。
// 在DFS的实现中,我们使用visited数组来记录每个节点的访问状态,
// 如果一个节点已经被访问过,则将visited数组中相应位置的值置为1,避免出现重复访问的情况。
// 如果在访问一个节点时,发现该节点不符合匹配条件
//(比如和需要匹配的字符不相等、已经访问过、不在矩阵范围内等),则直接返回0。
// 如果匹配到了最后一个字符,则返回1,表示匹配成功。
// 否则,对当前位置的四个邻居递归调用dfs函数,尝试匹配下一个字符。
// 在遍历完一个节点的所有未访问的邻居之后,将visited数组中相应位置的值置为0,逆行回溯。
// 最外层的exist函数用来遍历整个矩阵,针对每一个位置都尝试匹配指定的单词,只要有一个匹配成功,立即返回1。
// 如果遍历完整个矩阵,仍然没有找到匹配的单词,返回0。


#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define ROWS 4
#define COLS 4

char board[ROWS][COLS] = {
    {'A', 'B', 'C', 'E'},
    {'S', 'F', 'C', 'S'},
    {'A', 'D', 'E', 'E'},
    {'F', 'A', 'T', 'P'}
};

int visited[ROWS][COLS] = {0};

int dfs(char* word, int index, int i, int j)
{
    if (i < 0 || j < 0 || i >= ROWS || j >= COLS || board[i][j] != word[index] || visited[i][j] == 1) {
        return 0;
    }
    visited[i][j] = 1;
    if (index == strlen(word) - 1) {
        return 1;
    }
    int step1 = dfs(word, index+1, i+1, j);
    int step2 = dfs(word, index+1, i, j+1);
    int step3 = dfs(word, index+1, i-1, j);
    int step4 = dfs(word, index+1, i, j-1);
    visited[i][j] = 0;
    return step1 || step2 || step3 || step4;
}

int exist(char* word)
{
    for (int i = 0; i < ROWS; i++) {
        for (int j = 0; j < COLS; j++) {
            if (dfs(word, 0, i, j)) {
                return 1;
            }
        }
    }
    return 0;
}

int main()
{
    char* word1 = "ABCCED";
    char* word2 = "SEE";
    char* word3 = "ABCB";
    printf("%d\n", exist(word1));  // 1
    printf("%d\n", exist(word2));  // 1
    printf("%d\n", exist(word3));  // 0
    return 0;
}


文章来源:https://blog.csdn.net/tankeven/article/details/135761215
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。