拓扑排序是对有向无环图的节点进行线性排序，使得对于图中的每一条有向边u->v，节点u都排在节点v之前。DFS版本的拓扑排序通过深度优先遍历结合节点状态标记实现，核心是利用递归的回溯特性完成节点排序。
节点访问状态定义
实现DFS版拓扑排序需要为节点定义三种状态，不同状态对应不同的遍历阶段：
- 未访问：节点还未被DFS遍历到，初始时所有节点都处于该状态
- 访问中：节点已经进入DFS递归调用，但还未完成所有后续节点的遍历，此时如果再次遇到该状态的节点，说明图中存在环，无法进行拓扑排序
- 已访问：节点已经完成所有后续节点的遍历，可以加入拓扑排序结果
递归逻辑梳理
DFS递归的核心流程如下：
- 遍历所有节点，对每个未访问的节点启动DFS遍历
- 进入DFS函数后，先将当前节点标记为访问中
- 遍历当前节点的所有邻接节点，如果邻接节点未访问，则递归调用DFS；如果邻接节点处于访问中状态，说明存在环，直接返回错误
- 当前节点的所有邻接节点都处理完成后，将当前节点标记为已访问，并把当前节点加入拓扑排序结果的头部（因为递归是回溯时加入，所以结果顺序是逆序的，最后需要反转）
完整C++源码实现
以下是完整的DFS版拓扑排序实现代码，包含状态定义、DFS递归函数和主调用逻辑：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 定义节点访问状态枚举
enum VisitState {
UNVISITED, // 未访问
VISITING, // 访问中
VISITED // 已访问
};
class Graph {
private:
int nodeNum; // 节点数量
vector<vector<int>> adjList; // 邻接表存储图
vector<VisitState> states; // 节点状态数组
vector<int> topoResult; // 拓扑排序结果
bool hasCycle; // 标记是否存在环
public:
// 构造函数，初始化节点数量和邻接表
Graph(int n) : nodeNum(n), adjList(n), states(n, UNVISITED), hasCycle(false) {}
// 添加有向边 u->v
void addEdge(int u, int v) {
adjList[u].push_back(v);
}
// DFS递归函数
void dfs(int node) {
// 如果已经检测到环，直接返回
if (hasCycle) return;
// 将当前节点标记为访问中
states[node] = VISITING;
// 遍历所有邻接节点
for (int neighbor : adjList[node]) {
if (states[neighbor] == UNVISITED) {
// 邻接节点未访问，递归处理
dfs(neighbor);
} else if (states[neighbor] == VISITING) {
// 邻接节点处于访问中，说明存在环
hasCycle = true;
return;
}
// 邻接节点已访问则无需处理
}
// 所有邻接节点处理完成，标记为已访问，加入结果
states[node] = VISITED;
topoResult.push_back(node);
}
// 执行拓扑排序，返回是否成功（无环返回true）
bool topologicalSort() {
hasCycle = false;
topoResult.clear();
// 重置所有节点状态为未访问
fill(states.begin(), states.end(), UNVISITED);
// 遍历所有节点，对未访问节点启动DFS
for (int i = 0; i < nodeNum; i++) {
if (states[i] == UNVISITED) {
dfs(i);
if (hasCycle) {
return false;
}
}
}
// 反转结果，得到正确的拓扑顺序
reverse(topoResult.begin(), topoResult.end());
return true;
}
// 打印拓扑排序结果
void printResult() {
if (topoResult.empty()) {
cout << "无有效拓扑排序结果" << endl;
return;
}
cout << "拓扑排序结果：";
for (int node : topoResult) {
cout << node << " ";
}
cout << endl;
}
};
int main() {
// 创建包含6个节点的图
Graph g(6);
// 添加有向边，构建无环图
g.addEdge(5, 2);
g.addEdge(5, 0);
g.addEdge(4, 0);
g.addEdge(4, 1);
g.addEdge(2, 3);
g.addEdge(3, 1);
// 执行拓扑排序
if (g.topologicalSort()) {
g.printResult();
} else {
cout << "图中存在环，无法进行拓扑排序" << endl;
}
// 构建有环图的测试
Graph g2(3);
g2.addEdge(0, 1);
g2.addEdge(1, 2);
g2.addEdge(2, 0);
if (g2.topologicalSort()) {
g2.printResult();
} else {
cout << "图中存在环，无法进行拓扑排序" << endl;
}
return 0;
}
代码说明
上述代码中，VisitState枚举定义了三种节点状态，Graph类的dfs函数实现了核心递归逻辑，通过hasCycle标记判断图中是否存在环。拓扑排序的结果是在递归回溯时加入数组的，因此初始得到的是逆序结果，需要调用reverse函数反转得到正确的顺序。
如果图中有环，算法会在DFS过程中检测到访问中的节点再次出现，此时直接标记hasCycle为true，终止后续遍历，返回拓扑排序失败的结果。