广度优先遍历基本思想

图的广度优先搜索(Broad First Search) 。
类似于一个分层搜索的过程，广度优先遍历需要使用一个队列以保持访问过的结点的顺序，以便按这个顺序来访问这些结点的邻接结点

广度优先遍历算法步骤

  1. 访问初始结点v并标记结点v为已访问。
  2. 结点v入队列
  3. 当队列非空时，继续执行，否则算法结束。
  4. 出队列，取得队头结点u。
  5. 查找结点u的第一个邻接结点w。
  6. 若结点u的邻接结点w不存在，则转到步骤3；否则循环执行以下三个步骤：
    1. 若结点w尚未被访问，则访问结点w并标记为已访问。
    2. 结点w入队列
    3. 查找结点u的继w邻接结点后的下一个邻接结点w，转到步骤6。

      实例

      image.png
      广度优先算法的遍历顺序为：1->2->3->4->5->6->7->8

      实现代码

      ```java import java.util.ArrayList; import java.util.Arrays; import java.util.LinkedList;

public class Graph {

  1. private ArrayList<String> vertexList; //存储顶点集合
  2. private int[][] edges; //存储图对应的邻结矩阵
  3. private int numOfEdges; //表示边的数目
  4. //定义给数组boolean[], 记录某个结点是否被访问
  5. private boolean[] isVisited;
  7. public static void main(String[] args) {
  8.     //测试一把图是否创建ok
  9.     int n = 8;  //结点的个数
  10.     String Vertexs[] = {"1", "2", "3", "4", "5", "6", "7", "8"};
  12.     //创建图对象
  13.     Graph graph = new Graph(n);
  14.     //循环的添加顶点
  15.     for(String vertex: Vertexs) {
  16.         graph.insertVertex(vertex);
  17.     }
  19.     //添加边
  20.     graph.insertEdge(0, 1, 1);
  21.     graph.insertEdge(0, 2, 1);
  22.     graph.insertEdge(1, 3, 1);
  23.     graph.insertEdge(1, 4, 1);
  24.     graph.insertEdge(3, 7, 1);
  25.     graph.insertEdge(4, 7, 1);
  26.     graph.insertEdge(2, 5, 1);
  27.     graph.insertEdge(2, 6, 1);
  28.     graph.insertEdge(5, 6, 1);
  32.     //显示邻结矩阵
  33.     graph.showGraph();
  35.     //测试，bfs遍历是否ok
  36.     System.out.println("广度优先!");
  37.     graph.bfs(); // 1->2->3->4->5->6->7->8
  39. }
  41. //构造器
  42. public Graph(int n) {
  43.     //初始化矩阵和vertexList
  44.     edges = new int[n][n];
  45.     vertexList = new ArrayList<String>(n);
  46.     numOfEdges = 0;
  48. }
  50. //得到第一个邻接结点的下标 w 
  51. /**
  52.  * 
  53.  * @param index 
  54.  * @return 如果存在就返回对应的下标，否则返回-1
  55.  */
  56. public int getFirstNeighbor(int index) {
  57.     for(int j = 0; j < vertexList.size(); j++) {
  58.         if(edges[index][j] > 0) {
  59.             return j;
  60.         }
  61.     }
  62.     return -1;
  63. }
  64. //根据前一个邻接结点的下标来获取下一个邻接结点
  65. public int getNextNeighbor(int v1, int v2) {
  66.     for(int j = v2 + 1; j < vertexList.size(); j++) {
  67.         if(edges[v1][j] > 0) {
  68.             return j;
  69.         }
  70.     }
  71.     return -1;
  72. }
  74. //对一个结点进行广度优先遍历的方法
  75. private void bfs(boolean[] isVisited, int i) {
  76.     int u ; // 表示队列的头结点对应下标
  77.     int w ; // 邻接结点w
  78.     //队列，记录结点访问的顺序
  79.     LinkedList queue = new LinkedList();
  80.     //访问结点，输出结点信息
  81.     System.out.print(getValueByIndex(i) + "=>");
  82.     //标记为已访问
  83.     isVisited[i] = true;
  84.     //将结点加入队列
  85.     queue.addLast(i);
  87.     while( !queue.isEmpty()) {
  88.         //取出队列的头结点下标
  89.         u = (Integer)queue.removeFirst();
  90.         //得到第一个邻接结点的下标 w 
  91.         w = getFirstNeighbor(u);
  92.         while(w != -1) {//找到
  93.             //是否访问过
  94.             if(!isVisited[w]) {
  95.                 System.out.print(getValueByIndex(w) + "=>");
  96.                 //标记已经访问
  97.                 isVisited[w] = true;
  98.                 //入队
  99.                 queue.addLast(w);
  100.             }
  101.             //以u为前驱点，找w后面的下一个邻结点
  102.             w = getNextNeighbor(u, w); //体现出我们的广度优先
  103.         }
  104.     }
  106. } 
  108. //遍历所有的结点，都进行广度优先搜索
  109. public void bfs() {
  110.     isVisited = new boolean[vertexList.size()];
  111.     for(int i = 0; i < getNumOfVertex(); i++) {
  112.         if(!isVisited[i]) {
  113.             bfs(isVisited, i);
  114.         }
  115.     }
  116. }
  118. //图中常用的方法
  119. //返回结点的个数
  120. public int getNumOfVertex() {
  121.     return vertexList.size();
  122. }
  123. //显示图对应的矩阵
  124. public void showGraph() {
  125.     for(int[] link : edges) {
  126.         System.err.println(Arrays.toString(link));
  127.     }
  128. }
  129. //得到边的数目
  130. public int getNumOfEdges() {
  131.     return numOfEdges;
  132. }
  133. //返回结点i(下标)对应的数据 0->"A" 1->"B" 2->"C"
  134. public String getValueByIndex(int i) {
  135.     return vertexList.get(i);
  136. }
  137. //返回v1和v2的权值
  138. public int getWeight(int v1, int v2) {
  139.     return edges[v1][v2];
  140. }
  141. //插入结点
  142. public void insertVertex(String vertex) {
  143.     vertexList.add(vertex);
  144. }
  145. //添加边
  146. /**
  147.  * 
  148.  * @param v1 表示点的下标即使第几个顶点  "A"-"B" "A"->0 "B"->1
  149.  * @param v2 第二个顶点对应的下标
  150.  * @param weight 表示 
  151.  */
  152. public void insertEdge(int v1, int v2, int weight) {
  153.     edges[v1][v2] = weight;
  154.     edges[v2][v1] = weight;
  155.     numOfEdges++;
  156. }

} ```