广度优先搜索是图里面一种基础的搜索算法，英文简写BFS（breadth First Search），广度优先搜索能够搜索到源节点S到图中其他节点的最短距离，该方法适用于无权有向或者无权无向图中，
广度优先搜索采用的方式类似二叉树的层次遍历，比如对节点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实现：
代码语言：javascript复制/**
**图的节点类
**/
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代码：
代码语言：javascript复制 @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
