首页 > 代码库 > 拓扑排序

拓扑排序

排序,顾名思义是进行排序,那么就有一个条件,就是可以排出结果。

比如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 }

 

拓扑排序