在Java編程中,常常會用到廣度優先搜索和深度優先搜索。這兩種搜索算法都有各自的特點和應用場景。
廣度優先搜索(BFS)是從根節點開始,沿著樹的寬度遍歷每個節點。先訪問距離根節點最近的節點,然后是次近的,依次往外訪問。BFS通常使用隊列來實現,用來表示待訪問的節點序列。
Queue queue = new LinkedList();
queue.add(root);
while (!queue.isEmpty()) {
Node node = queue.poll();
//對node節點進行操作
for (Node next : node.children) {
queue.add(next);
}
}
深度優先搜索(DFS)則是優先遍歷每個節點的深度,盡可能沿著某個子樹往下遍歷,直到達到末端節點后再返回來遍歷其他兄弟節點。DFS通常使用遞歸或棧來實現,用來表示待訪問的節點序列。
Stack stack = new Stack();
stack.push(root);
while (!stack.isEmpty()) {
Node node = stack.pop();
//對node節點進行操作
for (Node next : node.children) {
stack.push(next);
}
}
BFS和DFS的應用場景不同。BFS通常用于求最短路徑,如八數碼問題、迷宮問題等。DFS則通常用于遍歷問題,如查找二叉樹中的節點、連通圖問題等。
總的來說,BFS和DFS都是常見的搜索算法,需要根據具體情況選擇適合的算法進行使用。