图的遍历是指从图中某一顶点出发遍历图中的其他顶点，且使每一个顶点仅被访问一次，这一过程叫图的遍历。以下图为例，进行广度优先遍历 图的广度优先遍历 - 图1

BFS分析

假设从顶点hit开始搜索，首先将顶点hit放入缓冲区，此时则访问顶点hit的邻接顶点hot，在访问时将顶点hit拿出缓冲区，并将邻接顶点hot放入缓冲区，为下一次遍历做准备；

  • 辅助数据结构：队列（先进先出 从队尾入队，从队首出队，）
  • 顶点访问判重：如果在访问某个顶点时，发现此顶点已经访问过，则不再访问该顶点。
  • 路径记录： 一个顶点可能有多个邻接顶点，但任意一个顶点最多只能有一个前驱顶点（除起始顶点以外），用和顶点数目相等的数组pre[0….N-1]记录顶点的前驱顶点，例如pre[i]=j 表示第i个顶点的前一个顶点是j，此处存顶点的索引;

BFS算法框架

  • 辅助数据结构
  1. 队列queue，用于存储访问顶点；
  2. 数组d[0..N-1]，用于记录顶点被访问次数，简称步数；
  3. 数组pre[0..N-1]顶点的前驱顶点，即顶点最终的访问路径；
  • 算法描述
    假设从顶点开始搜索，将顶点放入队列q，记录步数d[0]=0，记录顶点的前驱pre[0]=-1;开始判断队列是否为空，非空则从队首取值，即将顶点出队列，然后访问顶点的邻接顶点，对每个顶点判重，如果没有访问过则将邻接顶点放入队列，假如是顶点hot，然后记录步数d[1]=d[0]+1，记录前驱pre[1]=0；

BFS算法思考

对于BFS的改进—双向BFS

  • 在图中指定一个起点和一个终点，从起点和终点同时搜索，直到相遇；这样缩短了搜索的路径。
  • 在原始的BFS中，如果搜索的树形结构中树额高度非常高时，即叶子非常多（树的宽度大），此时把一棵高度为h的树，用两个近似h/2的树替代，宽度相对较小。

BFS示例

定义图的数据结构

  1. pbulic class Graph {
  3.     public String[] vertexs;
  4.     public int[][] edageMatrix;
  6.     public Graph(String[] vertexs) {
  7.         this.vertexs = vertexs;
  8.         this.edageMatrix = new int[vertexs.length][vertexs.length];
  9.     }
  11.     public void addEdage(int i, int j) {
  12.         this.edageMatrix[i][j] = 1;
  13.     }
  15.     public int[] getAdjVertex(int i) {
  16.         return this.edageMatrix[i];
  17.     }
  18. }

使用广度优先遍历图的顶点，

  1. public class Worldladder {
  3.   public static void main(String[] args) {
  5.     String[] vertexs = {"hit0", "hot1", "dot2", "dog3", "lot4", "log5", "cog6"};
  6.     Graph graph = new Graph(vertexs);
  7.     graph.addEdage(0, 1);
  8.     graph.addEdage(1, 2);
  9.     graph.addEdage(1, 4);
  10.     graph.addEdage(2, 3);
  11.     graph.addEdage(2, 5);
  12.     graph.addEdage(3, 5);
  13.     graph.addEdage(3, 6);
  14.     graph.addEdage(4, 5);
  15.     graph.addEdage(5, 6);
  17.     //以hit 为开始顶点广度遍历图
  18.     solution(0, graph);
  19.   }
  21.   public static void solution(Integer beginWord, Graph graph) {
  22.     Queue<Integer> queue = new LinkedList<Integer>();
  23.     Set<Integer> visitedSet = new LinkedHashSet<Integer>();//访问路径
  24.     int step = 0;//访问步数
  25.     queue.offer(beginWord);
  27.     while (!queue.isEmpty()) {
  28.         int word = queue.poll();
  29.         if (visitedSet.contains(word)) {
  30.             continue;
  31.         }
  32.         step++;
  33.         visitedSet.add(word);
  34.         int[] adj = graph.getAdjVertex(word);
  35.         for (int i = 0; i < adj.length; i++) {
  36.             if (adj[i] == 1) queue.offer(i);
  37.         }
  38.     }
  39.     System.out.println(step);
  40.     for (int visited : visitedSet) {
  41.         System.out.print(graph.vertexs[visited] + "->");
  42.     }
  43.   }
  44. }