图的广度优先遍历（Java实现）

PS：本文为转载文章，原文可读性会更好，文末有原文链接思路一，2图1的广度优先遍历算法步骤，3图的广度优先遍历代码实现在这篇文章中，我们学习了图的深度优先遍历。本篇我们主要学习图的广度优先遍历。这里先介绍一下图的广度优先遍历的基本思想。为了方便和理解这个思路，我先画一张图，如图1；图片的思路：（1）广度优先遍历，类似于层次搜索的过程；以图1为例，A顶点为第一层，B、C顶点为第二层，D、E、F、G顶点为第三层，H顶点为第四层。搜索过程从第一层开始，然后搜索下层。这总是可以理解的吗？(2)广度优先遍历需要用一个队列来保持被访问节点的顺序，从而按照这个顺序访问这些节点的相邻节点；以图1为例，先保存A顶点，然后把A顶点先访问，访问完A顶点后，从队列中删除A顶点，再访问A顶点的所有相邻顶点（B，C）并加入将它们加入队列，在访问完B、C、B之后访问C的相邻顶点（D、E）和C的相邻顶点（F、G）并删除顶点B、C，以此类推下面的顶点B和C...其实就是逐层进行Access，图1中的广度优先遍历结果是A->B->C->D->E->F->G->H。1.2图的广度优先遍历算法步骤在讲图的广度优先遍历算法步骤之前，我将以图1为例，列出实现图1所用到的一些变量；顶点数vertexNum为8，顶点列表lstVertex为A,B,C,D,E,F,G,H，边数edgeNum为8，队列lstSearch一开始为空；使用isVisited数组标记每个顶点是否被访问过，默认没有访问过，即每个元素的值为false；边的二维数组vertexPathArray如图2所示（注：1表示2个顶点直接相连，0表示2个顶点不直接相连）；图片的算法步骤（注：算法步骤如果看不懂，先看下面代码实现，再回头看算法步骤理解）：（1）访问初始节点索引并标记asvisited，其中index为顶点列表的索引，以图1为例，index为0，则取出lstVertex.get(0)进行访问，并设置isVisited[0]为true，表示第0个lstVertex的元素已被访问。(2)对于节点索引为index的队列，广度遍历需要维护一个本地队列lstSearch。(3)判断本地队列lstSearch的大小是否为0(一开始lstSearch的大小一定不能为0)，如果为0，则不执行(4)之后的步骤；如果lstSearch的大小不为0，则转到Godown(4)。(4)如果lstSearch的大小不为0，则删除lstSearch的第一个索引，返回得到一个顶点列表lstVertex元素的索引（用currIndex表示删除lstSearch的第一个索引），然后往下执行（5）;以图1为例，假设lstSearch的第一个索引元素为A，然后删除lstSearch的第一个索引，则A在lstVertex中的索引是否为0，从而得到顶点列表lstVertex元素索引为0。（5）获取索引为currIndex的顶点的第一个相邻顶点（currIndex也是lstVertex中元素的索引），将这个相邻顶点的索引设置为nextIndex，然后执行（6）。(6)如果nextIndex为-1，则执行(3)；如果nextIndex不为-1，则执行(7)。(7)如果nextIndex索引的顶点已经被访问过，则获取索引为currIndex的下一个相邻顶点的索引，并将这个索引赋值给nextIndex，然后执行(6)；如果nextIndex索引的顶点没有被访问过，则将索引为nextIndex的顶点加入队列lstSearch，并设置isVisited[nextIndex]为true表示nextIndex索引的顶点已经被访问过，并使用nextIndex作为索引从顶点列表lstVertex中输出顶点，然后获取索引为currIndex的下一个相邻顶点的索引，并将这个索引赋值给nextIndex，然后执行(6)。图1中的广度遍历过程如下：(1)从顶点A开始访问，将顶点A加入队列lstSearch，然后从队列lstSearch中删除顶点A，然后搜索顶点A的所有相邻顶点B和C。它输出(B,C)并将B,C添加到队列lstSearch中。(2)从lstSearch中删除B顶点，找到B顶点的所有相邻顶点D和E并输出(D,E)，然后将顶点D和E添加到lstSearch中。(3)从lstSearch中删除C顶点，找出C顶点的所有相邻顶点F和G并输出(F,G)，然后将顶点F和G添加到lstSearch中。(4)从lstSearch中删除D个顶点，找出D个顶点的所有相邻顶点H并输出(H)，然后将顶点H加入到lstSearch中。1.3图的广度优先遍历代码实现下面用代码实现一下；(1)创建图形类MyChart：packagecom.xiaoer.figure;importjava.util.ArrayList;importjava.util.LinkedList;importjava.util.List;publicclassMyChart{/**创建图@paramvertexNum顶点数@return返回MyChart对象*/publicstaticMyChartcreateChart(intvertexNum){MyChartmyChart=newMyChart(vertexNum);myChart.addVertices();myChart.addEdges();returnmyChart;}/**添加所有边，添加的边由两个顶点直接相连，见图5，A和B之间是否有边直接相连，indexOf方法返回传入的位置一维数组中的顶点（即下标）*/privatevoidaddEdges(){addEdge(indexOf("A"),indexOf("B"),1);addEdge(indexOf("A"),indexOf("C"),1);addEdge(indexOf("B"),indexOf("D"),1);addEdge(indexOf("B"),indexOf("E"),1);addEdge(indexOf("C"),indexOf("F"),1);addEdge(indexOf("C"),indexOf("G"),1);addEdge(indexOf("D"),indexOf("H"),1);addEdge(indexOf("E"),indexOf("H"),1);}/**全部相加顶点，看图5，是不是增加了A-H这8个顶点？*/privatevoidaddVertices(){addVertex("A");addVertex("B");addVertex("C");addVertex("D");addVertex("E");addVertex("F");addVertex("G");addVertex("H");}/**顶点数*/privateintvertexNum;/**顶点列表*/privateListlstVertex;/**顶点路径*/privateint[][]vertexPathArray;/**边数*/privateintedgeNum;/**已被访问*/privateboolean[]isVisited;MyChart(intvertexNum){this.vertexNum=vertexNum;lstVertex=newArrayList<>(vertexNum);vertexPathArray=newint[vertexNum][vertexNum];isVisited=newboolean[vertexNum];}/**添加顶点，这里不涉及展开@paramvertex添加的Vertex*/voidaddVertex(Stringvertex){if(vertexNum==lstVertex.size()){thrownewArrayIndexOutOfBoundsException("Arrayisfull");}lstVertex.add(vertex);}/**return顶点索引@paramvertex目标顶点@returnreturnsubscript*/intindexOf(Stringvertex){returnlstVertex.indexOf(vertex);}/**添加边@paramxIndex横坐标@paramyIndexordinate@paramweight边的权重，weight=1，表示两个顶点相连，成为一条边*/voidaddEdge(intxIndex,intyIndex,intweight){if(xIndex>=vertexNum||yIndex>=vertexNum){thrownewIndexOutOfBoundsException("IndexOutofBounds");}vertexPathArray[xIndex][yIndex]=weight;vertexPathArray[yIndex][xIndex]=weight;edgeNum++;}/**得到数量edges@return返回边数*/intgetEdgeNum(){returnedgeNum;}/**获取下一个相邻节点@paramindex当前顶点的横坐标@paramnextIndex当前顶点的前一个相邻顶点的纵坐标@return*/privateintgetNextNeighbor(intindex,intnextIndex){/***i从当前顶点的前一个相邻顶点的纵坐标+1开始，*例如：见图5，二维数组边缘（vertexPathArr）是：*ABCDEFGH*A01100000*B10011000*C10000110*D01000001*E01000001*F00100000*G00100000*H00011000**假设当前顶点是A顶点，并且已经找到A顶点的第一个邻接对于顶点B，A所在行的索引为0，B在第0行的第一列（nextIndex=*1），对吧？然后找出A的下一个相邻顶点是否从第二列开始(nextIndex+1))开始寻找*/for(inti=nextIndex+1;i0){返回i;}}return-1;}/**获取第一个相邻节点@paramindex表示行坐标@return*/privateintgetFirstNeighbor(intindex){/***一开始i为0，表示从第0列*例如：见图5，边的二维数组（vertexPathArr）为：*ABCDEFGH*A01100000*B10011000*C10000110*D01000001*E01000001*F00100000*G00100000*H00011000**假设当前顶点为C顶点，已经找到C顶点的第一个相邻顶点A，其中C所在的行坐标索引为2，*那么，应该是C顶点的第一个相邻顶点从第2行第0列开始搜索？*/for(inti=0;i0){返回i;}}//没有找到，直接返回-1return-1;}/**广度优先遍历*/publicvoidbfs(){bfs(0);}privatevoidbfs(intindex){LinkedListlstSearch=newLinkedList<>();System.out.print(lstVertex.get(index)+"->");//添加节点到集合lstSearch.add(index);//标识节点已经遍历isVisited[index]=true;//队列不为空，顺序处理for(;lstSearch.size()>0;){//获取队列中第一个顶点的索引IntegercurrIndex=lstSearch.removeFirst();//获取顶点的相邻顶点的索引intnextIndex=getFirstNeighbor(currIndex);//存在相邻节点for(;-1!=nextIndex;){//如果相邻顶点没有被访问过if(!isVisited[nextIndex]){lstSearch.add(nextIndex);isVisited[nextIndex]=true;System.out.print(lstVertex.get(nextIndex)+"->");}//获取下一个要处理的顶点的索引nextIndex=getNextNeighbor(currIndex,nextIndex);}}}}(2)创建测试类Test:packagecom.xiaoer.figure;publicclassTest{publicstaticvoidmain(String[]args){MyChartmyChart=MyChart.createChart(8);System.out.println("深度优先遍历：");myChart.bfs();}}运行程序，日志打印如下图；图片