拓扑排序详解与C++实现

理论分析

拓扑排序（Topological Sorting）是一种对有向无环图（DAG, Directed Acyclic Graph）的顶点进行排序的算法，使得对于图中的任意一条有向边(u, v)，顶点u都排在顶点v之前。

核心思想

拓扑排序的核心思想是：

1. 找到图中所有入度为0的顶点（没有前驱节点）
2. 选择其中一个顶点加入排序结果
3. 从图中删除该顶点及其所有出边（即减少其邻接顶点的入度）
4. 重复步骤1-3，直到所有顶点都被处理或发现环（此时无法进行拓扑排序）

应用场景

• 任务调度问题
• 课程安排问题
• 编译依赖关系
• 项目管理中的任务依赖关系

时间复杂度

拓扑排序的时间复杂度为O(V + E)，其中V是顶点数，E是边数，这是因为每个顶点和每条边都需要被处理一次。

C++实现代码

下面是使用Kahn算法实现拓扑排序的C++代码，包含详细注释：

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

// 拓扑排序函数
// 参数：
// - numVertices: 顶点数量
// - adj: 邻接表表示的图
// - result: 存储拓扑排序结果
// 返回值：
// - true: 成功完成拓扑排序（图是DAG）
// - false: 图中存在环，无法进行拓扑排序
bool topologicalSort(int numVertices, const vector<vector<int>>& adj, vector<int>& result) {
    // 存储每个顶点的入度
    vector<int> inDegree(numVertices, 0);
    
    // 计算所有顶点的入度
    for (int u = 0; u < numVertices; ++u) {
        for (int v : adj[u]) {
            inDegree[v]++;
        }
    }
    
    // 创建队列，存储所有入度为0的顶点
    queue<int> q;
    for (int i = 0; i < numVertices; ++i) {
        if (inDegree[i] == 0) {
            q.push(i);
        }
    }
    
    // 记录已经处理的顶点数量
    int processed = 0;
    
    // 处理队列中的顶点
    while (!q.empty()) {
        // 取出一个入度为0的顶点
        int u = q.front();
        q.pop();
        
        // 将该顶点加入结果
        result.push_back(u);
        
        // 遍历该顶点的所有邻接顶点，减少它们的入度
        for (int v : adj[u]) {
            // 如果入度变为0，加入队列
            if (--inDegree[v] == 0) {
                q.push(v);
            }
        }
        
        processed++;
    }
    
    // 如果处理的顶点数不等于总顶点数，说明存在环
    return processed == numVertices;
}

int main() {
    // 示例1：有向无环图（DAG）
    cout << "示例1：有向无环图" << endl;
    int numVertices1 = 6;
    vector<vector<int>> adj1(numVertices1);
    
    // 构建图
    adj1[5].push_back(2);
    adj1[5].push_back(0);
    adj1[4].push_back(0);
    adj1[4].push_back(1);
    adj1[2].push_back(3);
    adj1[3].push_back(1);
    
    vector<int> result1;
    if (topologicalSort(numVertices1, adj1, result1)) {
        cout << "拓扑排序结果：";
        for (int v : result1) {
            cout << v << " ";
        }
        cout << endl << endl;
    } else {
        cout << "图中存在环，无法进行拓扑排序" << endl << endl;
    }
    
    // 示例2：包含环的图
    cout << "示例2：包含环的图" << endl;
    int numVertices2 = 4;
    vector<vector<int>> adj2(numVertices2);
    
    // 构建包含环的图（0->1->2->3->1）
    adj2[0].push_back(1);
    adj2[1].push_back(2);
    adj2[2].push_back(3);
    adj2[3].push_back(1);
    
    vector<int> result2;
    if (topologicalSort(numVertices2, adj2, result2)) {
        cout << "拓扑排序结果：";
        for (int v : result2) {
            cout << v << " ";
        }
        cout << endl;
    } else {
        cout << "图中存在环，无法进行拓扑排序" << endl;
    }
    
    return 0;
}

代码解析

1. 拓扑排序函数实现：

   • 首先计算每个顶点的入度
   • 使用队列存储所有入度为0的顶点
   • 不断从队列中取出顶点，加入结果集，并减少其邻接顶点的入度
   • 如果邻接顶点的入度变为0，则加入队列
   • 最后检查是否处理了所有顶点，判断图中是否有环

2. 示例说明：

   • 第一个示例是一个有向无环图，能够得到正确的拓扑排序结果
   • 第二个示例包含环（1->2->3->1），算法能够检测到环的存在

3. 环的检测原理： 当图中存在环时，环上的所有顶点入度都不会变为0，导致最终处理的顶点数小于总顶点数，从而判断出图中存在环。

拓扑排序不是唯一的，对于同一个图可能存在多种不同的拓扑排序结果，具体取决于入度为0的顶点的选择顺序。