廣度優(yōu)先和深度優(yōu)先是兩種常見的基本算法。在Java程序設(shè)計(jì)中，二者均有重要應(yīng)用。

廣度優(yōu)先算法

廣度優(yōu)先算法，也稱為“寬度優(yōu)先搜索”，是通過搜索算法遍歷查找樹或圖的一種方式，它從根節(jié)點(diǎn)開始，依次訪問每個(gè)相鄰節(jié)點(diǎn)，并逐層地向下搜索。廣度優(yōu)先算法的實(shí)現(xiàn)可以采用隊(duì)列數(shù)據(jù)結(jié)構(gòu)。

/**
* 廣度優(yōu)先搜索
* @param graph 圖
* @param start 起點(diǎn)
* @param end 終點(diǎn)
*/
public void bfs(int[][] graph, int start, int end) {
Queuequeue = new LinkedList<>(); //隊(duì)列保存當(dāng)前層節(jié)點(diǎn)
boolean[] visited = new boolean[graph.length]; //記錄已訪問節(jié)點(diǎn)
queue.offer(start);
visited[start] = true;
int level = 0; //層數(shù)
while (!queue.isEmpty()) {
int size = queue.size();
level++;
for (int i = 0; i< size; i++) {
int curr = queue.poll();
for (int j = 0; j< graph.length; j++) {
if (graph[curr][j] != 0 && !visited[j]) {
if (j == end) {
System.out.println("找到終點(diǎn)，距離為：" + level);
return;
}
queue.offer(j);
visited[j] = true;
}
}
}
}
System.out.println("未找到終點(diǎn)");
}

深度優(yōu)先算法

深度優(yōu)先算法，也稱為“深度優(yōu)先搜索”，是從一個(gè)子節(jié)點(diǎn)開始，不斷向下遍歷每一個(gè)分支，直到遇到?jīng)]有未被訪問的分支，此時(shí)回溯到上一個(gè)節(jié)點(diǎn)，重復(fù)以上操作，直至遍歷完整個(gè)樹或圖。深度優(yōu)先算法的實(shí)現(xiàn)可以采用遞歸、棧等數(shù)據(jù)結(jié)構(gòu)。

/**
* 深度優(yōu)先搜索
* @param graph 圖
* @param start 起點(diǎn)
* @param end 終點(diǎn)
*/
public void dfs(int[][] graph, int start, int end) {
boolean[] visited = new boolean[graph.length]; //記錄已訪問節(jié)點(diǎn)
dfsHelper(graph, start, end, visited, 0);
}
/**
* 深度優(yōu)先搜索的輔助方法
*/
private void dfsHelper(int[][] graph, int curr, int end, boolean[] visited, int depth) {
visited[curr] = true;
if (curr == end) {
System.out.println("找到終點(diǎn)，距離為：" + depth);
return;
}
for (int i = 0; i< graph.length; i++) {
if (graph[curr][i] != 0 && !visited[i]) {
dfsHelper(graph, i, end, visited, depth + 1);
}
}
}

在實(shí)際應(yīng)用中，廣度優(yōu)先算法通常適用于搜索最短路徑，如迷宮問題、網(wǎng)頁抓取等。而深度優(yōu)先算法通常適用于搜索全部路徑或狀態(tài)，如八皇后問題、數(shù)獨(dú)問題等。