目录
拓扑排序思想
拓扑排序的思想是通过对有向无环图（DAG）进行排序，将图中的节点按照一定的拓扑顺序进行排列。
拓扑排序的基本思想是，首先找到入度为0的节点，将其加入结果序列中，并将其从图中删除。然后，更新剩余节点的入度，继续找到新的入度为0的节点，重复上述过程，直到所有节点都被加入结果序列中。
具体步骤如下：
统计每个节点的入度：遍历有向图的所有边，对于每条边 (u, v)，将节点 v 的入度加1。
初始化一个队列，将入度为0的节点加入队列中。
从队列中取出一个节点，将其加入结果序列中，并将其从图中删除。同时，将该节点指向的所有邻居节点的入度减1。
重复步骤3，直到队列为空。
检查结果序列的长度是否等于图中的节点数。如果等于，则拓扑排序成功；否则，表示图中存在环，无法进行拓扑排序。
拓扑排序保证了在结果序列中，任意一条边 (u, v) 都满足 u 在 v 之前。因此，拓扑排序常用于解决依赖关系或顺序关系的问题，例如课程安排、任务调度等。
需要注意的是，拓扑排序只适用于有向无环图，因为有向无环图中一定存在入度为0的节点，而有环的图中不存在入度为0的节点。
代码实现
以下是拓扑排序的实现代码：
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<int> topologicalSort(vector<vector<int>>& graph) {
int n = graph.size();
vector<int> indegree(n, 0);
// 计算每个节点的入度
for (int i = 0; i < n; i++) {
for (int j = 0; j < graph[i].size(); j++) {
int node = graph[i][j];
indegree[node]++;
}
}
// 使用队列来存储入度为0的节点
queue<int> q;
for (int i = 0; i < n; i++) {
if (indegree[i] == 0) {
q.push(i);
}
}
vector<int> result;
while (!q.empty()) {
int node = q.front();
q.pop();
result.push_back(node);
// 将当前节点的所有邻居的入度减1，并将入度变为0的邻居加入队列
for (int i = 0; i < graph[node].size(); i++) {
int neighbor = graph[node][i];
indegree[neighbor]--;
if (indegree[neighbor] == 0) {
q.push(neighbor);
}
}
}
return result;
}
int main() {
// 例子：有向图的邻接矩阵表示
vector<vector<int>> graph = {{1, 3}, {2}, {3, 4}, {}, {5}, {}}; // 0->1, 0->3, 1->2, 2->3, 2->4, 4->5
vector<int> result = topologicalSort(graph);
cout << "拓扑排序结果：";
for (int i = 0; i < result.size(); i++) {
cout << result[i] << " ";
}
cout << endl;
return 0;
}
上述代码实现了拓扑排序的算法。具体步骤如下：
- 首先，根据给定的有向图（邻接矩阵表示），计算每个节点的入度。
- 创建一个队列，将入度为0的节点加入队列中。
- 进行循环，当队列不为空时，执行以下操作：
- 取出队首节点，并将其放入结果数组中。
- 将当前节点的所有邻居的入度减1。
- 如果邻居节点的入度变为0，将其加入队列中。
- 返回结果数组，即为拓扑排序的结果。
在上述代码的示例中，给定了一个有向图的邻接矩阵表示，然后调用 topologicalSort 函数进行拓扑排序，并输出排序结果。
拓扑排序相关数据结构
实现拓扑排序算法，需要使用一个队列和一个数组来辅助计算节点的入度。具体介绍如下：
队列：用于存储入度为0的节点。在计算每个节点的入度后，将入度为0的节点加入队列中。对于每个入度为0的节点，都可以保证其之前没有其他节点，因此可以将其放在结果序列的最前面。在实际算法中，我们可以使用一个队列来存储入度为0的节点。
数组：用于计算每个节点的入度。在遍历有向图中的边时，可以统计每个节点的入度，将其记录在数组中。当节点的入度为0时，将其加入队列中。
在实际实现过程中，可以通过邻接表或邻接矩阵来表示有向图，便于计算每个节点的入度和邻居节点。具体实现方式可以参考上一篇回答中给出的示例代码。
总结来说，拓扑排序的相关数据结构包括队列和数组，其中队列用于存储入度为0的节点，数组用于计算每个节点的入度。在实际实现中，通常会使用邻接表或邻接矩阵来表示有向图。
