集册 | Java 实现图的广度优先搜索（BFS）算法，一起深度学习算法思维！

vlambda
2020-06-08

集册 | Java 实现图的广度优先搜索（BFS）算法，一起深度学习算法思维！

关注新技术，学习新知识！

本文为节选于《Java实例集册》，查看集册其它实例请到官网查看。

图的广度优先搜索（BFS）算法简述

基本概念：
对于给定的图G=(V,E),广度优先搜索从一个源顶点出发，通过对其邻接表进行遍历(搜索)，可以发现所有与源顶点邻接的顶点。依次类推，不断地向外扩展，进而发现与源顶点的邻接点相邻接的顶点。故得名广度优先搜索(BFS);

算法思想：
为了标记一个顶点是否被发现，其邻接表是否已经被扫描，广度优先搜索采用三种颜色进行标识，即白色、灰色和黑色。
1. 如果一个顶点没有被发现，则其颜色为白色；（未入队列）
2. 如果一个顶点已经被发现而邻接表未被搜索，则其为灰色；（已入队列）
3. 如果一个顶点的邻接表已经被扫描完，则其为黑色；（已出队列）

算法实现代码节选：

import java.util.Arrays;import java.util.Collections;import java.util.LinkedList;import java.util.List;
@SuppressWarnings({ "Duplicates", "WeakerAccess" })public class BFS {
 public Vertex search(Vertex start, String searchName) {
 LinkedListqueue = new LinkedList<>(); queue.addLast(start);
 while (!queue.isEmpty()) {
 Vertex vertex = queue.pollFirst(); vertex.color = Vertex.Color.BLACK; /* * 来 自* 时 代 J a v a 公 众 号 - nowjava.com */ if (vertex.name.equals(searchName)) { return vertex; }
 for (Vertex v : vertex.adjacentVertices) { if (v.color == Vertex.Color.WHITE) { v.color = Vertex.Color.GREY; v.depth = vertex.depth + 1;          queue.addLast(v); } } }
 return null; }
  /**   * Test main method   */ public static void main(String[] args) {
 Vertex vertexA = new Vertex("A"); Vertex vertexB = new Vertex("B"); Vertex vertexC = new Vertex("C"); Vertex vertexD = new Vertex("D"); Vertex vertexE = new Vertex("E"); Vertex vertexF = new Vertex("F"); Vertex vertexG = new Vertex("G");
 vertexA.adjacentVertices = Arrays.asList(vertexB, vertexC); vertexB.adjacentVertices = Arrays.asList(vertexA, vertexD); vertexC.adjacentVertices = Arrays.asList(vertexA, vertexE); vertexD.adjacentVertices = Arrays.asList(vertexB, vertexE); vertexE.adjacentVertices = Arrays.asList(vertexC, vertexF, vertexD); vertexF.adjacentVertices = Arrays.asList(vertexE, vertexG); vertexG.adjacentVertices = Collections.singletonList(vertexF); BFS bfs = new BFS(); Vertex vertex = bfs.search(vertexG, "A"); System.out.println(vertex == null ? "Not found" : vertex);
 }
  private static class Vertex { private ListadjacentVertices; private String name; private int depth; private Color color;
 Vertex(String name) { this.name = name; color = Color.WHITE; }
 @Override public String toString() { return "Vertex{" + "name='" + name + '\'' + ", depth=" + depth + ", color=" + color + '}'; }
 private enum Color { BLACK, GREY, WHITE } }}