广度优先搜索BFS及java实现

约定不等于承诺〃 2023-07-07 12:46 18阅读 0赞

广度优先搜索是图里面一种基础的搜索算法，英文简写BFS（breadth First Search），广度优先搜索能够搜索到源节点S到图中其他节点的最短距离，该方法适用于无权有向或者无权无向图中，

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pvaG4xMzM3_size_16_color_FFFFFF_t_70][]

广度优先搜索采用的方式类似二叉树的层次遍历，比如对节点V3来说，V1、V5属于第一层，V4、V6、V2属于第二层，从V3到V5的最短距离是V3->V5这条边，而不是从V3->V1->V4->V5，好比人类关系一样，比如A、B、C、D、E五人，A认识B，B认识C，C认识E，于此同时A认识D，D也认识E，比如A需要找E办点事，正常的逻辑是通过D结实E，这样只需经过两道关系，通过B的话则需要经过三道关系，广度优先搜索类似，按照距离源节点的远近来进行检索。

下面给出广度优先搜索的java实现：

/**
    **图的节点类
    **/
    public class Vertex {
        //该节点颜色，当color为VertexColor.WHITE时表名该节点没有被路由过，为其他颜色说明已经被使用过，后续路径的遍历就不要再遍历这个节点了，前面已经提到了广度优先搜索的层次搜索概念，最先被搜索到的是与源节点关系最近的路径
    	private VertexColor color;
    	//源节点到该顶点的距离
    	private int distance;
    	//前驱节点
    	private Vertex pre;
    	//该顶点的连接队列
    	private List<Vertex> adjList;
    	//统计该节点在图顶点数组下标，对广度搜索非必要属性，仅用于统计使用
    	private int index ;
    	
    	public Vertex(int index){
    		this.index = index;
    		adjList = new LinkedList<>();
    		this.color = VertexColor.WHITE;
    		this.pre = null;
    		this.distance = Integer.MAX_VALUE;
    	}
    	
    	//添加邻接矩阵点
    	public void addVertex(Vertex v){
    		this.adjList.add(v);
    	}
    	
    	public VertexColor getColor() {
    		return color;
    	}
    	public void setColor(VertexColor color) {
    		this.color = color;
    	}
    	public int getDistance() {
    		return distance;
    	}
    	public void setDistance(int distance) {
    		this.distance = distance;
    	}
    	public Vertex getPre() {
    		return pre;
    	}
    	public void setPre(Vertex pre) {
    		this.pre = pre;
    	}
    	public List<Vertex> getAdjList() {
    		return adjList;
    	}
    	public void setAdjList(List<Vertex> adjList) {
    		this.adjList = adjList;
    	}
    	
    	@Override
    	public String toString(){
    		return String.format("到节点:%d的最短距离为:%d,前驱节点下标为:%d,当前颜色为:%s", index,distance,pre.index,color);
    	}
    }

//顶点颜色
    public enum VertexColor {
    	WHITE,GRAY,BLACK;
    }

public class Graph {
    	//图中的顶点
    	private List<Vertex> vertexes;
    	
    	public Graph(int len){
    		//初始化时指定长度，避免扩容
    		vertexes = new ArrayList<>(len);
    	}
    	
    	public void addVertex(Vertex v){
    		vertexes.add(v);
    	}
    	
    	public List<Vertex> getVertexes() {
    		return vertexes;
    	}
    
    	public void setVertexes(List<Vertex> vertexes) {
    		this.vertexes = vertexes;
    	}
    }

上面为基础类，下面为demo代码：

@Test
    	public void bfsSearch(){
    		Graph g= new Graph(6);
    		
    		Vertex v1 = new Vertex(1);
    		Vertex v2 = new Vertex(2);
    		Vertex v3 = new Vertex(3);
    		Vertex v4 = new Vertex(4);
    		Vertex v5 = new Vertex(5);
    		Vertex v6 = new Vertex(6);
    		//初始化图的顶点数组
    		g.addVertex(v1);
    		g.addVertex(v2);
    		g.addVertex(v3);
    		g.addVertex(v4);
    		g.addVertex(v5);
    		g.addVertex(v6);
    		//初始化邻接矩阵
    		v1.addVertex(v2);
    		v1.addVertex(v4);
    		//
    		v2.addVertex(v4);
    		//
    		v3.addVertex(v1);
    		v3.addVertex(v5);
    		//
    		v4.addVertex(v5);
    		v4.addVertex(v6);
    		//
    		v5.addVertex(v6);
    		//查找v3节点到其他节点的最短距离
    		println("节点v3到其他节点的最短距离");
    		bfs(g,v3);
    		//查找v1节点到其他节点的最短距离
    		println("节点v1到其他节点的最短距离");
    		bfs(g,v1);
    	}
    	
    	public void bfs(Graph g,Vertex s){
    		//清空数据
    		List<Vertex> vertexList = g.getVertexes();
    		for(Vertex v:vertexList){
    			v.setColor(VertexColor.WHITE);
    			v.setDistance(Integer.MAX_VALUE);
    			v.setPre(null);
    		}
    		//设置源节点数据，自己到自己的最短距离为0
    		s.setDistance(0);
    		s.setColor(VertexColor.GRAY);
    		//LinkedList也是一种队列
    		Queue<Vertex> q = new LinkedList<>();
    		q.add(s);
    		while(!q.isEmpty()){
    			//将顶点从队列弹出
    			Vertex u = q.remove();
    			List<Vertex> list = u.getAdjList();
    			for(Vertex v:list){
    				if(v.getColor() == VertexColor.WHITE){
    					v.setColor(VertexColor.GRAY);
    					//设置源节点到该节点的距离，在前驱节点的基础上加1
    					v.setDistance(u.getDistance()+1);
    					//
    					v.setPre(u);
    					//将v入队列
    					q.add(v);
    				}
    			}
    			//更新u节点颜色
    			u.setColor(VertexColor.BLACK);
    		}
    		//输出源节点到每个节点的最短距离
    		for(Vertex v:vertexList){
    			if(v == s || v.getDistance() == Integer.MAX_VALUE)
    				continue;
    			println(v.toString());
    		}
    	}

输出：  
节点v3到其他节点的最短距离  
到节点:1的最短距离为:1,前驱节点下标为:3,当前颜色为:BLACK  
到节点:2的最短距离为:2,前驱节点下标为:1,当前颜色为:BLACK  
到节点:4的最短距离为:2,前驱节点下标为:1,当前颜色为:BLACK  
到节点:5的最短距离为:1,前驱节点下标为:3,当前颜色为:BLACK  
到节点:6的最短距离为:2,前驱节点下标为:5,当前颜色为:BLACK  
节点v1到其他节点的最短距离  
到节点:2的最短距离为:1,前驱节点下标为:1,当前颜色为:BLACK  
到节点:4的最短距离为:1,前驱节点下标为:1,当前颜色为:BLACK  
到节点:5的最短距离为:2,前驱节点下标为:4,当前颜色为:BLACK  
到节点:6的最短距离为:2,前驱节点下标为:4,当前颜色为:BLACK

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pvaG4xMzM3_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200223180835448.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pvaG4xMzM3,size_16,color_FFFFFF,t_70