在 C++ 中根据给定的依赖关系查找任务的顺序
假设我们有 n 个不同的任务；这些任务的标签从 0 到 n-1。某些任务可能有先决条件任务，因此，例如，如果我们要选择任务 2，那么我们必须先完成任务 1，它表示为一对 − [2, 1]。如果我们有任务总数和先决条件对列表，我们必须找到任务的顺序来完成所有任务。如果有多个正确的顺序，我们可以返回其中一个。如果无法完成所有给定的任务，则返回一个空数组。
因此，如果输入为 n = 4，且 A = [[1, 0], [2, 0], [3, 2], [3, 1],[4,2]]，则输出为 [0, 2, 1, 4, 3]
为了解决这个问题，我们将遵循以下步骤 −
定义一个函数 dfs()，它将采用 graph、start、onpath、已访问的数组、toposort 数组，
如果已标记 visit[start]，则 −
返回 false
onpath[start] := true, visit[start] := true
对于 graph[start] 中的每个邻居，执行
如果 onpath[neighbor] 为 true 或 dfs(graph, neighbour, onpath, accessed, toposort) 为 true，则 −
返回 true
在 toposort 末尾插入 start
返回 onpath[start] := false
从主方法中，执行以下操作 −
graph = 创建带有 n 个顶点和边的图，存储在 pre 数组中
定义一个数组 toposort
定义一个大小为 n 的数组 onpath 并填充false
定义一个大小为 n 的数组 accessed 并用 false 填充
初始化 i := 0，当 i < n 时，更新(将 i 增加 1)，执行 −
如果 accessed[i] 为 false 且 dfs(graph, i, onpath, accessed, toposort) 为 true，则 −
返回空白数组
反转数组 toposort
返回 toposort
示例
让我们看看下面的实现以便更好地理解 −
#include <bits/stdc++.h>
using namespace std;
vector<unordered_set<int> > create_graph(int n, vector<pair<int, int> >& pre) {
vector<unordered_set<int> > graph(n);
for (auto pre : pre)
graph[pre.second].insert(pre.first);
return graph;
}
bool dfs(vector<unordered_set<int> >& graph, int start,vector<bool>& onpath, vector<bool>& visited, vector<int>& toposort) {
if (visited[start])
return false;
onpath[start] = visited[start] = true;
for (int neigh : graph[start])
if (onpath[neigh] || dfs(graph, neigh, onpath, visited, toposort))
return true;
toposort.push_back(start);
return onpath[start] = false;
}
vector<int> get_order(int n, vector<pair<int, int> > &pre){
vector<unordered_set<int> > graph = create_graph(n, pre);
vector<int> toposort;
vector<bool> onpath(n, false), visited(n, false);
for (int i = 0; i < n; i++)
if (!visited[i] && dfs(graph, i, onpath, visited, toposort))
return {};
reverse(toposort.begin(), toposort.end());
return toposort;
}
int main() {
int n = 4;
vector<pair<int, int> > pre = {{1, 0}, {2, 0}, {3, 2}, {3, 1},{4,0}};
vector<int> v = get_order(n, pre);
for (int i = 0; i < v.size(); i++) {
cout << v[i] << " ";
}
}
输入
4, {{1, 0}, {2, 0}, {3, 2}, {3, 1},{4,0}}
输出
0 1 4 2 3
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/
