拓扑排序
排序 拓扑
2023-06-13 09:14:15 时间
有向无环图可以用来表示各种事物的顺序,比如工作顺序。一些事情必须在另一些事情完成之后才能开始进行。那么,为了获得正确的工作顺序(一件事情开始之前,必须保证它的前置条件全部满足),就需要用到拓扑排序。
拓扑排序其实就是在有向无环图中,只要存在边(u,v),那就让u排在v前面。
我们可以通过广度优先搜索或者深度优先搜索来实现拓扑排序。
广度优先的思路就是对每个入度为0的且未被访问过的节点进行广度优先搜索。
在搜索过程中,只要搜索了u与v之间的边,那就将v的入度减1,相当于删除边的操作。入度为零就代表着它的前置条件已经完全满足。一个节点只有当其入度为0且未被访问过,才对其进行广度优先搜索。
下面是通过bfs拓扑排序的伪代码
利用DFS进行拓扑排序的思路相对简单,就是循环以当前仍未搜索的节点为起点,进行dfs,然后逆序把节点id存入列表中。但是,对于大规模的图来说,深度优先搜索很容易栈溢出,并且由于递归调用有开销,所以,采用BFS会更好。
对于题目 GRL_4_B ,采用BFS的AC代码如下
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define MAXV 10005
vector<int> vec[MAXV];
vector<int> ans;
int v, e;
int indeg[MAXV] = {0};
bool vis[MAXV] = {false};
void bfs(int u)
{
queue<int>q;
vis[u] = true;
q.push(u);
while(!q.empty())
{
int t = q.front();
q.pop();
ans.push_back(t);
for(int x:vec[t])
{
indeg[x]--;
if(indeg[x]==0&&vis[x]==false)
{
q.push(x);
vis[x] = true;
}
}
}
}
void solve()
{
for (int i = 0; i < v; ++i)
{
if (indeg[i] == 0 && vis[i] == false)
{
bfs(i);
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> v >> e;
int s, t;
for (int i = 0; i < e; ++i)
{
cin >> s >> t;
vec[s].push_back(t);
indeg[t]++;
}
solve();
for(int x:ans)
{
cout<<x<<endl;
}
}
相关文章
- Python 一网打尽<排序算法>之堆排序算法中的树
- Java—Sort排序
- MATLAB中排序函数sort()的用法
- 两次登顶常识推理问答榜单ProtoQA,哈工大深圳创新掩码模型重排序策略
- 数据结构实验之排序二:交换排序 (SDUT 3399)
- mysql数值字符串类型的按照数值进行排序详解数据库
- Linux 中按日期排序文件的方法(linux文件日期排序)
- MySQL查询优化技巧:使用先排序再分组策略(mysql先排序在分组)
- MySQL中ASC排序的详解(mysql 中asc)
- MySQL关联查询排序技巧分享(mysql两表关联排序)
- 在Oracle中用递归函数实现的有效拓扑排序(oracle中递归函数)
- Oracle中展现交叉排序的精彩瞬间(oracle 交叉排序)
- c语言合并两个已排序数组的示例(c语言数组排序)
- VC++实现选择排序算法简单示例