首页 > 代码库 > 拓扑排序
拓扑排序
排序,顾名思义是进行排序,那么就有一个条件,就是可以排出结果。
比如A克B,B克C,C克A,,让你从A,B,C中选择出一个最牛逼的人,,那么这题就没有答案。
所以,条件就是不能出现环状。(即充要条件就是:有向无环图(Directed Acyclic Graph 简称DAG))
比如,现在有一个兵乓球比赛,每两个人进行对战(不考虑出现平局),出现如下结果:
现在让你把他们进行排序,那么我们可以先把结果化成一个DAG。
具体的实现步骤:
1.找到没有被箭头指的(即 入度为0),记录这个值。
2.将所有跟该值有关的箭头全部抹去(即 删去以他为起始的箭头)
重复这两个步骤,直至排出结果。
首先找到A
第二步:
第三步:
就剩最后一个D了,所以最终的排序为
算法实现:
1 #include <cstdio> 2 #include <cstring> 3 #include <cstdlib> 4 #include <algorithm> 5 #define MAX 100 6 using namespace std; 7 8 int map[MAX][MAX]; //邻接矩阵 9 int index[MAX]; //记录入度 10 int n; //有关的边数(箭头的数量) 11 int m; //节点数(运动员的个数) 12 int ranking[MAX]; //最终的排名 13 14 void toposort() 15 { 16 int i, j, k ,t; 17 t = 0; 18 for (i = 0; i < m; i++) //遍历m次即可 19 { 20 for (j = 0; j < m; j++) //找出入度为0的节点 21 { 22 if (index[j] == 0) 23 { 24 index[j]--; 25 ranking[t++] = j; //记录下这个节点 26 27 for (k = 0; k < m; k++) //删除所有与该节点相关联的边 28 { 29 if (map[j][k] == 1) 30 { 31 index[k]--; 32 } 33 } 34 break; 35 } 36 } 37 } 38 } 39 40 int main() 41 { 42 memset(map, 0, sizeof(map)); 43 memset(index, 0, sizeof(index)); 44 45 scanf("%d %d", &n, &m); 46 for (int i = 0; i < n; i++) 47 { 48 int x, y; 49 scanf("%d %d", &x, &y); 50 if (!map[x][y]) //防止有重复的项 51 { 52 map[x][y] = 1; 53 index[y]++; 54 } 55 } 56 57 toposort(); 58 59 for (int i = 0; i < m; i++) 60 { 61 printf("%d ", ranking[i]); 62 } 63 //注意存储时是从0开始存的,所以,答案是:0,1,2,3 64 //(A:1 B:2 C:3 D:4) 65 system("pause"); 66 return 0; 67 }
拓扑排序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。