首页 > 代码库 > 拓扑排序

拓扑排序

2024-10-28 14:08:39   210人阅读

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

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

 

拓扑排序


联系
我们