## 圖的遍歷  ### 深度優先遍歷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; } ~~~