先发个颠

　　最近各种不好的事接踵而至，导致情绪波动很大，什么事情都专心不了，导致学业和算法上的学习都荒废了将近一周（要考试周了），还差点和班上同学吵架（已经和好了）。在休整了一段时间后，我幡然醒悟，因此，从这篇blog开始，我要重新拾起学业以及算法学习了（写完这篇就去复习大物，后天考。明天的六级应该是过不了了）。

前言

　　前一个月一直在学习图论的相关知识，因此我决定在后面一段时间内慢慢介绍各种图论算法来巩固自己的图论知识（费曼学习法）。如果这些文章有幸能够帮助到你，我会很高兴的。

拓扑排序

介绍

　　拓扑排序是一种对有向无环图（DAG）进行排序的算法。在拓扑排序中，图中的节点表示任务或事件，有向边表示任务间的依赖关系。拓扑排序的目标是找到一种排序方式，使得所有任务都能按照依赖关系的顺序被执行。

　　拓扑排序是充要条件是有向无环图（DAG），因此我们还可以使用拓扑排序来判断图是否存在环路。

具体过程

　　拓扑排序需要运用到点的入度和出度的概念。入度即为以该点作为终点的边的数量，出度即为以该点作为起始点的边的数量。当入度点为0时，即不存在以该点为终点的边，因此这个点就是起始点（注意，一张图可能同时存在多个起点和终点），枚举以这个点为起点的边，将各边终点的点的入度减一，若入度减为0，则说明不再存在以该点为终点的边，再按照刚才的方法枚举以这个点为起点的边，直到所有点的入度都为0。(若未枚举完图中所有点，则说明该图存在环路)。

如图所示，1到6每个点都有若干条有向边，每存在一条以 i 为终点的边，i 的入度就加一； 每存在一条以 i 为起点的边， i 的出度就加一。该图中点 1 与点 4 的入度均为 0，即这两个点都为起点，然后依次枚举以他们为起点的边，边的终点的入度减一， 此时发现点 2和点 3 的入度为0， 则再依次枚举以点 2 和点 3 为起点的边，直到最后枚举完所有点，按照这种方法得到的枚举顺序为1 4 2 3 5 6。

实现方法

 1 //存图
 2 vector<int> a[N];
 3 //入度
 4 int idn[N];
 5 //出度
 6 int out[N];
 7 vector<int> ans;
 8 void solve() {
 9     int n, m;
10     cin>>n>>m;
11     for (int i = 1; i <= m; i++) {
12         int u, v;
13         cin>>u>>v;
14         a[u].push_back(v);
15         idn[v]++;
16         out[u]++;
17     }
18     //将入度为0的点存入队列
19     queue<int> q;
20     for (int i = 1; i <= n; i++) {
21         if (idn[i] == 0) {
22             q.push(i);
23             ans.push_back(i);
24         }
25     }
26     while(!q.empty()) {
27         int u = q.front();
28         q.pop();
29         for (int i = 0; i < a[u].size(); i++) {
30             int v = a[u][i];
31             idn[v]--;
32             //入度减为零则将该点入队
33             if (idn[v] == 0) {
34                 q.push(v);
35                 ans.push_back(v);
36             }
37         }
38     }
39     //如果没有枚举完所有点，则说明存在环路
40     if (ans.size() != n) {
41         cout<<"存在环路";
42     } else {
43         for (int i = 0; i < ans.size(); i++) {
44             cout<<ans[i]<<" ";
45         }
46     }
47 }

总结

　　拓扑排序的关键点是入度的概念。入度表示一个节点被其他节点所依赖的次数。在拓扑排序中，入度为0的节点表示没有任何依赖，可以作为排序的起点。通过不断删除入度为0的节点，并更新剩余节点的入度，最终可以得到一个拓扑有序的节点列表。

　　需要注意的是，拓扑排序只适用于有向无环图，如果图中存在环路，则无法进行拓扑排序。因为环路表示存在循环依赖，无法确定任务的执行顺序。因此，在使用拓扑排序之前，需要先判断图是否是有向无环图。（如果是判断是否存在环路，可以直接使用拓扑排序进行判断）