徐州市建设局招投标网站,php做网站示例,网络推广网络营销,男的做直播网站前言
拓扑排序是非常重要的一部分#xff0c;希望大家都能够手撕代码#xff01;#xff01;#xff01;#xff08;嘿嘿嘿#xff09; 一、拓扑排序定义#xff08;百度须知嘿嘿嘿#xff09;
拓扑排序 拓扑排序是一种对有向无环图#xff08;Directed Acyclic Gra… 前言
拓扑排序是非常重要的一部分希望大家都能够手撕代码嘿嘿嘿 一、拓扑排序定义百度须知嘿嘿嘿
拓扑排序 拓扑排序是一种对有向无环图Directed Acyclic Graph简称DAG进行的排序过程目的是将图中所有的顶点按照发生事件的顺序排成一条线性序列。这种排序确保了图中任意两个相邻顶点之间至少有一条边相连且在这条边的方向上这条边的终点在前于起点。拓扑排序的一个关键特性是它只包含在一个顶点在其事件序列中出现的次数这意味着每个顶点只会出现一次。
要执行拓扑排序可以从DAG图的任一顶点开始选择出度为0的顶点作为“根”并将它们放入队列。然后从队列中取出顶点将其事件序列中的下一个顶点加入队列同时移除与该顶点相关的所有边。这个过程会一直持续直到队列为空或者到达了一个没有前驱顶点的状态此时就得到了该DAG的拓扑排序。
在实际应用中拓扑排序可以用于确定哪些活动可以在给定的顺序下并发执行因为只有那些在特定顺序下没有依赖关系的活动才能一起运行。例如在AOV网中如果没有回路所有活动都可以按照拓扑序列排列从而形成一个线性序列使得每个活动的所有前驱活动都在其前面。1
总结来说拓扑排序是一种用于确定有向无环图中顶点顺序的方法确保每个顶点只出现一次并且遵循特定的事件发生顺序。这种方法对于分析并发执行的活动顺序非常有用。
二、例题
1.有向图的拓扑排序 2.AC代码
//图的拓扑序列只针对有向图
//有向无环图被称为拓扑图
//一个点的入度是指有多少条边是指向自己
//一个点有几条边出去就是这个点的出度
//一个有向无环图一定至少存在一个入度为0的点
#include iostream
#include cstring
#include algorithm
using namespace std;
const int N 100010;
int n, m;
int h[N], e[N], ne[N], idx;
int q[N], d[N];
//q是宽搜队列,d是这个点的入度void add(int a, int b) {//邻接表e[idx] b;ne[idx] h[a];h[a] idx;
}bool topsort() {int hh 0, tt -1;for (int i 1; i n; i)if (!d[i]) //如果这个点存在入度q[tt] i;//就把这个点加到队列里while (hh tt) {int t q[hh];//取出队头元素for (int i h[t]; i ! -1; i ne[i]) {//拓展队头元素int j e[i];//找到出边d[j]--;//删掉入边if (d[j] 0) //如果这个点的入度全部被删掉了q[tt] j;//就让这个点入队}}//判断所有点是否已经全部入队return tt n - 1; //返回队列里元素的数量是否等于n-1
}int main() {cin n m;memset(h, -1, sizeof h);for (int i 0; i m; i) {int a, b;cin a b;add(a, b); //插入一条a-b的有向边d[b];//b的入度加一}if (topsort()) {//如果存在拓扑序for (int i 0; i n; i)printf(%d , q[i]);puts();} else {puts(-1);}return 0;
} 总结
拓扑排序可能会经常用到希望大家能够完全掌握
