广度优先搜索BFS及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;
	}
}

	@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());
		}
	}