广度优先搜索是图里面一种基础的搜索算法，英文简写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实现：
-
/**
-
**图的节点类
-
**/
-
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
转载：https://blog.csdn.net/john1337/article/details/104464086
查看评论