拓扑排序的BFS与DFS实现

以Leetcode 210. 课程表 II 为例题大致讲解一下两种搜索算法的思路。

广度优先搜索,实际上就要结合入度表来进行拓扑排序,入度表需要遍历整张图来计算得到。

之后需要维护一个队列,队列中入度为0的节点,当这个节点出队的时候就要将这个点所指向的所有节点的入度都减1,如果某个指向的节点入度为0了,则将它加入队列中。

可以用计数器记录出队的节点数目,用来最终判断是不是可拓扑排序的,如果是可拓扑排序的,按照出队的顺序也可以构成拓扑序列。

DFS广度优先搜索来处理拓扑排序不是特别好理解。首先说说如何用DFS判断是否可以进行拓扑排序。如果有向图中存在环,则无法拓扑排序。关键是如何判定存在环,那么使用dfs需要维护节点的三种状态,一种是未访问,一种是正在访问,一种是访问结束。

如果访问结束的话,就可以将这个节点,加入到结果中,由于最先访问结束的节点肯定是最后的,所以要用一个栈的数据结构来维护拓扑排序序列。如果当前访问的节点存在某个邻接节点处于正在被访问的一个状态,那么就可以说明存在环。具体的实现过程可以用DFS函数的返回值来巧妙的构造不同情况的判别。

        public int[] findOrder(int numCourses, int[][] prerequisites) {
        //构建邻接表、状态数组( 0:未访问 1:正在访问 2:访问结束)和存储拓扑序列的栈
        HashMap<Integer, ArrayList<Integer>> hm = new HashMap<> (numCourses);
        Deque <Integer> stack = new LinkedList<Integer> ();
        int [] visited = new int[numCourses];
        for (int i = 0; i < numCourses; i++) hm.put(i, new ArrayList<Integer> ());
        for (int[] prerequsity : prerequisites) {
            int to = prerequsity[0];
            int from = prerequsity[1];
            hm.get(from).add(to);
        }

        //DFS过程,DFS返回值是false说明存在环,全部为true的话,结果都存在stack里面
        for(int i = 0; i < numCourses; i++) {
            if (visited[i] == 0) {
                if (!dfs(hm, visited, stack, i)) return new int[0];
            }
        }
        //从栈中取出数据,为了省点空间直接塞到状态数据里面了
        int i = 0;
        while(stack.size() != 0){
            visited[i++] = stack.pollLast();
        }
        return visited;
    }

    public boolean dfs(HashMap<Integer, ArrayList<Integer>> hm, int [] visited, Deque<Integer> stack, int i) {
        //能进入这个函数的肯定是0状态(未访问)的节点,首先更新到1状态(正在访问)
        visited[i] = 1;
        for (int adj : hm.get(i)) {
            //邻接节点处于1状态则说明存在环
            if (visited[adj] == 1) return false;
            //邻接节点未访问,但是从该邻接节点开始的DFS搜索检测到环
            if (visited[adj] == 0 && !dfs(hm, visited, stack, adj)) return false;
            //邻接节点处于访问结束状态不处理
        }
        //顺利访问完成的结果入栈,更新结果状态,返回true
        stack.offerLast(i);
        visited[i] = 2;
        return true;
    }

发表评论

电子邮件地址不会被公开。 必填项已用*标注