拓扑排序
转载自：https://blog.csdn.net/y_universe/article/details/79342940
拓扑排序
1、定义
对一个有向无环图(Directed Acyclic Graph简称DAG) G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。
在AOV网中，若不存在回路，则所有活动可排列成一个线性序列，使得每个活动的所有前驱活动都排在该活动的前面，我们把此序列叫做拓扑序列(Topological order)，由AOV网构造拓扑序列的过程叫做拓扑排序(Topological sort)。AOV网的拓扑序列不是唯一的，满足上述定义的任一线性序列都称作它的拓扑序列。
2、拓扑排序的实现步骤
- 在有向图中选一个没有前驱的顶点并且输出
- 从图中删除该顶点和所有以它为尾的弧（白话就是：删除所有和它有关的边）
- 重复上述两步，直至所有顶点输出，或者当前图中不存在无前驱的顶点为止，后者代表我们的有向图是有环的，因此，也可以通过拓扑排序来判断一个图是否有环。
3、拓扑排序示例手动实现
如果我们有如下的一个有向无环图，我们需要对这个图的顶点进行拓扑排序，过程如下：
首先，我们发现V6和v1是没有前驱的，所以我们就随机选去一个输出，我们先输出V6，删除和V6有关的边，得到如下图结果：
然后，我们继续寻找没有前驱的顶点，发现V1没有前驱，所以输出V1，删除和V1有关的边，得到下图的结果：
然后，我们又发现V4和V3都是没有前驱的，那么我们就随机选取一个顶点输出（具体看你实现的算法和图存储结构），我们输出V4，得到如下图结果：
然后，我们输出没有前驱的顶点V3，得到如下结果：
然后，我们分别输出V5和V2，最后全部顶点输出完成，该图的一个拓扑序列为：
v6–>v1—->v4—>v3—>v5—>v2
过程简述：
- 从 DAG 图中选择一个 没有前驱（即入度为0）的顶点并输出。
- 从图中删除该顶点和所有以它为起点的有向边。
- 重复 1 和 2 直到当前的 DAG 图为空或当前图中不存在无前驱的顶点为止。若当前图中不存在无前驱的顶点说明有向图中必存在环。
基本操作函数
topological_sort(n)：对含有n个顶点的图进行拓扑排序并输出。
代码模板(含详细注释)
这里用http://acm.hdu.edu.cn/showproblem.php?pid=1285作为模板题
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define V 510 //最大顶点数
int G[V][V]; //图
int degree[V]; //记录各顶点的入度
void topological_sort(int n) //拓扑排序函数
{
int i, j, k;
for(i = 1; i <= n; i++){
for(j = 1; j <= n; j++){
if(degree[j] == 0){ //找到入度为0的顶点
printf("%d", j); //输出
degree[j]--; //将其入度减为-1
k = j; //用k记录此顶点
break;
}
}
for(j = 1; j <= n; j++){
if(G[k][j] == 1){ //找到被此顶点打败过的顶点
G[k][j] = 0; //标记
degree[j]--; //将找到的顶点的入度减一
}
}
if(i != n)
printf(" ");
else
printf("\n");
}
}
int main(void)
{
int n; //队伍的个数
int m; //每组数据后接的输入行数
while(scanf("%d%d", &n, &m) != EOF){
memset(G, 0, sizeof(G)); //图的初始化
memset(degree, 0, sizeof(degree)); //顶点入度的初始化
while(m--){
int u, v;
scanf("%d%d", &u, &v); //u打败了v
if(G[u][v] == 0){
/*去重
这里要记录的是v被多少人打败过，
而不是被打败了多少次
*/
G[u][v] = 1; //u打败过v
degree[v]++; //顶点v的入度加一
}
}
topological_sort(n); //调用拓扑排序函数
}
return 0;
}
文章最后发布于: 2018-09-25 20:18:53
相关阅读
订阅号信息总算能够兴趣爱好推荐了?前不久，有网民发觉，订阅号消息列表的排序并不是依照时间轴展现，只是打乱了，乃至能够见到前一
关键字是SEO关键字优化排序的核心。在选择了关键字后，可以确定优化的方向。无论网站的关键是文本布局还是长尾关键字挖掘，我们
带你了解Excel的发展历史在Excel中如何快速计算 现在我们最常用的电子表格系统OfficeExcel已经成为企业或个人最常用的
一、基本概念 1.二叉排序树 二叉排序树（Binary sort tree，BST），又称为二叉查找树，或者是一棵空树；或者是具有下列性质的二叉树： (1)若
常见十大(内部)排序算法 - Sorting Algorithms C++
基本概念 内部和外部排序 内部排序在这里指的是只用到了电脑内存而不使用外存的排序方式。相对的，外部排序就是同时动用了电脑内
