⭐ 题目日期：

拼多多 - 2024/10/08

🌳 题目描述：

算法题的题干是英文的，有n个任务，并有若干约束条件，约束条件均为某个任务必须在另一个任务之前执行，输出这n个任务的所有满足约束的执行顺序。

🧗难度系数：

⭐️ ⭐️ ⭐ ⭐

📝思路分析：

这道题是在考察图论里经典算法拓扑排序。

拓扑排序是一种对有向无环图（Directed Acyclic Graph，DAG）进行排序的算法，其结果是一个线性序列，使得对于图中的任意一条有向边 (u, v)，顶点u在序列中总是出现在顶点 v 之前。在任务管理中，如果将项目中的任务看作顶点，任务之间的依赖关系看作有向边，那么拓扑排序可以确定任务的执行顺序，确保依赖关系得到满足。

对图进行深度优先搜索，当访问完一个节点的所有邻接节点后，才将该节点插入链表的头部，确保所有依赖于该节点的节点都已被处理。

🌟 算法

1. 初始化：

   创建图，用 map 来存储有向边，<key, value>, key 为起始点，value 为 node key 的邻接点的集合 set

2. 创建一个访问set，将访问过的节点加入。

3. 创建一个列表 list，用于存储拓扑序列。

4. 递归访问节点：

   对每个未访问的节点 u，调用递归函数 expandNode(u)。

5. 在 expandNode(u) 中：

   • 将 u 标记为已访问。
   • 遍历 u 的所有邻接节点 v：
     • 如果 v 未访问，递归调用 dfs(v)。
   • 将 u 加入 list 的第一个位置，因为越往后加入的节点，依赖性越低。

6. 生成拓扑序列：

7. List 中的顺序为拓扑排序结果，依赖性由低到高排列。

💻代码：

Java

public List<Integer> topologicalOrder(int[][] nums) {
 // 用链表进行存储，在头节点插入
 List<Integer> result = new LinkedList<>();
 if (nums == null || nums.length == 0) {
     return result;
 }

 Map<Integer, Set<Integer>> map = new HashMap<>();
 for (int[] edge : nums) {
     if (!map.containsKey(edge[0])) {
         map.put(edge[0], new HashSet<>());
     }
     map.get(edge[0]).add(edge[1]);
 }

 // 
 Set<Integer> set = new HashSet<>();
 for (int node : map.keySet()) {
     expandNode(node, map, set, result);
 }
 return result;
}

private void expandNode(int node, Map<Integer, Set<Integer>> map, Set<Integer> set, List<Integer> result) {
 if(set.add(node)) {
     // 判断该节点是否作为其他节点的依赖
     if (!map.containsKey(node)) {
         result.add(0, node);
         return;
     }
     for (int neighbor : map.get(node)) {
         expandNode(neighbor, map, set, result);
     }
     result.add(0, node);
 }
}

🚵🏻复杂度分析：

1. 时间复杂度：O(V + E)
2. 空间复杂度：O(V + E)