图的遍历方式

素颜马尾好姑娘i 2023-02-21 06:44 63阅读 0赞

# 图的遍历方式 #

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

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

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

## 广度优先搜索 ##

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70 1]

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的那条边的起始节点，整个进程反复进行直到所有节点都被访问为止。二叉树的前序遍历就是一种深度优先搜索。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70 3]

### 递归实现 ###

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;
                    }
                }
            }
    
        }

更多精彩内容关注本人公众号：架构师升级之路  
![在这里插入图片描述][20200627175030665.jpg]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200629154646878.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200629154655697.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200629154710106.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200629154718248.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk=,size_16,color_FFFFFF,t_70
[20200627175030665.jpg]: https://img-blog.csdnimg.cn/20200627175030665.jpg