目录
1. 有向无环图
顾名思义，边有向，图中没有回路。这里只需要知道各顶点的入度和出度怎么计算即可。
2. AOV网：顶点活动图
在有向无环图中，用顶点来表示一个活动，用边来表示活动的先后顺序的图结构。
拓扑排序与 AOV 网络之间存在密切的关系，因为 AOV 网络通常用于描述项目中的活动之间的依赖关系，而拓扑排序则可以用来确定这些活动的执行顺序。
3. 拓扑排序
概念：抽象，略。
找到做事情的先后顺序，拓扑排序的结果可能不是唯一的.
模拟一遍拓扑排序就明白了：
在这个有向无环图中，统计了各个顶点的入度和出度。
拓扑排序是找到做事情的先后顺序，也就是说，在做1这件事之前，我必须先把0这件事做完了才行。而入度为0的顶点就是拓朴排序的起点，如果有多个入度为0的顶点，拓扑排序的结果就不一样了。
因此，拓扑排序分为以下几个步骤：
- 找出入度为0的点，然后输出。
- 删除与该点连接的边，即这些边指向的顶点的入度-1。
- 重复1，2操作，直到图中没有点或者没有入度为0的点为止。
重要应用，判断有向图中是否有环。
例如：
该图中右侧三个顶点（3，4，5）构成了环。根据上面步骤进行拓扑排序，发现当1，2顶点依次处理完后，剩下顶点之间的关系是这样的：
此时，图中没有入度为1的顶点了，而已处理的顶点数未达到图中顶点的个数，因此就可以判断出该图是有环的。
4. 实现拓扑排序
借助队列，来一次BFS即可。
1.初始化：把所有入度为0的顶点加入到队列中。
2.当队列不为空时：
（1）拿出队头元素，加入到最终结果中。
（2）删除与该元素相连的边。
（3）判断：删除边指向的顶点，此时入度是否为0，如果为0，加入到队列中。
5. 力扣OJ
不看题目的示例，直接看前面那个图：
根据题目要求，它让我们判断是否可能完成所有课程的学习，其实就是看我们在拓扑排序的过程中能否处理完所有顶点，也就是判断这个有向图中是否有环。对此，我们首要任务其实是建图。
二维数组中每个元素 prerequisites[i]就表示prerequisites[1]指向prerequisites[0]，即通过给出的prerequisites数组要转换成图示中的图，实现图有两种方式，这里我们使用邻接表实现（稀疏图）。对于建图，我们要灵活使用语言提供的容器。
模拟一个邻接表也有两种方式：
- List<List<Integer>>：本题中，课程映射成了数字（整型）的形式，因此我们可以用一个大的List表示图中的顶点数，小的List存储这个顶点的邻接顶点。
- Map<Integer, List<Integer>>：这种方式同样可以创建邻接表，但它的通用性更强。原因就是当课程是以字符串的形式表示的，如数学，语文，英语等，此时我们如果用第一种方式建表就需要先把课程和数字（整型）的对应关系确定下来。而第二种方式直接将泛型更改为String类型，即Map<String, List<String>>即可直接建表。
除建表外，还需要一个入度表，用于后续BFS的过程中将入度变为0的顶点入队。结合上述拓扑排序的实现步骤，代码实现如下（具体步骤看注释）：
class Solution {
public boolean canFinish(int n, int[][] p) {
//1.准备工作，建图
Map<Integer, List<Integer>> edges = new HashMap<>();
int[] in = new int[n]; //入度表
//遍历二维数组
for (int[] ints : p) {
//以p[1]为键，p[0]为值的元素建表
if (!edges.containsKey(ints[1])) {
edges.put(ints[1], new ArrayList<>());
}
edges.get(ints[1]).add(ints[0]);
in[ints[0]]++; //p[0]的入度加1
}
//2.进行拓扑排序
//2.1 遍历入度表，将所有入度为0的顶点入队
Queue<Integer> queue = new LinkedList<>();
for(int i = 0; i < n; i++) {
if(in[i] == 0) {
queue.offer(i);
}
}
//2.2 bfs
int count = 0;//记录能够完成几门课程
while(!queue.isEmpty()) {
int edge = queue.poll();
count++;
//遍历该顶点的邻接顶点(先要保证该顶点有邻接顶点)，将它们的入度-1
if (edges.containsKey(edge)) {
for (int inIdx : edges.get(edge)) {
in[inIdx]--;
if (in[inIdx] == 0) {
queue.offer(inIdx);
}
}
}
}
//或者判断入度表是否有不为0的顶点，有则返回false，否则为true
return count == n;
}
}接下来可尝试解决另外两道题：
标签：int,拓扑,入度,轻松,ints,顶点,排序 From： https://blog.csdn.net/sjsjzhx/article/details/137158461