拓扑排序

一、基本概念

1.定义

拓扑排序是对一个有向无环图（DAG）中所有顶点的一种线性排序，使得对于图中的每一条有向边 (u, v)，顶点 u 在顶点 v 之前。这种排序确保了在执行任务时，所有依赖于某个任务的任务都在该任务完成之后开始。

2.特点

• 有向无环图：拓扑排序只适用于有向无环图（DAG），因为环会导致依赖关系的循环，使得无法确定顺序。
• 不唯一性：拓扑排序可能不唯一，同一个图可以有多个有效的拓扑排序。

3.例子

考虑一个项目任务的依赖关系：

• 任务A必须在任务B之前完成。
• 任务C必须在任务B之前完成。
• 任务D必须在任务B之前完成。

这种关系可以表示为图：

可能的拓扑排序有：

ACDB

ADCB

注意：每个DAG都有至少一个拓扑排序，但并非所有的有向图都有拓扑排序。

二、Kahn算法求解

1. 算法概述

Kahn算法是一种用于拓扑排序的算法，利用图的入度（指向某个顶点的边的数量）来找到可以先执行的节点。它逐步构建拓扑排序，确保所有依赖关系得到满足。

2. 算法步骤

1. 计算入度：
   • 初始化一个入度数组，统计每个顶点的入度。
   • 对于每条有向边 (u, v)，增加顶点 v 的入度。
2. 初始化队列：
   • 创建一个队列，将所有入度为0的顶点入队。这些顶点没有依赖，可以立即开始处理。
3. 处理队列：
   • 当队列不为空时：
     • 从队列中取出一个顶点 u，将其加入拓扑排序结果中。
     • 遍历所有邻接顶点 v，将其入度减1。
     • 如果某个邻接顶点 v 的入度减至0，将其加入队列。
4. 检查结果：
   • 如果拓扑排序结果中顶点的数量少于图中顶点的数量，说明图中存在环，无法完成拓扑排序。

注意：

队列用栈也可以，拓扑排序可能有多种结果，队列和栈得到的顺序可能不同

3.主要代码实现

// Kahn算法实现拓扑排序
void topologicalSortKahn(const vector<vector<int>>& graph, int V) {
    vector<int> indegree(V, 0); // 1. 初始化入度数组，统计每个节点的入度
    
    for (int u = 0; u < V; ++u) { // 遍历图中的每个节点
        for (int v : graph[u]) { // 遍历节点u的所有邻接节点v
            indegree[v]++; // 增加邻接节点v的入度
        }
    }

    queue<int> q; // 2. 初始化队列，存储所有入度为0的节点
    
    for (int i = 0; i < V; ++i) { // 将所有入度为0的节点入队
        if (indegree[i] == 0) {
            q.push(i); // 没有依赖的节点可以立即处理
        }
    }

    vector<int> topoOrder; // 3. 存储拓扑排序结果的向量
    
    while (!q.empty()) { // 4. 处理队列，直到队列为空
        int u = q.front(); // 从队列中取出一个节点u
        q.pop(); // 弹出节点u
        
        topoOrder.push_back(u); // 将节点u添加到拓扑排序结果中

        for (int v : graph[u]) { // 遍历u的所有邻接节点v
            if (--indegree[v] == 0) { // 更新邻接节点v的入度
                q.push(v); // 如果v的入度变为0，将其入队
            }
        }
    }

    if (topoOrder.size() != V) { // 5. 检查是否存在环
        cout << "图中存在环，无法进行拓扑排序。" << endl; // 如果存在环，输出提示
    } else {
        cout << "拓扑排序结果："; // 打印拓扑排序结果
        for (int node : topoOrder) { // 输出每个节点
            cout << node << " "; 
        }
        cout << endl; 
    }
}

4. 复杂度分析

• 时间复杂度：O(V + E)，其中 V 是顶点数，E 是边数。每个节点和边都被处理一次。
• 空间复杂度：O(V)，用于存储入度数组和队列。

三、DFS算法求解

1. 算法概述

DFS算法利用递归的方法遍历图，通过标记节点的状态来确保在拓扑排序中遵循依赖关系。该算法在遍历完一个节点及其所有邻接节点后，将该节点加入拓扑排序结果。

2. 算法步骤

1. 标记状态：
   • 使用一个数组或向量来标记每个节点的状态：未访问、正在访问和已完成。
2. 递归处理：
   • 对于每个未访问的节点，进行DFS遍历。
   • 在遍历的过程中，将节点标记为“正在访问”。
   • 递归访问该节点的所有邻接节点。
   • 在返回时，将节点标记为“已完成”，并将其加入结果栈。

3.主要代码实现

// DFS遍历函数
void dfs(int node, vector<bool>& visited, stack<int>& Stack, const vector<vector<int>>& graph) {
    visited[node] = true; // 将当前节点标记为已访问
    for (int v : graph[node]) { // 遍历当前节点的所有邻接节点
        if (!visited[v]) { // 如果邻接节点未被访问
            dfs(v, visited, Stack, graph); // 递归访问邻接节点
        }
    }
    Stack.push(node); // 将当前节点压入栈中，表示已完成
}

// Kahn算法实现拓扑排序
void topologicalSortDFS(const vector<vector<int>>& graph, int V) {
    vector<bool> visited(V, false); // 初始化访问状态数组
    stack<int> Stack; // 用于存储拓扑排序结果

    for (int i = 0; i < V; ++i) { // 遍历所有节点
        if (!visited[i]) { // 如果节点未被访问
            dfs(i, visited, Stack, graph); // 调用DFS
        }
    }

    cout << "拓扑排序结果："; // 打印拓扑排序结果
    while (!Stack.empty()) { // 反转栈中的结果
        cout << Stack.top() << " "; // 输出栈顶元素
        Stack.pop(); // 弹出栈顶元素
    }
    cout << endl; 
}

4. 复杂度分析

• 时间复杂度：O(V + E)，其中 V 是顶点数，E 是边数。每个节点和边都被访问一次。
• 空间复杂度：O(V)，用于存储访问状态数组和栈。