企业官网建设流程全解析

• 教程

DFS（深度优先搜索）与 BFS（广度优先搜索）是图与树结构中最基础、应用最广泛的两类遍历算法，也是面试与工程实践中高频出现的核心考点。本文以 Learn-Algorithms 仓库中 5 Graph/DFS 和 BFS.md 文档为骨架，结合仓库内二叉树、堆等源码实现，系统讲解两种算法的核心思想、数据结构差异、代码模板、应用场景与典型面试题，帮助读者从原理到实战一次性掌握 DFS/BFS。

一、算法总览：两条截然不同的搜索路径

在 Learn-Algorithms 仓库的图论笔记中（见 5 Graph/README.md），图的遍历被明确划分为两类：

遍历：广度优先 BFS、深度优先 DFS

这两类算法解决的是同一个问题——如何系统地访问图中的所有顶点——但采取了完全相反的访问顺序策略。

1.1 DFS：深度优先，一条路走到黑

DFS（Depth-First Search，深度优先搜索）以"深度"为准则：从一个起点出发，先沿着一条分支一直往下走，直到走到目标节点；如果走到了尽头（没有达到目标）且无路可走，就**回溯（backtrack）**到上一步的状态，换一条没走过的路继续探索。

这正如原文档所述：

DFS：深度优先搜索，以深度为准则，先一条路走到底，直到达到目标；没有达到目标又无路可走了，那么则退回到上一步的状态，走其他路。这便是回溯上来。

核心关键词是"回溯"：DFS 天然携带回溯特性，这是它能够用于"穷举所有路径""寻找可行解"的根本原因。

1.2 BFS：广度优先，层层推进

BFS（Breadth-First Search，广度优先搜索）在面临一个路口时，会把所有岔路口都记下来，然后选择其中一个进入，记录它的分支情况，再返回去进入下一个岔路，如此反复，直到所有可达节点都被访问。

BFS：广度优先搜索，在面临一个路口时，把所有的岔路口都记下来，然后选择其中一个进入，然后将它的分路情况记录下来，然后再返回来进入另外一个岔路，并重复这样的操作。

核心特征是"按层扩散"：BFS 总是先访问距离起点最近的一层节点，再逐层向外推进。

1.3 一句话对比（原文档要点）

DFS 用递归的形式，用到了栈结构，先进后出；BFS 选取状态用队列的形式，先进先出。

二、核心差异的根源：栈与队列的选择

原文档一句话点破了两种算法的本质区别——DFS 用栈（递归调用栈），BFS 用队列。这一差异直接决定了算法的行为特征。

2.1 为什么 DFS 需要栈：先进后出（LIFO）

DFS 需要"后进入的分支先处理"。递归函数执行时，系统调用栈天然满足"先进后出"：函数 A 调用 B，B 必须先返回，A 才能继续。因此 DFS 用递归实现时无需显式建栈，调用栈就是它的栈。

如果用显式栈模拟 DFS，核心模板如下：

// 显式栈版 DFS void dfs_iterative(int start) { Stack s; push(&s, start); visited[start] = 1; while (!stack_empty(&s)) { int u = pop(&s); process(u); // 访问节点 for (int v : neighbors(u)) { if (!visited[v]) { visited[v] = 1; push(&s, v); // 后进先出，实现深度优先 } } } }

注意：栈的 LIFO 特性决定了"越晚压入的节点越先被访问"，这正是沿一条分支深入下去的驱动力。

2.2 为什么 BFS 需要队列：先进先出（FIFO）

BFS 需要"先记录的分支先处理"，只有队列的 FIFO 语义能满足：先入队的节点（距离更近的一层）先被出队访问，从而保证按层扩散。仓库中 4 Tree/1-二叉树 /btree/队列.h 实现了一个链式队列，其注释与实现精确对应了 BFS 对数据结构的要求：

只在一段进行插入，另一端删除元素

该队列用head（队头）与tail（队尾）两个指针维护结构，enQueue在队尾插入新节点、deQueue从队头弹出节点，isEmpty通过q->head == q->tail判断队列是否为空，O(1) 完成入队出队操作：

// 入队（加入到队尾） Status enQueue(Queue *q, ElemType e) { LinkQueue *newNode = (LinkQueue *)malloc(sizeof(LinkQueue)); if (!newNode) return ERROR; newNode->elem = e; newNode->next = NULL; q->tail->next = newNode; q->tail = newNode; // 队尾插入 q->length++; return OK; } // 出队（队头弹出） Status deQueue(Queue *q, ElemType *e) { LinkQueue *p = q->head->next; if (!p) return ERROR; // 队列空 if (e) *e = p->elem; LinkQueue *temp = p->next; q->head->next = temp; if (p == q->tail) // 只有一个元素时防止队尾指针丢失 q->tail = q->head; free(p); q->length--; return OK; }

源码中还注意到顺序存储队列的经典缺陷（4 Tree/1-二叉树 /btree/队列.h 注释）：

在队列采用顺序存储时，有一个毛病，就是队列操作一段时间后，头指针到了队列容器的尾部，而头指针前面的容器内存不可用了，造成内存极大的浪费，这个问题可以通过循环队列来解决。但是在链式队列上则不存在这样的问题

这一细节对理解 BFS 工程实现很有价值：大规模图遍历时若用数组队列会频繁扩容浪费内存，链式队列或循环队列是更稳妥的选择。

三、二叉树上的 DFS 与 BFS：仓库源码实战

Learn-Algorithms 仓库在二叉树部分给出了 DFS 与 BFS 的完整 C 语言实现，是理解两种算法最直观的"练武场"。

3.1 二叉树结构定义

仓库 4 Tree/1-二叉树 /btree/bintree.c 使用链表方式构建二叉树：

typedef struct BiTNode { char item; struct BiTNode *lChild, *rChild; } BiTNode, *BiTree;

节点只有左右两个分支，这让 DFS 和 BFS 的实现变得极其清晰。

3.2 DFS 在二叉树上的三种体现：前序、中序、后序遍历

二叉树的先序、中序、后序遍历都是 DFS——它们只是改变了"访问节点"与"递归进入子树"的先后顺序。仓库 bintree.c 中三种遍历全部采用递归（即调用栈）实现：

// 前序遍历：根 -> 左 -> 右（先访问，后递归） int PreOrderTraverse(BiTree T) { if (T) { printf("%c\n", T->item); PreOrderTraverse(T->lChild); PreOrderTraverse(T->rChild); } return 0; } // 中序遍历：左 -> 根 -> 右 int InOrderTraverse(BiTree T) { if (T) { InOrderTraverse(T->lChild); printf("%c\n", T->item); InOrderTraverse(T->rChild); } return 0; } // 后序遍历：左 -> 右 -> 根（先递归，最后访问） int PostOrderTraverse(BiTree T) { if (T) { PostOrderTraverse(T->lChild); PostOrderTraverse(T->rChild); printf("%c\n", T->item); } return 0; }

这三个函数印证了原文档的论断："DFS 用递归的形式，用到了栈结构"。每一次递归调用进入更深一层，返回时自然完成回溯。

3.3 BFS 在二叉树上的体现：层序遍历

二叉树的层序遍历（Level Order）就是 BFS。仓库 bintree.c 中LevelOrderTraverse用上述链式队列实现了真正的"先进先出"逐层访问：

// 广度优先遍历（队列实现） int LevelOrderTraverse(BiTree T) { if (T) { Queue queue; initQueue(&queue); BiTree u = (BiTree)malloc(sizeof(BiTNode)); enQueue(&queue, T); // 根节点先入队 while (!isEmpty(&queue)) { deQueue(&queue, &u); // 队头出队并访问 printf("%c", u->item); if (u->lChild) enQueue(&queue, u->lChild); // 左孩子入队 if (u->rChild) enQueue(&queue, u->rChild); // 右孩子入队 } } return 0; }

对照队列实现（队列.h 与 bintree.c）可清晰看到 BFS 的完整调用链：enQueue入队 →isEmpty判空 →deQueue出队 → 访问 → 孩子节点入队。由于先入队的上一层节点总是先出队，访问顺序天然按层展开。

仓库 bintree.c 的main函数还给出了完整的可运行流程：先按先序方式创建二叉树（输入空格表示空节点），随后依次打印前序、中序、后序与层序遍历结果：

printf("创建二叉树，输入\"空格\"创建空节点（先序方式建立二叉树）:\n"); binaryTree = CreateBiTree(); printf("前序遍历:\n"); PreOrderTraverse(binaryTree); printf("中序遍历:\n"); InOrderTraverse(binaryTree); printf("后序遍历:\n"); PostOrderTraverse(binaryTree); printf("层序遍历:\n"); LevelOrderTraverse(binaryTree);

四、通用图上的 DFS 与 BFS 模板

图比二叉树复杂在于：可能存在环，且一个节点可能有多个邻居。因此通用模板必须引入visited数组防止重复访问。

4.1 通用 DFS 模板（递归版）

void dfs(int u, int visited[], Graph *g) { visited[u] = 1; // 标记已访问，防环 process(u); // 访问/处理节点 for (int i = 0; i < g->degree[u]; i++) { int v = g->adj[u][i]; if (!visited[v]) { dfs(v, visited, g); // 深入下一层 } } }

4.2 通用 BFS 模板

void bfs(int start, int visited[], Graph *g) { Queue q; initQueue(&q); enQueue(&q, start); visited[start] = 1; while (!isEmpty(&q)) { int u; deQueue(&q, &u); process(u); // 访问节点 for (int i = 0; i < g->degree[u]; i++) { int v = g->adj[u][i]; if (!visited[v]) { visited[v] = 1; enQueue(&q, v); // 未访问邻居入队 } } } }

要点：visited标记应在入队/压栈时设置而非出队时设置，否则同一节点可能被重复入队，破坏复杂度 O(V+E) 的保证。

五、应用场景：何时用 DFS，何时用 BFS

5.1 DFS 的典型场景

• 连通性判断：判断两个节点是否连通、统计连通分量个数；
• 路径枚举与回溯：全排列、N 皇后、数独、组合问题（仓库 8 Algorithms Analysis/回溯法.md 有专门讲解）；
• 拓扑排序：以 DFS 后序顺序逆序输出可得拓扑序（见仓库 5 Graph/拓扑排序.md）；
• 二分图判定、强连通分量、桥与割点：Tarjan 系算法均基于 DFS；
• 树上的 DFS 序、子树统计：将子树问题转化为区间问题。

5.2 BFS 的典型场景

• 无权图最短路径：BFS 第一次访问到某节点时走过的步数即最短步数；
• 层序遍历：二叉树按层输出、逐层统计节点数；
• 状态空间搜索（迷宫、拼图）：用状态作为节点、操作作为边，BFS 保证找到步数最少的解；
• 多源扩散问题：多起点同时入队，如"感染扩散""腐烂橘子"类问题；
• 拓扑排序（Kahn 算法）：基于入度与队列实现。

仓库 5 Graph/README.md 列出了图的工业界应用场景（导航路径规划、任务调度、社区发现、匹配等），这些场景背后的路径搜索与连通性分析，本质上都由 DFS/BFS 支撑：

导航路径规划：用户选择开始地点和目的地之后，导航软件给出路程最短、不走高速、时长最短等方案

其中"路程最短"正是 BFS 类算法（加权场景延伸为 Dijkstra）的应用，而"连通性、社区发现"则依赖 DFS 遍历能力。

六、复杂度分析与优化技巧

6.1 时间复杂度

• DFS：每个节点访问一次、每条边检查一次，时间复杂度O(V + E)（V 为顶点数，E 为边数）。
• BFS：同样每个节点入队出队各一次、每条边检查一次，时间复杂度也是O(V + E)。

两者渐进复杂度相同，差异体现在空间与结果特性上。

6.2 空间复杂度与优化

• DFS（递归）：空间 O(树高)，最坏退化为链时 O(N)；显式栈版可避免系统调用栈溢出风险，在深图中更安全；
• BFS：空间为"最宽一层"的节点数，星型图中可达 O(N)；
• 优化技巧：
  • 用visited位图/哈希代替布尔数组，降低空间；
  • BFS 双向扩展（从起点和终点同时 BFS，相遇即停止）可将搜索空间从 b^d 降到约 2·b^(d/2)；
  • DFS 加剪枝（在递归前判断是否满足约束）大幅减少无效分支，是回溯法的核心优化（见 8 Algorithms Analysis/回溯法.md）。

七、面试高频题与 LeetCode 对照

仓库 9 Algorithms Job Interview 目录收录了大量面试代码，其中 codes/7 bianrytree/binary_search.c 等文件可作为练习素材。面试中常考的核心考点包括：

1. 递归版与迭代版互转：能写出 DFS 的显式栈版本和 BFS 的队列版本；
2. visited 标记时机：解释为何入队时标记优于出队时标记；
3. 复杂度分析：准确说出 O(V+E) 与空间占用；
4. 场景判别：最短路径/逐层扩散优先 BFS，枚举/回溯/连通性优先 DFS。

八、小结

DFS 与 BFS 是算法学习的基石，也是无数高级算法（Dijkstra、A*、Tarjan、拓扑排序、最大流）的共同底座。掌握本节内容后，可进一步阅读仓库中的 5 Graph/README.md 了解图论整体框架、5 Graph/最短路径.md 学习 BFS 在加权图上的延伸（Dijkstra），并通过 4 Tree/1-二叉树 /btree/bintree.c 亲手运行一遍完整代码，完成从理论到实战的闭环。

• 教程