图的广度优先遍历概念和实现

2021年6月18日 1点热度 0条评论 来源: yulio1234

广度优先遍历是按层次遍历,和树的广度优先遍历很像。给定一个顶点,一层一层的往外遍历。可以想象成一组人在向各个方向走迷宫,当遇到路口时等待其他人走到这一层路口,然后分裂成更多的人走这个迷宫。
广度优先遍历是通过队列实现的。
与深度优先不同,paths找到的路径是顶点到目标点最短的路径

/** * 广度优先遍历 * @author yuli * */
public class BreadthFirstSearch implements Paths{ 
    //标记是否被访问列表
    private boolean[] marked;
    //访问的次数
    private int count;

    private int[] edgeTo;源顶点,用来记录寻找路径

    private int start;//开始的顶点
    public BreadthFirstSearch(UndirectedGraph graph,int start) {
        //通过顶点数创建访问列表
        marked = new boolean[graph.vertexNum()];
        this.start = start;
        edgeTo = new int[graph.vertexNum()];
        bfs(graph, start);
    }
    //广度优先搜索方法
    public void bfs(UndirectedGraph graph,int vertex){
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(vertex);
        marked[vertex] = true;
        //如果队列不为空就循环
        while(!queue.isEmpty()){
            //获得队头
            vertex = queue.poll();
            //访问队头
            System.out.println(vertex);
            //遍历邻接点
            Iterable<Integer> adj = graph.adj(vertex);
            for (Integer integer : adj) {
                //如果邻接点没有被访问就入队
                if(!marked[integer]){
                    //标记邻接点已经被访问了
                    marked[integer] = true;
                    //记录邻接点的源路径
                    edgeTo[integer] = vertex;
                    //将邻接点入队
                    queue.offer(integer);
                }
            }
        }
    }
    /** * 是否包含到v的路径 */
    @Override
    public boolean hasPathTo(int v) {
        //该顶点是否被访问过
        return marked[v];
    }
    /** * 找到起始顶点到指定顶点(v)的一条路径 */
    @Override
    public Iterable<Integer> pathTo(int v) {
        if(!hasPathTo(v)){
            return null;
        }
        Stack<Integer> path = new Stack<>();
        //从路径的顶点,递归回到开始的节点
        for(int m = v;m != start ;m = edgeTo[m]){
            path.push(m);
        }
        path.push(start);
        return path;
    }
}
    原文作者:yulio1234
    原文地址: https://blog.csdn.net/yulio1234/article/details/77731616
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。