## 图的遍历  ### 深度优先遍历dfs 1. 利用栈实现 2. 从初始顶点开始把节点按深度放入栈，然后弹出 3. 每弹出一个顶点，把该顶点的下一个没有进过栈的邻接点放入栈 4. 直到栈变空 ~~~ /** * 图的dfs遍历，深度优先遍历 * 用栈实现 * @param vertex 初始顶点 * @return */ public Set<Vertex> dfs(Vertex vertex){ Set<Vertex> result = new LinkedHashSet<>(); Stack<Vertex> stack = new Stack<>(); Set<Vertex> pass = new HashSet<>(); // 将初始顶点加入到栈和路过的集合pass里 stack.add(vertex); pass.add(vertex); result.add(vertex); // 处理栈 while (!stack.isEmpty()){ Vertex cur = stack.pop(); // 处理相邻的顶点 for(Vertex next : cur.nexts){ // 不在pass里的 if(!pass.contains(next)){ // 记录到pass里 pass.add(next); // 先将原来节点压入到栈里 stack.add(cur); stack.add(next); // 找到一个就退出 result.add(next); break; } } } return result; } ~~~ ``` dfs:1->2->4->3->5-> ``` ### 宽度优先遍历bfs 1. 利用队列实现 2. 从初始顶点开始依次按照宽度进队列，然后弹出 3. 每弹出一个顶点，把该顶点所有没有进过队列的邻接顶点放入队列 4. 直到队列变空 ~~~ /** * 图的宽度优先遍历，bfs，用队列 * @param vertex 初始顶点 * @return */ public Set<Vertex> bfs(Vertex vertex){ Set<Vertex> result = new LinkedHashSet<>(); Queue<Vertex> queue = new LinkedList<>(); Set<Vertex> pass = new HashSet<>(); queue.offer(vertex); pass.add(vertex); // 处理队列 while (!queue.isEmpty()){ Vertex cur = queue.poll(); result.add(cur); // 处理相邻节点 for(Vertex next : cur.nexts){ if(!pass.contains(next)){ queue.offer(next); pass.add(next); } } } return result; } ~~~