深度优先搜索（Depth-First Search，DFS）是一种在图中遍历或搜索的方法。它从图的某个顶点开始，沿着树的深度遍历图的各个顶点，直到遍历完整个图。DFS在C语言中有着广泛的应用，如拓扑排序、求解迷宫问题、判断有向图的强连通性等。本文将详细介绍DFS的原理及其在C语言中的应用。
一、DFS的原理
1. 基本思想
DFS的基本思想是：从图的某个顶点出发，先沿着一条路径走到底，然后再回溯，继续沿着另一条路径走到底，直到遍历完所有顶点。
2. 算法步骤
（1）访问顶点v；
（2）递归地以v的邻接顶点为起点，进行深度优先搜索；
（3）如果v的邻接顶点已经访问过，则跳过，继续访问下一个邻接顶点。
3. 算法实现
在C语言中，可以使用递归和非递归两种方式实现DFS。以下是一个递归实现DFS的示例代码：
```c
include
define MAX_VERTICES 100
// 定义图的结构体
typedef struct Graph {
int numVertices;
int adjMatrix[MAX_VERTICES][MAX_VERTICES];
} Graph;
// 初始化图的邻接矩阵
void initializeGraph(Graph g, int numVertices) {
g->numVertices = numVertices;
for (int i = 0; i < numVertices; i++) {
for (int j = 0; j < numVertices; j++) {
g->adjMatrix[i][j] = 0;
}
}
}
// DFS遍历
void dfs(Graph g, int v, int visited[]) {
visited[v] = 1; // 标记v为已访问
printf(\
