作为反向后 DFS 的拓扑排序 |课程安排 II LeetCode

Question

目前正在 LeetCode 上解决课程表 II，这是由于以下行而未通过所有测试用例的代码：

Collections.reverse(postOrder);

。删除这一行可以解决所有测试用例。

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        HashMap<Integer, ArrayList<Integer>> graph = new HashMap<>();

        for (int[] pre: prerequisites) {
            graph.put(pre[0], new ArrayList<>());
        }
        
        for (int[] pre: prerequisites) {
            graph.get(pre[0]).add(pre[1]);
        }

        boolean visited[] = new boolean[numCourses];
        boolean visiting[] = new boolean[numCourses];

        ArrayList<Integer> postOrder = new ArrayList<Integer>();

        for (int i = 0; i < numCourses; i++) {
            if (!visited[i]) {
                if (!dfs(i, visited, visiting, postOrder, graph)) {
                    return new int[0];
                }
            }
        }
        Collections.reverse(postOrder);
        return postOrder.stream().mapToInt(i -> i).toArray();

    }

    private boolean dfs(Integer v, boolean[] visited, boolean[] visiting, ArrayList<Integer> postOrder, HashMap<Integer, ArrayList<Integer>> graph) {
        visiting[v] = true;

        if (graph.get(v) != null) {
            for (Integer neighbor : graph.get(v)) {
                if(visiting[neighbor]) {
                    return false;
                }
                
                if (!visited[neighbor]) {
                    if (!dfs(neighbor, visited, visiting, postOrder, graph)) {
                        return false;
                    }
                }
            }
        }
        

        visiting[v] = false;
        visited[v] = true;
        
        postOrder.add(v);
        System.out.println(v);
        return true;
    }
}

我了解到后序 DFS 的反转会产生有效的拓扑排序。然而，当我反转我的 DFS 订单后列表时，我得到了错误的答案。我通过了所有测试用例，没有逆转。有谁知道为什么会这样？我很感激任何见解。

这是重现错误答案的 main() 代码：

import java.util.ArrayList;
import java.util.HashMap;

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();

        // Test case 1
        int numCourses1 = 3;
        int[][] prerequisites1 = {{1, 0}};
        int[] result1 = solution.findOrder(numCourses1, prerequisites1);
        printResult(result1);

        // Test case 2
        int numCourses2 = 3;
        int[][] prerequisites2 = {{0, 1}, {1, 2}, {2, 0}};
        int[] result2 = solution.findOrder(numCourses2, prerequisites2);
        printResult(result2);
    }

    private static void printResult(int[] result) {
        if (result.length == 0) {
            System.out.println("No valid course order.");
        } else {
            for (int course : result) {
                System.out.print(course + " ");
            }
            System.out.println();
        }
    }
}

作为测试用例 2 的结果，我的代码给出的答案与实际答案相反。

Answer 1

我了解到后序 DFS 的反转会产生有效的拓扑排序。

如果您颠倒后订单顺序，那么您将获得预订单。例如，如果您有这个（依赖）树，其中

a

需要

b

、

e

和

f

，...等：

         a
       / | \
      b  e  f
     / \   /|\
    c   d g h i

那么后序顺序为：

c d b e g h i f a

反转：

a f i h g e b d c

这意味着您现在将从根开始，并以相反（即错误）的顺序访问依赖项：

a

不应该是输出中的第一个，因为它依赖于其他几个节点。

您可能听说过可以使用后序序列，其中以相反的顺序访问节点的子节点。例如：

i h g f e d c b a

这会很好用。