数据结构第二季 Day08 图的广度优先搜索(BFS)、深度优先

一、图的广度优先搜索

1、图的遍历是怎么定义的？有哪两种常见的方式？

• 图的遍历：由图中某一顶点出发访问图中其余顶点，且每一个顶点仅被访问一次

• 常见的遍历方式有 2 种（有向图、无向图都适用）
• ①广度优先搜索（Breadth First Search，BFS），又称为宽度优先搜索、横向优先搜索
• ②深度优先搜索（Depth First Search，DFS），发明的科学家获得了图灵奖

image.png

2、下图按照广度优先搜索规则分层，动手分一分，要能分清楚？

image.png image.png

3、广度优先搜索代码实现思路（思路很重要）？

• 参考二叉树的层序遍历

image.png

4、广度优先搜索代码代码实现？

    @Override
    public void bfs(V begin) {
        Vertex<V, E> beginVertex = vertices.get(begin);
        if (beginVertex == null) return;

        Set<Vertex<V, E>> visitedVertices = new HashSet<>();
        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);
            vertex.outEdges.forEach((Edge<V, E> edge) -> {
                if (!visitedVertices.contains(edge.to)) {
                    queue.offer(edge.to);
                    visitedVertices.add(edge.to);
                }
            });
        }
    }

二、图的深度优先搜索

1、什么是深度优先搜索（Depth First Search）？

• 之前所学的二叉树前序遍历就是一种深度优先搜索
• 深度优先：①沿着一条路（未走过的）有多深走多深，直到不能走了； ②回退一步；③重复①、②操作；

image.png

2、用深度优先搜索的思想，把下图的所有情况都走一遍？

image.png image.png

3、既然二叉树的前序遍历也是深度优先的搜索，那么是否可以给我们启发呢？深度优先有哪两种遍历方式？

• 递归遍历
• while 遍历

4、思考下图中的 visitedVertices 变量是否可以写成 ListGraph 的成员变量？

image.png

• 我们不能为了一个方法内部的遍历操作的实现，去污染外部代码
• 所以比较好的是方法内部自己解决

5、DFS 的递归实现

    public void dfs(V begin) {
        Vertex<V, E> beginVertex = vertices.get(begin);
        if (beginVertex == null) return;

        dfs(beginVertex, new HashSet<>());
    }

    private void dfs(Vertex<V, E> vertex, Set<Vertex<V, E>> visitedVertices) {
        System.out.println(vertex.value);
        visitedVertices.add(vertex);
        vertex.outEdges.forEach((Edge<V, E> edge) -> {
            if (!visitedVertices.contains(edge.to)) {
                dfs(edge.to, visitedVertices);
            }
        });
    }

三、深度优先搜索非递归实现

1、递归算法转换成非递归算法的两个思路？

• ①首先抓住递归函数是不断开辟栈空间的，不断开辟的栈空间 其实和 栈 这种数据结构很相似。
• ②不断开辟，转换成非递归，肯定有个循环，一般是 while 循环。

2、深度优先搜索 - 非递归思路？

核心思路：弹出一条后，将 from 和 to 都加入 stack 中，然后 break；

image.png

3、在搜索遍历过程中，需要把每次遍历到的内容暴露给调用者，在 java 中如何实现？

• 声明一个接口 Visitor 类，再声明一个接口 visit 函数。
• 因为这个接口只有一个函数，所以也可以使用 lambda 表达式进行简写

    public interface VertexVisitor<V> {
        boolean visit(V v);
    }


    public abstract void bfs(V begin, VertexVisitor<V> visitor);
    public abstract void dfs(V begin, VertexVisitor<V> visitor);

4、DFS 的非递归实现

• 以下是我自己的版本，我怎么觉得我的版本更简单，而且也是正确的丫

    public void dfs(V begin) {
        Vertex<V, E> beginVertex = vertices.get(begin);
        if (beginVertex == null) return;

        Set<Vertex<V, E>> visitedVertices = new HashSet<>();
        Stack<Vertex<V, E>> stack = new Stack<>();

        Vertex<V, E> vertex = beginVertex;
        stack.push(vertex);
        visitedVertices.add(beginVertex);

        while (!stack.isEmpty()) {
            vertex = stack.pop();
            System.out.print(vertex.value + "_");

            vertex.outEdges.forEach((Edge<V, E> edge) -> {
                if (!visitedVertices.contains(edge.to)) {
                    stack.push(edge.to);
                    visitedVertices.add(edge.to);
                }
            });
        }
    }

• 以下是正规版本

    public void dfs(V begin, VertexVisitor<V> visitor) {
        if (visitor == null) return;
        Vertex<V, E> beginVertex = vertices.get(begin);
        if (beginVertex == null) return;

        Set<Vertex<V, E>> visitedVertices = new HashSet<>();
        Stack<Vertex<V, E>> stack = new Stack<>();

        // 先访问起点
        stack.push(beginVertex);
        visitedVertices.add(beginVertex);
        if (visitor.visit(begin)) return;

        while (!stack.isEmpty()) {
            Vertex<V, E> vertex = stack.pop();

            for (Edge<V, E> edge : vertex.outEdges) {
                if (visitedVertices.contains(edge.to)) continue;

                stack.push(edge.from);
                stack.push(edge.to);
                visitedVertices.add(edge.to);
                if (visitor.visit(edge.to.value)) return;

                break;
            }
        }
    }

四、图的基本操作补充

1、在 java 中一边遍历数组，一边删除遍历到的元素要怎么做？如何实现 graph 的 removeEdge 和 removeVertex 方法？

• 使用迭代器删除

        for (Iterator<Edge<V, E>> iterator = vertex.outEdges.iterator(); iterator.hasNext();) {
            Edge<V, E> edge = iterator.next();
            edge.to.inEdges.remove(edge);
            // 将当前遍历到的元素edge从集合vertex.outEdges中删掉
            iterator.remove();
            edges.remove(edge);
        }

• 实现 graph 的 removeEdge 和 removeVertex 方法

    @Override
    public void removeEdge(V from, V to) {
        Vertex<V, E> fromVertex = vertices.get(from);
        Vertex<V, E> toVertex = vertices.get(to);
        if (fromVertex == null || toVertex == null) return;

        Edge<V, E> edge = new Edge<>(fromVertex, toVertex);
        if (fromVertex.outEdges.remove(edge)) {
            toVertex.inEdges.remove(edge);
            edges.remove(edge);
        }

    }

    @Override
    public void removeVertex(V v) {
        Vertex<V, E> vertex = vertices.remove(v);
        if (vertex == null) return;

        for (Iterator<Edge<V, E>> iterator = vertex.outEdges.iterator(); iterator.hasNext();) {
            Edge<V, E> edge = iterator.next();
            edge.to.inEdges.remove(edge);
            // 将当前遍历到的元素edge从集合vertex.outEdges中删掉
            iterator.remove();
            edges.remove(edge);
        }

        for (Iterator<Edge<V, E>> iterator = vertex.inEdges.iterator(); iterator.hasNext();) {
            Edge<V, E> edge = iterator.next();
            edge.from.outEdges.remove(edge);
            // 将当前遍历到的元素edge从集合vertex.inEdges中删掉
            iterator.remove();
            edges.remove(edge);
        }
    }

2、写代码时最好实现成有向图，为什么？

• 因为有向图可以用来表达无向图
• 无向图却不能用来表达有向图