图的遍历方式

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

图有2种常见的遍历方式（有向图、无向图都适用）

广度优先搜索（Breadth First Search，BFS），又称为宽度优先搜索、横向优先搜索
深度优先搜索（Depth First Search，DFS）

广度优先搜索

广度优先搜索：从起始节点开始一层一层的进行遍历，只有完全遍历完一层所有的节点后才会进入下一层的遍历。二叉树的层序遍历就是一种广度优先搜索。

在这里插入图片描述

Graph<V, E>接口中添加内部接口：

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

代码实现如下：

    public void bfs(V begin, Visitor<V> visitor) {// 根据值获取起始顶点Vertex<V, E> beginVertex = vertices.get(begin);if(Objects.isNull(beginVertex)) {return;}Queue<Vertex<V, E>> queue = new LinkedList<>();Set<Vertex<V, E>> visitedVertices  = new HashSet<>(); // 记录已经添加入队列中的顶点queue.offer(beginVertex);visitedVertices.add(beginVertex);while (!queue.isEmpty()) {Vertex<V, E> vertex = queue.poll();// 返回true终止遍历if(visitor.visit(vertex.value)) {return;}vertex.outEdges.forEach(edge -> {if(!visitedVertices.contains(edge.toVertex)) {queue.offer(edge.toVertex);visitedVertices.add(edge.toVertex);}});}}

深度优先搜索

深度优先搜索：从起始节点沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过或者无法继续往下搜索时，搜索将回溯到发现节点v的那条边的起始节点，整个进程反复进行直到所有节点都被访问为止。二叉树的前序遍历就是一种深度优先搜索。

在这里插入图片描述

递归实现

    public void dfs(V begin, Visitor<V> visitor) {// 根据值获取起始顶点Vertex<V, E> beginVertex = vertices.get(begin);if(Objects.isNull(beginVertex)) {return;}// 递归调用dfs(beginVertex, visitor, new HashSet<>());}// dfs返回true，中断遍历private boolean dfs(Vertex<V, E> vertex, Visitor<V> visitor, Set<Vertex<V, E>> visitedVertices) {if(visitor.visit(vertex.value)) {return true;}visitedVertices.add(vertex);Iterator<Edge<V, E>> iterator = vertex.outEdges.iterator();while (iterator.hasNext()) {Edge<V, E> edge = iterator.next();if(!visitedVertices.contains(edge.toVertex)) {if(dfs(edge.toVertex, visitor, visitedVertices)) {return true;}}}return false;}

迭代实现

    public void dfs(V begin, Visitor<V> visitor) {// 根据值获取起始顶点Vertex<V, E> beginVertex = vertices.get(begin);if (Objects.isNull(beginVertex)) {return;}Set<Vertex<V, E>> visitedVertices = new HashSet<>();Stack<Vertex<V, E>> stack = new Stack<>();stack.push(beginVertex);visitedVertices.add(beginVertex);if(visitor.visit(beginVertex.value)) {return;}while (!stack.isEmpty()) {Vertex<V, E> vertex = stack.pop();Iterator<Edge<V, E>> iterator = vertex.outEdges.iterator();while (iterator.hasNext()) {Edge<V, E> edge = iterator.next();if(!visitedVertices.contains(edge.toVertex)) {stack.push(vertex);stack.push(edge.toVertex);visitedVertices.add(edge.toVertex);if(visitor.visit(edge.toVertex.value)) {return;}break;}}}}