如何用C语言实现深度搜索算法视频教学？-C语言-盈思创科技

核心思想与原理（先理解，再编码）

在开始看代码或视频之前,务必先理解DFS的核心思想。

（图片来源网络，侵删）

DFS（Depth-First Search）：一种用于遍历或搜索树或图的算法，它的思想是“一条路走到黑，走不通再回头”。

核心步骤：

访问：访问当前节点。
标记：将当前节点标记为“已访问”，防止重复访问（在图中尤其重要）。
探索：递归地访问当前节点的第一个未被访问的邻接节点。
回溯：当当前节点的所有邻接节点都已被访问后，函数调用栈会自动“回溯”到上一个节点，继续执行它的逻辑。

一个绝佳的比喻：迷宫探险 想象你被困在一个迷宫里，DFS的策略是：

你站在入口处（起始节点）。
你选择一条路（比如左边）一直走下去。
每到一个岔路口,你总是选择最左边那条你没走过的路。
如果走进死胡同（没有未访问的邻接节点了），你就原路返回（回溯）到上一个岔路口。
然后从那个岔路口选择下一条你没走过的路（比如第二条路）。
重复这个过程,直到你走出迷宫（找到目标节点）或探索完所有路径。

C语言视频教程推荐

视频教程能非常直观地展示算法的执行过程,强烈推荐观看。

（图片来源网络，侵删）

B站（Bilibili） - 国内首选

B站是学习编程的宝库,有很多优秀的UP主提供免费且高质量的教学。

推荐UP主/关键词搜索：
- “王道考研”：他们的数据结构系列课程非常经典，讲解清晰，对考研学生和自学者都很有帮助，搜索“王道 DFS”或“王道数据结构”。
- “青岛大学-王卓”：王卓老师的数据结构课程在国内也很有名气，讲解细致，动画演示丰富，搜索“王卓数据结构”。
- “浙江大学-陈越、何钦铭”：他们的“数据结构”课程是国家精品课，质量极高，可以在中国大学MOOC（慕课）平台找到，B站也有搬运，搜索“浙大数据结构”。
- 直接搜索：C语言深度优先搜索、DFS 算法 C语言实现、数据结构树的遍历 DFS。
通常会包含：
- 动画演示DFS在树和图上的遍历过程。
- 递归和栈两种实现方式的讲解。
- 代码的逐行分析和调试过程。
- 典型例题的讲解。

YouTube

如果你能流畅地使用英文,YouTube是全球最大的视频平台，资源极其丰富。

推荐频道/关键词搜索：
- "CS50" (哈佛大学计算机科学导论)：他们的数据结构和算法部分讲得非常棒，深入浅出。
- "Abdul Bari"：这位老师讲解算法非常清晰，有大量的动画和实例。
- "Jenny's Lectures CS IT"：她的数据结构系列也很受欢迎，讲解耐心。
- 搜索关键词：DFS algorithm in C、Depth First Search C programming、tree traversal DFS C。

C语言代码实现与解析

下面我将为您提供DFS在二叉树和图两种数据结构上的C语言实现。

DFS在二叉树上的实现

二叉树的DFS通常指前序遍历、中序遍历和后序遍历，它们的区别在于访问根节点的时机，这里以最常见的前序遍历为例。

#include <stdio.h>
#include <stdlib.h>
// 定义二叉树节点结构
typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;
// 创建新节点
TreeNode* createNode(int value) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    if (newNode == NULL) {
        printf("内存分配失败!\n");
        exit(1);
    }
    newNode->val = value;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}
// DFS - 前序遍历 (根 -> 左 -> 右)
void preorderDFS(TreeNode* root) {
    // 基本情况：如果节点为空，则返回
    if (root == NULL) {
        return;
    }
    // 1. 访问当前节点 (根)
    printf("%d ", root->val);
    // 2. 递归访问左子树
    preorderDFS(root->left);
    // 3. 递归访问右子树
    preorderDFS(root->right);
}
int main() {
    // 构建一个简单的二叉树
    //       1
    //      / \
    //     2   3
    //    / \
    //   4   5
    TreeNode* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    printf("前序遍历结果: ");
    preorderDFS(root); // 输出应为: 1 2 4 5 3
    printf("\n");
    // 释放内存 (在实际项目中需要更完整的释放逻辑)
    free(root->left->right);
    free(root->left->left);
    free(root->right);
    free(root->left);
    free(root);
    return 0;
}

代码解析：

TreeNode 结构体定义了二叉树的节点，包含值、左子节点和右子节点。
preorderDFS 函数是核心，它是一个递归函数。
基本情况：if (root == NULL)，这是递归的出口，当遇到一个不存在的节点（即空指针）时，函数停止向下执行，返回到上一个调用点。
递归步骤：
1. printf("%d ", root->val); 访问当前节点。
2. preorderDFS(root->left); 递归调用自身，处理左子树，这个调用会一直向左下钻，直到遇到空节点。
3. preorderDFS(root->right); 左子树处理完毕后，再递归处理右子树。

DFS在图上的实现

图比树复杂,因为图中可能存在环，导致无限递归，必须使用一个访问数组 visited[] 来记录哪些节点已经被访问过。

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h> // 使用 bool 类型
#define MAX_VERTICES 10 // 图的最大顶点数
// 邻接表表示的图
typedef struct Graph {
    int numVertices;
    bool** adjMatrix; // 邻接矩阵
    // 如果用邻接表，可以定义一个结构体数组 struct Node* adjLists[MAX_VERTICES];
} Graph;
// 创建图
Graph* createGraph(int vertices) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->numVertices = vertices;
    // 分配邻接矩阵内存
    graph->adjMatrix = (bool**)malloc(vertices * sizeof(bool*));
    for (int i = 0; i < vertices; i++) {
        graph->adjMatrix[i] = (bool*)malloc(vertices * sizeof(bool));
        for (int j = 0; j < vertices; j++) {
            graph->adjMatrix[i][j] = false; // 初始化所有边为false
        }
    }
    return graph;
}
// 添加边 (无向图)
void addEdge(Graph* graph, int src, int dest) {
    graph->adjMatrix[src][dest] = true;
    graph->adjMatrix[dest][src] = true; // 无向图，对称
}
// DFS核心函数 (递归实现)
void DFSUtil(Graph* graph, int vertex, bool* visited) {
    // 1. 访问当前节点
    printf("%d ", vertex);
    // 2. 标记为已访问
    visited[vertex] = true;
    // 3. 递归访问所有邻接节点
    for (int i = 0; i < graph->numVertices; i++) {
        // 如果存在边，并且邻接节点未被访问
        if (graph->adjMatrix[vertex][i] && !visited[i]) {
            DFSUtil(graph, i, visited);
        }
    }
}
// 对外暴露的DFS接口
void DFS(Graph* graph, int startVertex) {
    // 创建并初始化访问数组
    bool* visited = (bool*)malloc(graph->numVertices * sizeof(bool));
    for (int i = 0; i < graph->numVertices; i++) {
        visited[i] = false;
    }
    printf("从顶点 %d 开始的DFS遍历: ", startVertex);
    // 从起始顶点开始DFS
    DFSUtil(graph, startVertex, visited);
    printf("\n");
    free(visited);
}
int main() {
    int vertices = 5;
    Graph* graph = createGraph(vertices);
    // 添加边，构建一个图
    // 0 -- 1 -- 3
    //  \   /
    //   2 -- 4
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 2, 4);
    DFS(graph, 0); // 从顶点0开始遍历
    // 释放内存 (省略了邻接矩阵每一行的释放)
    free(graph->adjMatrix);
    free(graph);
    return 0;
}

代码解析：

Graph 结构体使用邻接矩阵来表示图，adjMatrix[i][j] = true 表示顶点 i 和 j 之间有边。
DFSUtil 是递归的核心函数。
- visited[vertex] = true; 标记当前节点为已访问，这是防止陷入死循环的关键。
- for 循环遍历当前节点的所有邻接节点。
- if (graph->adjMatrix[vertex][i] && !visited[i]) 是判断条件：存在边 且 邻接节点未被访问，如果满足条件，就递归调用 DFSUtil。
DFS 函数是封装好的接口，负责创建和初始化 visited 数组，并调用 DFSUtil。

学习路径建议

第一步：理解概念，不看代码，先看视频或图文，理解“一条路走到黑”的遍历思想。
第二步：掌握树的DFS，从二叉树的前序遍历开始，因为它最直观，手动模拟代码的执行过程，画出递归调用栈的变化。
第三步：掌握图的DFS，重点理解visited 数组的作用，这是图和树DFS实现的最大区别，同样，手动模拟一个小图的遍历过程。
第四步：练习编程，自己亲手敲一遍上面的代码，并尝试修改（实现中序、后序遍历，或者用邻接表表示图）。
第五步：解决实际问题，尝试用DFS解决一些经典问题，如：
- 迷宫问题：将迷宫看作图，起点到终点的路径。
- N皇后问题：在棋盘上放置N个皇后，使得它们互不攻击。
- 岛屿数量：LeetCode等平台上的经典题目。

希望这份详细的指南能帮助你顺利掌握深度优先搜索算法！祝你学习愉快！

如何用C语言实现深度搜索算法视频教学？