Java中的廣度優先搜索和深度優先搜索是兩種常用的搜索算法,它們可以用于圖形遍歷、迷宮求解和尋路等應用。兩種算法的實現方式略有不同,但本質上都是通過遞歸或非遞歸的方式遍歷圖形節點。
/** * 廣度優先搜索實現 */ public void BFS(int start) { Queuequeue = new LinkedList<>(); boolean[] visited = new boolean[V]; visited[start] = true; queue.add(start); while (!queue.isEmpty()) { int current = queue.poll(); System.out.print(current + " "); for (int v : adj[current]) { if (!visited[v]) { visited[v] = true; queue.add(v); } } } }
代碼中,我們使用一個隊列和一個布爾類型的數組visited來實現廣度優先搜索。visited數組用來記錄每個節點是否已被訪問過,隊列用于存儲待訪問的節點。首先將起點標記為已訪問,并加入隊列中。然后開始循環,從隊列中取出一個節點并輸出,再將其未訪問的鄰居節點加入隊列中,并將其標記為已訪問。
/** * 深度優先搜索實現 */ public void DFS(int start) { boolean[] visited = new boolean[V]; DFSHelper(start, visited); } private void DFSHelper(int current, boolean[] visited) { visited[current] = true; System.out.print(current + " "); for (int v : adj[current]) { if (!visited[v]) { DFSHelper(v, visited); } } }
代碼中,我們使用一個布爾類型的數組visited來記錄每個節點是否已被訪問過。首先將起點標記為已訪問,并輸出。然后遞歸遍歷當前節點的所有未訪問的鄰居節點,直到所有可達節點都被訪問過。
廣度優先搜索和深度優先搜索都有其優缺點。廣度優先搜索在空間占用方面較高,但能夠保證找到最短路徑。深度優先搜索則相反,但在空間占用方面較低,且能夠快速找到一條可行路徑。
下一篇php 26個字母