拓扑排序(Topological Sorting)是一种针对有向无环图(DAG)的排序算法。在拓扑排序中,图中的顶点被安排成一个线性序列,使得如果图中存在一条从顶点 u 到顶点 v 的有向边,则在序列中顶点 u 出现在顶点 v 之前。
拓扑排序通常用于描述一组任务或事件之间的依赖关系,其中每个任务都有一些前置任务,必须在它们完成后才能执行。通过拓扑排序,我们可以确定一种合理的执行顺序,以确保所有任务都按照其依赖关系得到正确执行。
在实现上,拓扑排序可以根据下面的步骤实现:
- 找到入度为 0 的顶点,把这些节点加入到排序结果中,这些节点没有前置任务
- 将已经加入到排序结果中的节点及其相连的边删去,更改图中其他节点的入度
- 重复 1,2 步,直到图中没有入度为 0 的节点
如果被拓扑排序的图是一个有向无环图,那么所有顶点都会被排序;而如果图中有环,则拓扑排序只会得到一部分的节点序列。
因此,拓扑排序也常被用来检测一个图中是否有环。
下面是拓扑排序入门的一个经典案例及其代码实现( 2024春招字节跳动暑期实习一面代码题 ):
题目描述: 一共有 n 门课你可以选,从课程0,1到课程 n-1 。 有一个数组 p , p[i] = [a, b] 表示你必须要先修完课程 b 才可以修课程 a 。 请写一个方程返回 true / false 表示你是否能修完所有的课程。
package com.ymiir;
import java.util.*;
public class Main {
public static boolean topologicalSorting(int n, int[][] graph){ int[] inDegree = new int[n]; Map<Integer, List<Integer>> map = new HashMap<>(); for(int i=0;i<n;i++){ inDegree[i] = 0; } for(int i=0;i<graph.length;i++){ int node = graph[i][0]; int pre = graph[i][1]; inDegree[node]++; map.computeIfAbsent(pre, k->new ArrayList<>()).add(node); } Queue<Integer> queue = new ArrayDeque<>(); for(int i=0;i<n;i++){ if(inDegree[i]==0){ queue.offer(i); } }
int count = 0; while(!queue.isEmpty()){ int temp = queue.poll(); count++; if(map.containsKey(temp)){ for(int v : map.get(temp)){ inDegree[v]--; if(inDegree[v]==0){ queue.add(v); } } } } return count==n; }
public static void main(String[] args) { int[][] graph = ; boolean flag = topologicalSorting(4,graph); System.out.println(flag); } }
|