Java拓扑排序知识点（含面试大厂题和源码）

拓扑排序是针对有向无环图（DAG）的一种排序算法，它将图中的所有顶点排成一个线性序列，使得对于任何一条有向边 U -> V，顶点 U 都在顶点 V 的前面。拓扑排序是许多算法的前置步骤，如课程规划、工程任务调度、依赖性解析等。

拓扑排序的算法步骤：

计算入度：计算图中所有顶点的入度（指向该顶点的边的数量）。
初始化一个空栈：用于存放排序结果。
遍历所有顶点：
- 从入度为0的顶点开始，将其加入栈中，并将该顶点标记为已访问。
- 从当前顶点出发，遍历其所有邻接点，将每个邻接点的入度减1。如果邻接点的入度变为0，则重复上述步骤。
重复步骤3：直到所有顶点都被访问过。
输出栈中的顶点：栈中的顶点序列即为拓扑排序结果。

拓扑排序的Java实现：

java">import java.util.*;public class TopologicalSort {public List<Integer> topoSort(int V, int[][] edges) {List<Integer> result = new ArrayList<>();int[] inDegree = new int[V];// 初始化入度数组for (int[] edge : edges) {inDegree[edge[1]]++;}// 使用队列存储所有入度为0的顶点Queue<Integer> queue = new LinkedList<>();for (int i = 0; i < V; i++) {if (inDegree[i] == 0) {queue.offer(i);}}while (!queue.isEmpty()) {int current = queue.poll();result.add(current);for (int[] edge : edges) {if (edge[0] == current) {int next = edge[1];inDegree[next]--;if (inDegree[next] == 0) {queue.offer(next);}}}}return result;}public static void main(String[] args) {TopologicalSort topoSort = new TopologicalSort();int V = 6;int[][] edges = {{5, 2},{5, 0},{4, 0},{4, 1},{2, 3},{3, 1}};List<Integer> result = topoSort. topoSort(V, edges);System.out.println("Topological Sort: " + result);}
}

在面试中，拓扑排序是一个重要的知识点，它考察应聘者对图算法的理解和算法实现能力。通过实现拓扑排序，可以展示你对图算法和排序算法的掌握程度。希望这些知识点和示例代码能够帮助你更好地准备面试！拓扑排序是图算法中的一个常见问题，经常出现在大厂的面试中。以下是三道与拓扑排序相关的面试题目，以及相应的Java源码实现。

题目 1：课程安排问题

描述：
给定 n 门课程和一个先决条件列表，每个课程都有一个先决条件，表示必须先修的课程。请为这些课程安排学习顺序。

示例：

输入: n = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
输出: [0, 1, 2, 3] 或 [0, 2, 1, 3]（答案不唯一）

Java 源码：

java">import java.util.ArrayList;
import java.util.List;public class CourseSchedule {public int[] findOrder(int n, int[][] prerequisites) {int[] inDegree = new int[n];List<List<Integer>> graph = new ArrayList<>(n);for (int i = 0; i < n; i++) {graph.add(new ArrayList<>());}for (int[] edge : prerequisites) {graph.get(edge[1]).add(edge[0]);inDegree[edge[0]]++;}List<Integer> zeroInDegree = new ArrayList<>();for (int i = 0; i < n; i++) {if (inDegree[i] == 0) {zeroInDegree.add(i);}}List<Integer> order = new ArrayList<>();while (!zeroInDegree.isEmpty()) {int course = zeroInDegree.remove(0);order.add(course);for (int next : graph.get(course)) {if (--inDegree[next] == 0) {zeroInDegree.add(next);}}}return order.size() == n ? order.stream().mapToInt(i -> i).toArray() : new int[]{};}public static void main(String[] args) {CourseSchedule solution = new CourseSchedule();int n = 4;int[][] prerequisites = {{1, 0}, {2, 0}, {3, 1}, {3, 2}};int[] result = solution.findOrder(n, prerequisites);System.out.println("Course order: " + Arrays.toString(result));}
}

题目 2：项目任务顺序

描述：
给定一个项目，包含多个任务，以及任务之间的依赖关系。每个任务只能等所有依赖它的任务完成后才能开始。请为这些任务安排执行顺序。

示例：

输入: n = 5, edges = [[1,0],[2,0],[3,1],[3,2],[4,0],[4,3],[5, 1],[5, 2],[5, 3],[5, 4]]
输出: [0, 1, 2, 3, 4] 或其他有效的拓扑排序结果

Java 源码：

java">import java.util.*;public class ProjectScheduling {public List<Integer> criticalPath(int n, int[][] edges) {List<List<Integer>> graph = new ArrayList<>();int[] inDegree = new int[n];for (int i = 0; i < n; i++) {graph.add(new ArrayList<>());}for (int[] edge : edges) {graph.get(edge[1]).add(edge[0]);inDegree[edge[0]]++;}Queue<Integer> queue = new LinkedList<>();for (int i = 0; i < n; i++) {if (inDegree[i] == 0) {queue.offer(i);}}List<Integer> order = new ArrayList<>();while (!queue.isEmpty()) {int task = queue.poll();order.add(task);for (int next : graph.get(task)) {if (--inDegree[next] == 0) {queue.offer(next);}}}return order;}public static void main(String[] args) {ProjectScheduling solution = new ProjectScheduling();int n = 5;int[][] edges = {{1, 0}, {2, 0}, {3, 1}, {3, 2}, {4, 0}, {4, 3}, {5, 1}, {5, 2}, {5, 3}, {5, 4}};List<Integer> result = solution.criticalPath(n, edges);System.out.println("Task execution order: " + result);}
}

题目 3：最长无环子序列

描述：
给定一个整数序列，找到一个最长的无环子序列。无环子序列是指子序列中的任意两个数字之间没有拓扑排序关系。

示例：

输入: [2, 6, 4, 1, 5, 3]
输出: 3

Java 源码：

java">import java.util.*;public class LongestAcyclicSubsequence {public int longestUncrossed(int[] arr) {int n = arr.length;int[] dp = new int[n];int[] tails = new int[n];Arrays.fill(tails, -1);dp[0] = 1;for (int i = 1; i < n; i++) {int max = 0;int prev = -1;for (int j = 0; j < i; j++) {if (arr[j] < arr[i]) {if (tails[j] == -1 || tails[j] > prev) {max = Math.max(max, dp[j]);}} else if (arr[j] == arr[i] && tails[j] != -1) {prev = Math.max(prev, dp[j]);}}dp[i] = max + 1;tails[i] = max;}return Arrays.stream(dp).max().getAsInt();}public static void main(String[] args) {LongestAcyclicSubsequence solution = new LongestAcyclicSubsequence();int[] arr = {2, 6, 4, 1, 5, 3};int result = solution.longestUncrossed(arr);System.out.println("Length of longest uncrossed subsequence: " + result);}
}