深度优先搜索

DFS

1.算法介绍

深度优先搜索（DFS）算法是一种用于遍历或搜索树或图的算法。它的基本思想是尽可能深地搜索图的分支，直到到达叶节点或无法再深入为止，然后回溯到前一个节点，继续探索其他分支。这种搜索策略可以确保图中的每个节点都被访问到，除非它是一个环。
深度优先搜索的实现通常使用递归或栈来实现。对于树或图的遍历，可以从根节点或任意节点开始，然后沿着某个分支深入搜索，直到达到叶节点或无法再深入为止。在这个过程中，需要记录已经访问过的节点，以避免重复访问。当一条路径搜索完成后，需要回溯到上一个节点，继续搜索其他分支。

2.算法原理

深度优先搜索（DFS）算法的原理主要基于图的遍历。给定一个图（可以是有向图或无向图），DFS从某个起始节点出发，尽可能深地搜索图的分支，直到达到叶节点或无法再深入为止。然后，它回溯到上一个节点，继续搜索其他未遍历的分支。这个过程反复进行，直到图中所有可达的节点都被访问过。
DFS使用栈（stack）这种数据结构来辅助实现。在搜索过程中，将当前访问的节点以及从起始节点到该节点的路径上的所有节点都放入栈中。当搜索到叶节点或无法再深入时，从栈中弹出当前节点，并回溯到上一个节点，继续搜索。
DFS的核心思想包括两个方面：
1.回溯（backtracking）：当搜索到叶节点或无法再深入时，需要回溯到上一个节点，继续搜索其他未遍历的分支。这种走不通就退回再走的技术称为回溯法。满足回溯条件的某个状态的点称为“回溯点”。
2.剪枝（pruning）：在搜索过程中，通过某些条件判断，提前终止对当前分支的搜索，以减少不必要的搜索。这种减小搜索树规模、尽早排除搜索树中不必要的分支的手段称为剪枝。
DFS的时间复杂度在最坏情况下为O(n!)，其中n为图中节点的数量。这是因为对于每个节点，都可能有n种选择（即选择下一个要访问的节点），从而导致搜索树的规模达到n的阶乘。然而，在实际应用中，DFS通常能在较小的搜索空间内找到解，因此其平均时间复杂度往往低于最坏情况。

3.算法实现

下面是一个使用C语言实现的深度优先搜索（DFS）算法示例。在这个示例中，我们使用邻接矩阵来表示图，并使用递归来实现DFS。

#include <stdio.h>
#include <stdbool.h>

#define MAX_VERTICES 100

// 函数原型声明
void dfs(int graph[MAX_VERTICES][MAX_VERTICES], bool visited[], int v);

int main() {
    // 示例图的邻接矩阵表示
    // 1 表示存在边，0 表示不存在边
    int graph[MAX_VERTICES][MAX_VERTICES] = {
        {0, 1, 1, 0, 0, 0, 0, 0, 0, 0},
        {1, 0, 0, 1, 1, 0, 0, 0, 0, 0},
        {1, 0, 0, 0, 0, 1, 0, 0, 0, 0},
        {0, 1, 0, 0, 0, 1,