算法
大家好，我是架构君，一个会写代码吟诗的架构师。今天说一说算法|深度优先搜索（DFS）与广度优先搜索（BFS）的Java实现[通俗易懂],希望能够帮助大家进步!!!
基础部分在图中实现最基本的操作之一就是搜索从一个指定顶点可以到达哪些顶点，比如从武汉出发的高铁可以到达哪些城市，一些城市可以直达，一些城市不能直达。现在有一份全国高铁模拟图，要从某个城市（顶点）开始，沿着铁轨（边）移动到其他城市（顶点），有两种方法可以用来搜索图：深度优先搜索（DFS）和广度优先搜索（BFS）。它们最终都会到达所有连通的顶点，深度优先搜索通过栈来实现，而广度优先搜索通过队列来实现，不同的实现机制导致不同的搜索方式。
深度优先搜索深度优先搜索算法有如下规则：规则1：如果可能，访问一个邻接的未访问顶点，标记它，并将它放入栈中。规则2：当不能执行规则1时，如果栈不为空，就从栈中弹出一个顶点。规则3：如果不能执行规则1和规则2时，就完成了整个搜索过程。
对于上图，应用深度优先搜索如下：假设选取A顶点为起始点，并且按照字母优先顺序进行访问，那么应用规则1，接下来访问顶点B，然后标记它，并将它放入栈中；再次应用规则1，接下来访问顶点F，再次应用规则1，访问顶点H。我们这时候发现，没有H顶点的邻接点了，这时候应用规则2，从栈中弹出H，这时候回到了顶点F，但是我们发现F也除了H也没有与之邻接且未访问的顶点了，那么再弹出F，这时候回到顶点B，同理规则1应用不了，应用规则2，弹出B，这时候栈中只有顶点A了，然后A还有未访问的邻接点，所有接下来访问顶点C，但是C又是这条线的终点，所以从栈中弹出它，再次回到A，接着访问D,G,I，最后也回到了A，然后访问E，但是最后又回到了顶点A，这时候我们发现A没有未访问的邻接点了，所以也把它弹出栈。现在栈中已无顶点，于是应用规则3，完成了整个搜索过程。
深度优先搜索在于能够找到与某一顶点邻接且没有访问过的顶点。这里以邻接矩阵为例，找到顶点所在的行，从第一列开始向后寻找值为1的列；列号是邻接顶点的号码，检查这个顶点是否未访问过，如果是这样，那么这就是要访问的下一个顶点，如果该行没有顶点既等于1（邻接）且又是未访问的，那么与指定点相邻接的顶点就全部访问过了（后面会用算法实现）。
广度优先搜索深度优先搜索要尽可能的远离起始点，而广度优先搜索则要尽可能的靠近起始点，它首先访问起始顶点的所有邻接点，然后再访问较远的区域，这种搜索不能用栈实现，而是用队列实现。
规则1：访问下一个未访问的邻接点（如果存在），这个顶点必须是当前顶点的邻接点，标记它，并把它插入到队列中。规则2：如果已经没有未访问的邻接点而不能执行规则1时，那么从队列列头取出一个顶点（如果存在），并使其成为当前顶点。规则3：如果因为队列为空而不能执行规则2，则搜索结束。
对于上面的图，应用广度优先搜索：以A为起始点，首先访问所有与A相邻的顶点，并在访问的同时将其插入队列中，现在已经访问了A,B,C,D和E。这时队列（从头到尾）包含BCDE，已经没有未访问的且与顶点A邻接的顶点了，所以从队列中取出B，寻找与B邻接的顶点，这时找到F，所以把F插入到队列中。已经没有未访问且与B邻接的顶点了，所以从队列列头取出C，它没有未访问的邻接点。因此取出D并访问G，D也没有未访问的邻接点了，所以取出E，现在队列中有FG，在取出F，访问H，然后取出G，访问I，现在队列中有HI，当取出他们时，发现没有其它为访问的顶点了，这时队列为空，搜索结束。
代码实现实现深度优先搜索的栈StackX.class：
packagetestOffer.graphpro;//实现深度优先搜索的栈publicclassStackX{privatefinalintSIZE=20;privateint[]st;privateinttop;publicStackX(){st=newint[SIZE];top=-1;}publicvoidpush(intj){st[++top]=j;}publicintpop(){returnst[top--];}publicintpeek(){returnst[top];}publicbooleanisEmpty(){return(top==-1);}}实现广度优先搜索的队列Queue.class：
此代码由Java架构师必看网-架构君整理packagetestOffer.graphpro;//实现广度优先搜索的队列publicclassQueueX{privatefinalintSIZE=20;privateint[]queArray;privateintfront;privateintrear;publicQueueX(){queArray=newint[SIZE];front=0;rear=-1;}publicvoidinsert(intj){if(rear==SIZE-1)rear=-1;queArray[++rear]=j;}publicintremove(){inttemp=queArray[front++];if(front==SIZE){front=0;}returntemp;}publicbooleanisEmpty(){return(rear+1==front||front+SIZE-1==rear);}}图代码Graph.class：
packagetestOffer.graphpro;publicclassGraph{privatefinalintMAX_VERTS=20;//表示顶点的个数privateVertexvertexList[];//用来存储顶点的数组privateintadjMat[][];//用邻接矩阵来存储边，数组元素表示没有边界，1表示有边界privateintnVerts;//顶点个数privateStackXtheStack;//用栈实现深度优先搜索privateQueueXqueue;//用队列实现广度优先搜索/***顶点类**/classVertex{publiccharlabel;publicbooleanwasVisited;publicVertex(charlabel){this.label=label;wasVisited=false;}}publicGraph(){vertexList=newVertex[MAX_VERTS];adjMat=newint[MAX_VERTS][MAX_VERTS];nVerts=0;//初始化顶点个数为0//初始化邻接矩阵所有元素都为0，即所有顶点都没有边for(inti=0;i