写在前面
拓扑排序常用于判断有向图是否有环或者获取满足一定先后顺序的图的遍历结果，其核心思路比较简单，就是DFS(深度优先遍历)或者BFS(广度优先遍历)，遍历过程中主要需要维护一个入度数组即可，详细的算法流程还请自行百度，这里只是贴出一个板子。
代码模板
//拓扑排序
//degree - 入度数组
//items - 需要进行拓扑的点
//graph - 需要拓扑的图
public List<Integer> topoSort(int[] degree, List<List<Integer>> graph, List<Integer> items){
Queue<Integer> queue = new LinkedList<>();
for(Integer item : items){
if(degree[item] == 0){
queue.offer(item);
}
}
List<Integer> res = new ArrayList<>();
while(!queue.isEmpty()){
int u = queue.poll();
res.add(u);
for(int v : graph.get(u)){
degree[v]--;
if(degree[v] == 0){
queue.offer(v);
}
}
}
return res.size() == items.size() ? res : new ArrayList<Integer>();
}
由于通常都是使用degree数组或者graph图的下标表示每一个顶点，此时最后一个参数就不必要了。
PS：相关题目如下
网友评论