拓扑排序
目录
OpenJ_Bailian - 4084 拓扑排序（BFS）
有向无环图的拓扑排序是指给所有节点排序，使得所有的有向边都是从序号小的节点指向序号大的。
深度优先搜索和广度优先搜索都可以用于产生拓扑排序。
力扣 210. 课程表 II（DFS）
现在你总共有 n 门课需要选，记为 0 到 n-1。
在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]
给定课程总量以及它们的先决条件，返回你为了学完所有课程所安排的学习顺序。
可能会有多个正确的顺序，你只要返回一种就可以了。如果不可能完成所有课程，返回一个空数组。
示例 1:
输入: 2, [[1,0]]
输出: [0,1]
解释: 总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。
示例 2:
输入: 4, [[1,0],[2,0],[3,1],[3,2]]
输出: [0,1,2,3] or [0,2,1,3]
解释: 总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。
说明:
输入的先决条件是由边缘列表表示的图形，而不是邻接矩阵。详情请参见图的表示法。
你可以假定输入的先决条件中没有重复的边。
提示:
1 <= numCourses <= 2000
0 <= prerequisites.length <= numCourses * (numCourses - 1)
prerequisites[i].length == 2
0 <= ai, bi < numCourses
ai != bi
所有[ai, bi] 互不相同
-
class Solution2 {
-
public:
-
bool canFinish(vector<vector<int>>& diag, int loc) {
-
if (visitt[loc] == 1)return false;
-
if (flag[loc] == 1)return true;
-
visitt[loc] = 1, flag[loc] = 1;
-
for (int i = 0; i < diag[loc].size(); i++)
-
{
-
if (!canFinish(diag, diag[loc][i]))return false;
-
}
-
visitt[loc] = 0;
-
return true;
-
}
-
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
-
vector<int>tmp;
-
vector<vector<int>>diag;
-
for (int i = 0; i < numCourses; i++)
-
{
-
diag.insert(diag.end(), tmp);
-
visitt[i] = 0, flag[i] = 0;
-
}
-
for (int i = 0; i < prerequisites.size(); i++)
-
{
-
diag[prerequisites[i][0]].push_back(prerequisites[i][1]);
-
}
-
for (int i = 0; i < numCourses; i++)
-
{
-
if (flag[i])continue;
-
cout << i;
-
if (!canFinish(diag, i))return false;
-
}
-
return true;
-
}
-
private:
-
map<int, int>visitt;//单次访问标记
-
map<int, int>flag;//所有访问标记
-
};
-
-
class Solution {
-
public:
-
void findOrder(vector<vector<int>>& diag, int loc, vector<int>& ans)
-
{
-
if (outNum[loc] || flag[loc])return;
-
ans.push_back(loc);
-
flag[loc]++;
-
for (int i = 0; i < diag[loc].size(); i++)
-
{
-
outNum[diag[loc][i]]--;
-
findOrder(diag, diag[loc][i], ans);
-
}
-
}
-
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
-
vector<int>tmp;
-
if (!Solution2().canFinish(numCourses, prerequisites))return tmp;
-
vector<vector<int>>diag;
-
for (int i = 0; i < numCourses; i++)
-
{
-
diag.insert(diag.end(), tmp);
-
visitt[i] = 0, outNum[i] = 0, flag[i] = 0;
-
}
-
for (int i = 0; i < prerequisites.size(); i++)
-
{
-
diag[prerequisites[i][1]].push_back(prerequisites[i][0]);
-
outNum[prerequisites[i][0]]++;
-
}
-
vector<int>ans;
-
flag.clear();
-
for (int i = 0; i < numCourses; i++)
-
{
-
findOrder(diag, i, ans);
-
}
-
return ans;
-
}
-
private:
-
map<int, int>visitt;//单次访问标记
-
map<int, int>flag;//所有访问标记
-
map<int, int>inNum;//入度
-
map<int, int>outNum;//出度
-
};
OpenJ_Bailian - 4084 拓扑排序（BFS）
给出一个图的结构，输出其拓扑排序序列，要求在同等条件下，编号小的顶点在前。
Input
若干行整数，第一行有2个数，分别为顶点数v和弧数a，接下来有a行，每一行有2个数，分别是该条弧所关联的两个顶点编号。
v<=100, a<=500
Output
若干个空格隔开的顶点构成的序列(用小写字母)。
Sample
| Inputcopy | Outputcopy |
|---|---|
6 8 1 2 1 3 1 4 3 2 3 5 4 5 6 4 6 5 |
v1 v3 v2 v6 v4 v5 |
注意这题输出的顺序，要输出所有拓扑排序的最小字典序的那个。
-
#include <iostream>
-
#include <string>
-
#include <vector>
-
#include <string.h>
-
#include <map>
-
#include <queue>
-
using namespace std;
-
-
-
//输入有向边集{{1，2}{1，3}{2，3}}，输出邻接表{1:{2,3},2:{3}}
-
map<int, vector<int>> edgeToAdjaList(const vector<vector<int>>& v)
-
{
-
map<int, vector<int>> ans;
-
for (auto &vi : v) {
-
ans[vi[0]].push_back(vi[1]);
-
}
-
return ans;
-
}
-
//拓扑排序 BFS版
-
//输入n=3，v={{0,1}{0,2}{1,2}}, 输出{0,1,2}，有环则输出为空
-
vector<int> TopoSort(int n, const vector<vector<int>>&v)
-
{
-
priority_queue<int, vector<int>, greater<int>> q;
-
map<int, int>m;
-
for (auto vi : v)m[vi[1]]++;
-
for (int i = 0; i < n; i++)if(m[i]==0)q.push(i);
-
vector<int>ans;
-
auto mv = edgeToAdjaList(v);
-
while (!q.empty()) {
-
int k = q.top();
-
q.pop();
-
ans.push_back(k);
-
for (auto i : mv[k]) {
-
m[i]--;
-
if (m[i] == 0)q.push(i);
-
}
-
}
-
return ans.size() == n ? ans : vector<int>{};
-
}
-
-
int main()
-
{
-
//freopen("D:/in.txt", "r",stdin);
-
int v, a, x, y;
-
cin >> v >> a;
-
vector<vector<int>> p;
-
while (a--) {
-
cin >> x >> y;
-
p.push_back(vector<int>{x-1, y-1});
-
}
-
auto ans = TopoSort(v, p);
-
for (int i = 0; i < ans.size(); i++)cout << "v" << ans[i]+1 << " ";
-
cout << endl;
-
return 0;
-
}
文章来源: blog.csdn.net，作者：csuzhucong，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/nameofcsdn/article/details/126678850
- 点赞
- 收藏
- 关注作者
评论（0）