目录
图的遍历简介
广度优先搜索算法
算法的思想
算法实现的思想
算法的复杂度
深度优先搜索算法
算法的思想
算法实现的思想
算法的复杂度
java实现
图的基础java代码
广度优先算法
深度优先算法
测试
图的遍历是指从图中的任一顶点出发，对图中的所有顶点访问一次并且只访问一次。图的遍历是图的一种基本操作，图中的许多其他操作也都是建立在遍历的基础之上。在图中，没有特殊的顶点被指定为起始顶点，图的遍历可以从任何顶点开始。图的遍历主要有深度优先搜索和广度优先搜索两种方式。
从图中的某一个顶点x出发，访问x，然后访问与x所相邻的所有未被访问的顶点x1、x2……xn，接着再依次访问与x1、x2……xn相邻的未被访问的所有顶点。依次类推，直至图中的每个顶点都被访问。
广度优先遍历背后基于队列，下面介绍一下具体实现的方法：
访问起始顶点，并将插入队列； 从队列中删除队头顶点，将与其相邻的所有的未被访问的顶点插入队列中； 重复第二步，直至队列为空。 未被访问的顶点怎么识别呢？利用顶点的isVisited属性来进行标记。
同时还需要另一个队列（或者是list）用来保存访问的顺序，另一个队列的顶点入队顺序就是图的广度遍历顺序，因此，该队列保持 与 前一个队列的顶点入队操作 一致。由于前一个队列是辅助遍历的，它有出队的操作，它就不能记录整个顶点的访问序列了，因此才需要一个保存访问顺序的队列。当整个过程遍历完成后，将 保存访问顺序的队列 进行出队操作，即可得到整个图的广度优先遍历的顺序了。
该算法的时间复杂度为--遍历之前，给每个顶点进行初始化时需要遍历所有顶点V，在遍历过程中需要判断顶点的邻接点是否被遍历，也即遍历该顶点的邻接表，邻接表代表的实质是边，边总数为E，故总的时间复杂度为O(V+E)，空间复杂度为O(V)--辅助队列的长度为顶点的长度
从图中的某一个顶点x出发，访问x，然后遍历任何一个与x相邻的未被访问的顶点y，再遍历任何一个与y相邻的未被访问的顶点z……依次类推，直到到达一个所有邻接点都被访问的顶点为止；然后，依次回退到尚有邻接点未被访问过的顶点，重复上述过程，直到图中的全部顶点都被访问过为止。
深度优先遍历背后基于堆栈，有两种方式：第一种是在程序中显示构造堆栈，利用压栈出栈操作实现；第二种是利用递归函数调用，基于递归程序栈实现。本文介绍第一种方式：
访问起始顶点，并将其压入栈中； 从栈中弹出最上面的顶点，将与其相邻的未被访问的顶点压入栈中；当深度优先遍历到某个顶点时，若该顶点的所有邻接点均已经被访问，则发生回溯，即返回去遍历 该顶点 的 前驱顶点 的 未被访问的某个邻接点。（相当于没有把新的节点压入栈中，下一个被访问的节点是当前节点下面的节点） 重复第二步，直至栈为空栈。 未被访问的顶点怎么识别呢？利用顶点的isVisited属性来进行标记。
对于深度优先而言，访问了 顶点A 时，紧接着只需要找到 顶点A 的一个未被访问的邻接点，再访问该邻接点即可。而对于广度优先，访问了 顶点A 时，就是要寻找 顶点A的 所有未被访问的邻接点，再访问 所有的这些邻接点。
同时还需要另一个队列（或者是list）用来保存访问的顺序
深度优先遍历的算法的时间复杂度：O(V+E)--遍历之前，给每个顶点进行初始化时需要遍历所有顶点V，在遍历过程中需要判断顶点的邻接点是否被遍历，也即遍历该顶点的邻接表，邻接表代表的实质是边，边总数为 E，故总的时间复杂度为O(V+E)；空间复杂度：O(V)--用了一个栈，一个list
可以参考 https://blog.csdn.net/xushiyu1996818/article/details/90373591
深度优先与广度优先不同的是
广度优先遇到一个顶点，让它出队列，然后把它所有的未被访问的节点入队列
而深度优先，遇到一个顶点，只是先获得它，并不出栈（因为要多次利用它），然后把它的第一个未被访问的节点入队列。
如果没有相邻的未被访问的顶点，才把这个顶点出栈
/** 深度优先遍历图，以origin作为标识的顶点作为起始点 * @param origin * @return 返回一个list，其中元素为广度遍历到的顶点，顺序为深度遍历的顺序 * 如果队列中没有以origin作为标识的顶点，返回一个空的list */ public List<Vertex<T>> depthFirstTraversal(T origin){ //清除状态 clearVisitStatus(); //这个是深度遍历的栈 Stack<Vertex<T>> stack=new Stack<>(); //这个是返回的list，用来存储深度遍历到的顶点 List<Vertex<T>> result=new LinkedList<>(); Vertex<T> vertex=vertexMap.get(origin); if(vertex==null){ //如果队列中没有以origin作为标识的顶点，返回一个空的list System.out.println("没有找到顶点"+origin); return result; } //以origin作为标识的顶点作为起始点 stack.push(vertex); //result里用来存储深度遍历到的顶点,由于深度遍历，一个节点可能被访问多次，所以在入栈时操作 result.add(vertex); //将这个顶点设置为已访问,访问状态在加入队列时设置 vertex.visit(); while(!stack.isEmpty()){ vertex=stack.peek(); System.out.println("遍历到顶点:"+vertex.getLabel()); //获得以这个顶点为出发点，相邻的第一个没有被访问的顶点 Vertex other=vertex.getUnvisitedVertex(); if(other==null){ //如果没找到，那么vertex就退出栈，让下一个被访问 stack.pop(); System.out.println("顶点:"+vertex.getLabel()+" ,没有找到未访问过的顶点，出栈"); } else{ //如果找到了，就让other顶点入栈，vertex还留在这里，下一个被访问的是other other.visit(); stack.push(other); //result里用来存储深度遍历到的顶点,由于深度遍历，一个节点可能被访问多次，所以在入栈时操作 result.add(other); System.out.println("从顶点:"+vertex.getLabel()+" ,找到未访问过的顶点:"+other.getLabel()); } } System.out.println(); return result; }