深度优先和广度优先查找以及拓扑排序

深度和广度优先查找

• 归属：蛮力法

• 简称：DFS(深度优先查找)、BFS(广度优先查找)

• 思想：

  • DFS： 深度优先查找深林。如果遇到一个新的未访问结点，则继续访问该结点，进行递归访问。
  • BFS： 广度优先访问深林。借助队列，队列一开始只有一个未访问结点，弹出结点，访问该结点，并将该顶点的未访问的子节点放入队列，然后队列再循环弹出结点，重复之前的操作。

• 算法：

    static class Node {
        int value;
        Node[] next;
        boolean marked = false;
    }

    /**
     * 深度优先遍历
     */
    public static void dfs(Node[] nodes) {
        for (Node node : nodes) {
            if (!node.marked) dfs(node);
        }
    }

    static Stack<Node> stack = new Stack<>();
    private static void dfs(Node node) {
        stack.push(node);
        node.marked = true;
        System.out.println("访问结点,值=" + node.value);
        for (Node nextN : node.next) {
            if (!nextN.marked) {
                dfs(nextN);
                break;
            }
        }
        while (stack.isEmpty()) {
            stack.pop();
            //回退到前一个，判断是否还有结点未访问
            Node n = stack.pop();
            stack.push(n);
            for (Node nextN : n.next) {
                if (!nextN.marked) {
                    dfs(nextN);
                    break;
                }
            }
        }
    }

//    /**
//     * 不使用栈的DFS
//     */
//    private static void dfs(Node node) {
//        System.out.println("访问结点,值=" + node);
//        node.marked = true;
//        for (Node nextNode : node.next) {
//            if (!nextNode.marked) {
//                dfs(nextNode);
//            }
//        }
//    }

    


    /**
     * 广度优先遍历
     */
    public static void bfs(Node[] nodes) {
        for (Node node : nodes) {
            if (!node.marked) bfs(node);
        }
    }

    private static void bfs(Node node) {
        Queue<Node> queue = new ArrayDeque<>();
        queue.add(node);
        while (!queue.isEmpty()) {
            Node headNode = queue.poll();
            headNode = true;
            System.out.println("访问结点,值=" + headNode.value);
            for (Node oneNode : headNode.next) {
                if (!oneNode.marked) queue.add(oneNode);
            }
        }
    }

• 思考：算法中的Node类包含了一个变量marked，但是在很多时候我们拿到的链表结点对象是没有这个变量的。我尝试通过包装类去给一个普通链表结点添加这个变量，但实际上不可实现，或者不值得实现。我得出的结论是：链表这种数据结构是不可包装的，或者说想要包装一个链表的消耗是很大的。

拓扑排序

• 介绍
  由AOV网构造拓扑序列的拓扑排序算法主要是循环执行以下两步，直到不存在入度为0的顶点为止。
  1. 选择一个入度为0的顶点并输出之；
  2. 从网中删除此顶点及所有出边
  3. 重复操作

排序V5-V1-V4-V3-V7-V6

• 思路
  上面的DFS中，stack的所有pop()操作完成后，pop()出来的值的逆序便是拓扑排序。