8.bfs、dfs

广度优先搜索（Breadth First Search）

之前所学的二叉树层序遍历就是一种广度优先搜索

@Override
    public void bfs(V begin) {
        Vertex<V, E> beginVertex = vertices.get(begin);
        Set<Vertex<V, E>> visitedVertices = new HashSet<>();
        if (beginVertex == null) {
            return;
        }
        Queue<Vertex<V, E>> queue = new LinkedList<>();
        queue.offer(beginVertex);
        visitedVertices.add(beginVertex);
        while (!queue.isEmpty()) {
            Vertex<V, E> vertex = queue.poll();
            System.out.println(vertex.value);
            for (Edge<V, E> edge : vertex.outEdges) {
                //forEach
                if (visitedVertices.contains(edge.to)) {
                    continue;
                }
                queue.offer(edge.to);
                visitedVertices.add(edge.to);
            }
        }
    }

深度优先搜索（Depth First Search）

    **之前所学的二叉树前序遍历就是一种深度优先搜索

/**
     * @param beginVertex 非递归调用
     */
    private void dfs(Vertex<V, E> beginVertex) {
        Set<Vertex<V, E>> visitedVertex = new HashSet<>();
        Stack<Vertex<V, E>> stack = new Stack<>();
        stack.push(beginVertex);
        visitedVertex.add(beginVertex);
        System.out.println(beginVertex.value);
        while (!stack.isEmpty()) {
            Vertex<V, E> vertex = stack.pop();
            for (Edge<V, E> edge : vertex.outEdges) {
                if (visitedVertex.contains(edge.to)) {
                    continue;
                }
                stack.push(edge.from);
                stack.push(edge.to);
                visitedVertex.add(edge.to);
                System.out.println(edge.to.value);
                break;
            }
        }
    }

/**
     * 递归遍历
     * @param begin 从begin开始 深度优先搜索
     */
    @Override
    public void dfs(V begin) {
        Set<Vertex<V, E>> visitedVertex = new HashSet<>();
        Vertex<V, E> beginVertex = vertices.get(begin);
        if (beginVertex == null) {
            return;
        }
        dfs(beginVertex, visitedVertex);
    }
    private void dfs(Vertex<V, E> vertex, Set<Vertex<V, E>> visitedVertex) {
        System.out.println(vertex.value);
        visitedVertex.add(vertex);
        for (Edge<V, E> edge : vertex.outEdges) {
            if (visitedVertex.contains(edge.to)) {
                continue;
            }
            dfs(edge.to, visitedVertex);
        }
    }