图的遍历（深度优先，广度优先）总结-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
java实现
图的基础java代码
可以参考 https://blog.csdn.net/xushiyu1996818/article/details/90373591
广度优先算法
/**
* 将图中所有节点的isVisited属性变成false
*/
public void clearVisitStatus(){
Iterator<Vertex<T>> iteratorVertex=getVertexIterator();
while(iteratorVertex.hasNext()){
Vertex<T> vertex=iteratorVertex.next();
vertex.unVisit();
}
}
/** 广度优先遍历图，以origin作为标识的顶点作为起始点
* @param origin
* @return 返回一个list，其中元素为广度遍历到的顶点，顺序为广度遍历的顺序
* 如果队列中没有以origin作为标识的顶点，返回一个空的list
*/
public List<Vertex<T>> breathFirstTraversal(T origin){
//清除状态
clearVisitStatus();
//这个是广度遍历的队列
Queue<Vertex<T>> queue=new LinkedList<>();
//这个是返回的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作为标识的顶点作为起始点
queue.offer(vertex);
//将这个顶点设置为已访问,访问状态在加入队列时设置
vertex.visit();
while(!queue.isEmpty()){
vertex=queue.poll();
//result里用来存储广度遍历到的顶点
result.add(vertex);
System.out.println("遍历到顶点:"+vertex.getLabel());
Iterator<Edge> edgeIterator=vertex.getEdgeIterator();
while(edgeIterator.hasNext()){
Edge edge=edgeIterator.next();
Vertex other=edge.getEndVertex();
if(!other.isVisited()){
queue.offer(other);
//将这个顶点设置为已访问,访问状态在加入队列时设置
vertex.visit();
System.out.println("从顶点:"+vertex.getLabel()+" ,找到未访问过的顶点:"+other.getLabel());
}
}
}
return result;
}深度优先算法
深度优先与广度优先不同的是
广度优先遇到一个顶点，让它出队列，然后把它所有的未被访问的节点入队列
而深度优先，遇到一个顶点，只是先获得它，并不出栈（因为要多次利用它），然后把它的第一个未被访问的节点入队列。
如果没有相邻的未被访问的顶点，才把这个顶点出栈
/** 深度优先遍历图，以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;
}测试
package datastructure.graph.adjacencymatrixgraph;
public class Main {
public static void main(String[] args) {
Graph<String> graph=new Graph<>(false);
graph.addVertex("first", 0);
graph.addVertex("second", 0);
graph.addVertex("third", 0);
graph.addVertex("fourth", 0);
graph.addEdge("first", "second", 1);
graph.addEdge("first", "third", 2);
graph.addEdge("fourth", "third", 2);
graph.printGraph();
graph.breathFirstTraversal("first");
graph.depthFirstTraversal("first");
}
}