FC15-基于深度优先搜索（DFS）的拓扑排序算法¶

代码实现¶

C++
// DFS函数
void DFS(ALGraph G, int v, int visit[], int res[], int *k) {
    visit[v] = 1; // 标记v顶点已访问
    for (ArcNode *temp = G.adjlist[v].firstarc; temp != NULL; temp = temp->nextarc) {
        int w = temp->adjvex;
        if (visit[w] == 0) { // 如果w顶点未被访问
            DFS(G, w, visit, res, k); // 对w顶点进行DFS
        }
    }
    res[(*k)++] = v; // 将顶点v加入拓扑序列
}

// 拓扑排序函数
void TPsort(ALGraph G) {
    int visit[G.vexnum]; // 访问标记数组
    int res[G.vexnum];   // 拓扑序列数组
    int k = 0;           // 拓扑序列数组的索引

    // 初始化访问标记数组
    for (int i = 0; i < G.vexnum; i++) {
        visit[i] = 0;
    }

    // 对每个顶点进行DFS
    for (int i = 0; i < G.vexnum; i++) {
        if (visit[i] == 0) { // 如果顶点i未被访问
            DFS(G, i, visit, res, &k);
        }
    }

    // 输出拓扑序列（逆序）
    for (int i = k - 1; i >= 0; i--) {
        cout << res[i] << " ";
    }
}

代码逻辑解析¶

1. 拓扑排序的基本概念¶

拓扑排序是对一个有向无环图(DAG)的所有顶点的一种线性排序，使得对于任何两个顶点 $ u $ 和 $ v $，如果存在一条从 $ u $ 到 $ v $ 的路径，则在排序中 $ u $ 出现在 $ v $ 之前。

2. 关键数据结构¶

结构体定义：¶

ArcNode：用于描述边或弧的信息。

C++
typedef struct ArcNode {
    int adjvex;              // 弧头对应的顶点位置
    struct ArcNode *nextarc; // 下一条弧的指针
} ArcNode;

VNode：表示图中的顶点及其关联的第一条弧。

C++
typedef struct VNode {
    int data;                // 顶点的数据域
    ArcNode *firstarc;       // 第一条依附于该顶点的弧
} VNode, AdjList[100];

ALGraph：整个图的结构体，包含邻接表、顶点数量和弧的数量。

C++
typedef struct {
    AdjList adjlist;         // 邻接表
    int vexnum, arcnum;      // 当前顶点数与弧数
} ALGraph;

3. 核心函数详解¶

DFS函数（递归处理）¶

C++
void DFS(ALGraph G, int v, int visit[], int res[], int *k)

此函数以深度优先的方式遍历图，并记录完成时间顺序，最后将顶点加入结果数组。

参数说明：
G: 图对象
v: 当前访问的顶点编号
visit[]: 已访问标志数组
res[]: 存放拓扑序列的结果数组
k: 当前拓扑序列插入位置的指针
执行流程：
将当前顶点标记为已访问；
遍历其所有邻接顶点；
若某邻接顶点未被访问，则递归调用DFS；
回溯后，将当前顶点压入结果栈中（即放入结果数组末尾）。

拓扑排序主函数¶

C++
void TPsort(ALGraph G)

负责初始化并启动DFS过程，并按逆序输出拓扑排序结果。

流程简述：
初始化访问标记数组 visit[]；
遍历每一个尚未访问过的顶点，依次调用DFS；
最终按照DFS结束的时间倒序输出结果。

时间复杂度分析¶

1. DFS遍历阶段¶

每个顶点最多访问一次，每条边也只会检查一次。因此总时间为：

\[ \text{Time Complexity} = O(V + E) \]

其中 $ V $ 是顶点数目，$ E $ 是边数。

2. 整体时间复杂度¶

由于整个过程只做一次完整的DFS遍历，故总体时间复杂度也为：

\[ O(V + E) \]

空间复杂度分析¶

1. 辅助空间占用¶

visit[]：大小为 $ V $
res[]：大小为 $ V $
递归栈最大深度取决于图中最长的一条路径，最坏情况下为 $ O(V) $

2. 总体空间复杂度¶

\[ O(V) \]

较难理解部分的说明¶

1. 为什么需要反向输出？¶

因为DFS是在回溯阶段才把顶点加入结果集的，此时已完成对其所有子树的探索。换句话说，最先完成的是没有出度的顶点，这些应排在最后面。

举个例子：

graph TD
A --> B
B --> C
C --> D

在这个简单的链式结构中，D先完成→C→B→A。但由于我们希望A出现在前面，所以必须反转输出顺序。

2. 图解说明¶

假设有如下DAG：

Text Only
1 2 3	`0 → 1 → 3 ↓ ↓ 2 → 4`

邻接关系如下：

顶点	邻接顶点
0	1, 2
1	3, 4
2	4
3
4

执行DFS的过程大致如下：

从0开始DFS → 1 → 3（3无后续），返回；
继续1 → 4（4无后续），返回；
返回至0 → 2 → 4（已访问过），返回；
最终完成0；

得到的完成顺序是 [3, 4, 1, 2, 0]，反转后为 [0, 2, 1, 4, 3]，符合拓扑序。

延伸知识点¶

1. Kahn算法对比¶

另一种常见的拓扑排序方法是 Kahn 算法，它利用了“入度”概念：

C++
void KahnTopoSort(ALGraph G) {
    queue<int> Q;
    vector<int> inDegree(G.vexnum, 0);

    // 计算各顶点的入度
    for (int i = 0; i < G.vexnum; ++i) {
        ArcNode* p = G.adjlist[i].firstarc;
        while (p != nullptr) {
            inDegree[p->adjvex]++;
            p = p->nextarc;
        }
    }

    // 将所有入度为0的顶点入队
    for (int i = 0; i < G.vexnum; ++i) {
        if (inDegree[i] == 0)
            Q.push(i);
    }

    vector<int> topoOrder;
    while (!Q.empty()) {
        int u = Q.front(); Q.pop();
        topoOrder.push_back(u);
        ArcNode* p = G.adjlist[u].firstarc;
        while (p != nullptr) {
            inDegree[p->adjvex]--;
            if (inDegree[p->adjvex] == 0)
                Q.push(p->adjvex);
            p = p->nextarc;
        }
    }

    // 输出拓扑序列
    for (auto x : topoOrder)
        cout << x << " ";
}

特性	DFS-based Topo Sort	Kahn Algorithm
思想基础	DFS完成时间	入度消减
实现方式	递归	BFS+队列
是否检测环路	可配合强连通分量判断	易于判断是否存在环
应用场景	敏感依赖分析	任务调度

2. 实际应用场景¶

课程安排问题：某些课程有前置要求，如必须先修完A才能选修B；
编译构建系统：模块之间可能存在依赖关系，需确定正确的构建顺序；
软件工程依赖管理：Maven、Gradle等工具会根据依赖生成拓扑排序；
项目管理计划制定：关键路径分析需要用到类似的拓扑技术。

3. 相关算法扩展¶

如何判断是否有环？¶

若图中存在环，则无法形成合法的拓扑排序。可借助以下方法检测：

在DFS过程中引入三种状态：
白色：未发现；
灰色：正在访问（尚未退出）；
黑色：已经完成。

若遇到灰色节点，说明形成了环。

C++
enum Color { WHITE, GRAY, BLACK };
Color color[MAX_VERTICES];

bool dfsCheckCycle(ALGraph G, int u) {
    color[u] = GRAY;
    for (ArcNode* p = G.adjlist[u].firstarc; p != nullptr; p = p->nextarc) {
        int v = p->adjvex;
        if (color[v] == GRAY) return true;
        if (color[v] == WHITE && dfsCheckCycle(G, v)) return true;
    }
    color[u] = BLACK;
    return false;
}

总结¶

本节介绍了如何使用深度优先搜索实现拓扑排序。相比其他方法，这种方法简洁高效，在图的结构合理的情况下具有良好的性能表现。掌握这种算法有助于解决各种实际生活中的依赖关系建模问题，例如任务调度、依赖解析等领域都有着广泛的应用价值。