手机网站怎么提高关键词,wordpress导航网,金湖网页设计多少钱,淄博北京网站建设目录
介绍#xff1a;
实现原理#xff1a;
简答来说#xff1a;
例子
模板#xff08;C#xff09; 介绍#xff1a; 拓扑排序#xff08;Topological Sorting#xff09;是一种针对有向无环图#xff08;DAG#xff09;的节点进行排序的算法。DAG是一个图
实现原理
简答来说
例子
模板C 介绍 拓扑排序Topological Sorting是一种针对有向无环图DAG的节点进行排序的算法。DAG是一个图其中所有边都是有向的并且不存在任何环路即没有循环。拓扑排序可以将这种图中的节点线性排序使得所有的有向边从排在前面的节点指向排在后面的节点。
实现原理 找到入度为0的节点入度是指有向图中指向某个节点的边的数量。在开始排序之前首先找到所有入度为0的节点。这些节点是图中没有其他节点指向它们的节点因此它们可以作为排序的起点。 从图中删除入度为0的节点将入度为0的节点从图中删除并将与这些节点相连的边去掉即将这些相连节点的入度减1。 重复上述步骤重复执行步骤1和步骤2直到所有节点都被删除。每次找到入度为0的节点并删除它们直到没有节点剩余为止。 排序结果排序完成后被删除的节点按照删除的顺序从头到尾组成了一个拓扑排序序列。 拓扑排序的结果不是唯一的因为可能存在多个入度为0的节点。在实际应用中如果图中存在环路非DAG则无法进行拓扑排序因为无法满足拓扑排序的条件。
简答来说 其实就是简单的bfs但是拓扑排序中每次都要以入度为0的结点开始bfs所以相较于普通的bfs多了一个记录每个结点入度的d[N]数组然后每次将删除边后读入为0的结点入队。 入队的结点顺序就是拓扑排序的结果我们用top[N]数组来记录。若最后入队过的结点小于总结点数说明有环返回false可以判断此图是否可以拓扑排序。
例子 模板C
#includeiostream
#includequeue
#includecstring
using namespace std;const int N 100010;
int h[N], e[N], ne[N], idx; // 邻接表
int d[N], top[N]; // 每个节点入度排序结果
int cnt 0; // 记录top数组末尾位置
int n, m; // 结点个数边数// 邻接表连边方法
void add(int a, int b)
{e[idx] b; ne[idx] h[a]; h[a] idx;
}// 拓扑排序
bool topsort()
{queueint q; // 队列for (int i 1; i n; i)if (d[i] 0) q.push(i); // 入度为 0的入队while(q.size()){int t q.front();top[cnt] t; // 记录入队顺序q.pop();// bfsfor (int i h[t]; ~i; i ne[i]){int j e[i];d[j]--; // 此节点入度减一if(d[j] 0) q.push(j); // 若入度减为0入队}}if (cnt n) return 0; // 入队的结点小于总结点数else return 1;}int main()
{cin n m;memset(h, -1, sizeof h); // 初始化表头// 建图while(m--){int x, y; cin x y;add(x, y);d[y] ; // 入度}if (topsort() 0) cout -1; // 若不能排序输出-1else{for (int i 0; i n; i) cout top[i] ; // 输出排序结果}return 0;
}
