设计C++算法求解有向无环图的所有拓扑序列。
时间: 2024-05-15 09:14:05 浏览: 99
有向无环图的全拓扑排序
拓扑序列是指对于有向无环图中每个节点,它在序列中出现的位置都在它所有前驱节点之后。我们可以使用深度优先搜索和拓扑排序来求解有向无环图的所有拓扑序列。
具体做法如下:
1. 构建邻接表存储有向无环图。
2. 统计每个节点的入度。
3. 将入度为0的节点加入一个队列中。
4. 从队列中取出一个节点,将其加入拓扑序列中。
5. 对该节点的所有后继节点的入度减1。
6. 如果某个后继节点的入度变为0,则将其加入队列中。
7. 重复步骤4-6,直到队列为空。
这个算法可以保证输出所有拓扑序列,因为每次从队列中取出一个节点时,都是选择了一个入度为0的节点,这个节点可以在序列中排在任何一个前驱节点的位置之后。因此,我们可以把每次取出的节点都插入到一个临时的拓扑序列中,然后递归处理剩余的节点,直到所有节点都被处理完毕。
下面是C++代码实现:
```
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
void dfs(vector<vector<int>>& graph, vector<int>& indegrees, vector<int>& path, vector<vector<int>>& result) {
if (path.size() == graph.size()) {
result.push_back(path);
return;
}
for (int i = 0; i < graph.size(); i++) {
if (indegrees[i] == 0) {
queue<int> q;
for (int j = 0; j < graph[i].size(); j++) {
int next = graph[i][j];
indegrees[next]--;
if (indegrees[next] == 0) {
q.push(next);
}
}
path.push_back(i);
dfs(graph, indegrees, path, result);
path.pop_back();
for (int j = 0; j < graph[i].size(); j++) {
int next = graph[i][j];
indegrees[next]++;
}
while (!q.empty()) {
int next = q.front();
q.pop();
indegrees[next]++;
}
}
}
}
vector<vector<int>> allTopologicalSorts(vector<vector<int>>& graph) {
vector<vector<int>> result;
vector<int> indegrees(graph.size(), 0);
for (int i = 0; i < graph.size(); i++) {
for (int j = 0; j < graph[i].size(); j++) {
int next = graph[i][j];
indegrees[next]++;
}
}
vector<int> path;
dfs(graph, indegrees, path, result);
return result;
}
int main() {
vector<vector<int>> graph = {{1, 2}, {3}, {3}, {4}, {}};
vector<vector<int>> result = allTopologicalSorts(graph);
for (int i = 0; i < result.size(); i++) {
for (int j = 0; j < result[i].size(); j++) {
cout << result[i][j] << " ";
}
cout << endl;
}
return 0;
}
```
以上代码实现了所有拓扑序列的求解,并输出了所有解。
阅读全文