Java是一種廣泛應用于各種領域的編程語言,其中包括了一些常見的搜索算法。其中,深度優先搜索(DFS)和廣度優先搜索(BFS)是兩種常用的算法。
深度優先搜索的核心是遞歸,通過不斷遞歸到子節點,然后回溯,繼續搜索。可以使用棧來實現 DFS。下面是使用Java實現DFS的一個簡單例子。
public class DFS { boolean visited[]; public void dfs(int node, List>adj) { visited[node] = true; for (int i = 0; i< adj.get(node).size(); i++) { int neighbor = adj.get(node).get(i); if (!visited[neighbor]) { dfs(neighbor, adj); } } } }
這里,我們使用了一個布爾數組作為訪問標記。對于每個節點,我們先將它標記為已訪問,然后遞歸查找所有未訪問的子節點。
而廣度優先搜索則是通過隊列實現的。從源節點開始,將它的所有鄰居節點加入隊列中,然后依次從隊列中取出每個節點做同樣的操作,直到遍歷完整張圖。下面是使用Java實現BFS的一個簡單例子。
import java.util.*; public class BFS { boolean visited[]; public void bfs(int start, List>adj) { Queue
queue = new LinkedList<>(); visited[start] = true; queue.add(start); while (!queue.isEmpty()) { int node = queue.poll(); for (int i = 0; i< adj.get(node).size(); i++) { int neighbor = adj.get(node).get(i); if (!visited[neighbor]) { visited[neighbor] = true; queue.add(neighbor); } } } } }
這里,我們使用了一個布爾數組來標記每個節點是否已經被訪問,并用一個隊列存儲待訪問的節點。從源節點開始,依次處理隊列中的所有節點,并將它們的鄰居加入隊列中。不斷循環直到隊列為空,表示遍歷完成。