**深度优先搜索（Depth-First Search，DFS）是一种用于遍历或搜索树形结构以及图的算法。**其基本思想是从根节点开始，尽可能深地探索分支，直到达到某个节点的叶子节点，然后回溯到上一个节点继续探索其他路径。
在C语言中，我们可以用递归的方式来实现DFS。以下是一个简单的DFS遍历无向图的例子：
#include <stdio.h>
#define MAX vertices// 图的邻接表表示
int graph[MAX][MAX];// 顶点数
int V;// DFS函数
void dfs(int v) {// 标记当前节点为已访问printf("%d ", v);// 遍历邻居节点并递归调用dfs()for (int i = 0; i < V; i++) {if (graph[v][i] == 1 && visited[i] == false) {visited[i] = true;dfs(i);}}
}int main() {// 初始化图和标记数组int edges[] = {0, 1, 0, 2, 0, 3};int edges_count = sizeof(edges) / sizeof(edges[0]);V = 4;visited = new bool[V]; // 假设visited数组已经初始化为false// 填充邻接表for (int i = 0; i < edges_count; i += 2) {graph[edges[i]][edges[i + 1]] = 1;graph[edges[i + 1]][edges[i]] = 1; // 无向图，双向边}// 从任意节点开始进行DFSdfs(0); // 假设从节点0开始return 0;
}
在这个例子中，visited数组用于跟踪每个节点是否已被访问过。每次遇到未访问的节点，就将其加入堆栈，并递归地访问它的相邻节点，直至所有可达节点都被遍历过。
拓扑排序
拓扑排序是一种针对有向无环图 (DAG) 的算法。它将图中的节点排序，使得对于图中的每条边 (u, v)，节点 u 总是出现在节点 v 之前。换句话说，它按照节点的依赖关系进行排序。 如果一个图包含环，则无法进行拓扑排序。
C语言代码 (使用 Kahn 算法):
#include <stdio.h>
#include <stdlib.h>#define MAX_VERTICES 100int adjMatrix[MAX_VERTICES][MAX_VERTICES];
int inDegree[MAX_VERTICES];
int numVertices;int main() {// 初始化图 (邻接矩阵) 和 inDegree 数组// ... 计算每个节点的入度 (inDegree)int* queue = (int*)malloc(numVertices * sizeof(int));int head = 0, tail = 0;// 将所有入度为 0 的节点添加到队列for (int i = 0; i < numVertices; i++) {if (inDegree[i] == 0) {queue[tail++] = i;}}while (head < tail) {int vertex = queue[head++];printf("%d ", vertex);// 更新邻接节点的入度for (int i = 0; i < numVertices; i++) {if (adjMatrix[vertex][i] == 1) {inDegree[i]--;if (inDegree[i] == 0) {queue[tail++] = i;}}}}free(queue);return 0;
}
DFS 与拓扑排序的关系:
DFS 可以用来检测图中是否存在环，这是拓扑排序的先决条件。如果在 DFS 过程中检测到环，则无法进行拓扑排序。 一个常用的拓扑排序算法，是基于DFS的后序遍历来实现的，通过反转后序遍历的结果得到拓扑排序。
具体来说，利用DFS进行拓扑排序步骤如下：
1 DFS遍历图，记录每个节点的完成时间 (finishing time)。 完成时间指的是该节点及其所有子节点的 DFS 遍历结束后记录的时间戳。
2 根据完成时间降序排列节点，即得到拓扑排序结果。 完成时间晚的节点意味着其依赖关系在更深的层次，因此应该排在更后面。
虽然DFS可以辅助拓扑排序，但它们不是等价的。DFS是一个通用的图遍历算法，而拓扑排序只适用于DAG，并且其目标是生成一个特定的节点顺序。