您现在的位置是：网站首页>技术百科技术百科

搜索算法之深度优先搜索（DFS, Depth-First Search）

小大寒2024-01-01[技术百科]博学多闻

搜索算法之深度优先搜索（DFS, Depth-First Search）深度优先搜索（DFS, Depth-First Search）是一种图或树的遍历算法，通过沿某一路径不断深入，直到无法继续为止，再回溯并寻找下一条路径。其实现通常采用递归或栈结构，广泛应用于路径搜索、连通性检测等场景。

搜索算法之深度优先搜索（DFS, Depth-First Search）

1. 基础概念

1.1 定义

深度优先搜索是一种系统性搜索算法。其核心思想是：

从起始节点出发，优先选择未访问的子节点深入搜索。
如果当前路径已无法继续，则回退到上一个节点，继续尝试其他未访问路径。

DFS可用于遍历图或树，适用于寻找所有解或某些最优解。

1.2 特点

搜索路径以“深”为优先，直至搜索到叶子节点或满足终止条件。
实现简单，可通过递归或显式使用栈完成。
时间复杂度通常与节点和边数有关，但可能消耗大量内存用于存储路径。

1.3 使用场景

解决迷宫问题、路径搜索。
拓扑排序。
连通性检测（如求图的连通分量）。
求解排列组合问题（如8皇后问题）。

2. 实现与操作

2.1 核心操作实现

以下示例以C语言实现DFS遍历图：

    #include <stdio.h>
    #include <stdlib.h>
    #include <stdbool.h>
    
    #define MAX_NODES 100
    
    // 图的结构体
    typedef struct {
        int adjMatrix[MAX_NODES][MAX_NODES]; // 邻接矩阵
        int numNodes;                       // 节点数
    } Graph;
    
    // 标记访问状态的数组
    bool visited[MAX_NODES];
    
    // 初始化图
    void initGraph(Graph* graph, int numNodes) {
        graph->numNodes = numNodes;
        for (int i = 0; i < numNodes; i++) {
            for (int j = 0; j < numNodes; j++) {
                graph->adjMatrix[i][j] = 0;
            }
        }
    }
    
    // 添加边
    void addEdge(Graph* graph, int u, int v) {
        graph->adjMatrix[u][v] = 1;
        graph->adjMatrix[v][u] = 1; // 无向图
    }
    
    // 深度优先搜索
    void dfs(Graph* graph, int node) {
        printf("访问节点: %d\n", node);
        visited[node] = true;
    
        // 遍历所有相邻节点
        for (int i = 0; i < graph->numNodes; i++) {
            if (graph->adjMatrix[node][i] == 1 && !visited[i]) {
                dfs(graph, i);
            }
        }
    }
    
    // 主函数
    int main() {
        Graph graph;
        initGraph(&graph, 6);
    
        addEdge(&graph, 0, 1);
        addEdge(&graph, 0, 2);
        addEdge(&graph, 1, 3);
        addEdge(&graph, 2, 4);
        addEdge(&graph, 3, 5);
    
        printf("深度优先搜索结果:\n");
        for (int i = 0; i < graph.numNodes; i++) {
            visited[i] = false; // 初始化为未访问
        }
    
        dfs(&graph, 0); // 从节点0开始搜索
        return 0;
    }
        </stdbool.h></stdlib.h></stdio.h>

2.2 代码详解

initGraph 初始化图的邻接矩阵。
addEdge 添加边，形成无向图。
dfs 使用递归实现深度优先搜索，并打印访问路径。
main 演示DFS的完整流程。

3. 时间与空间复杂度分析

3.1 时间复杂度

时间复杂度：O(V + E)，其中V为节点数，E为边数。每个节点和边仅访问一次。

3.2 空间复杂度

空间复杂度：O(V)，主要用于存储递归调用栈和访问状态数组。

4. 优缺点与局限性

4.1 优点

实现简单，适合搜索所有解。
内存占用较低（与广度优先搜索相比）。

4.2 缺点与局限性

可能陷入死循环（未标记访问状态时）。
对目标节点分布不均的图，搜索效率较低。

5. 常见应用场景

5.1 实际应用：求解迷宫问题

以下是一个迷宫DFS求解的代码：

    #include <stdio.h>
    #include <stdbool.h>
    
    #define N 4
    
    bool isSafe(int maze[N][N], int x, int y) {
        return x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 1;
    }
    
    bool solveMazeUtil(int maze[N][N], int x, int y, int sol[N][N]) {
        if (x == N - 1 && y == N - 1 && maze[x][y] == 1) {
            sol[x][y] = 1;
            return true;
        }
        if (isSafe(maze, x, y)) {
            sol[x][y] = 1;
            if (solveMazeUtil(maze, x + 1, y, sol)) return true;
            if (solveMazeUtil(maze, x, y + 1, sol)) return true;
            sol[x][y] = 0;
        }
        return false;
    }
    
    void solveMaze(int maze[N][N]) {
        int sol[N][N] = { {0} };
        if (!solveMazeUtil(maze, 0, 0, sol)) {
            printf("没有解决方案\n");
        } else {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    printf("%d ", sol[i][j]);
                }
                printf("\n");
            }
        }
    }
    
    int main() {
        int maze[N][N] = {
            {1, 0, 0, 0},
            {1, 1, 0, 1},
            {0, 1, 0, 0},
            {1, 1, 1, 1}
        };
        solveMaze(maze);
        return 0;
    }
        </stdbool.h></stdio.h>