1.深度優(yōu)先理論基礎(chǔ)(dfs)

• dfs的兩個(gè)關(guān)鍵操作

搜索方向，是認(rèn)準(zhǔn)一個(gè)方向搜，直到碰壁之后再換方向
換方向是撤銷原路徑，改為節(jié)點(diǎn)鏈接的下一個(gè)路徑，回溯的過程。

• dfs解題模板

void dfs(參數(shù)) {if (終止條件) {存放結(jié)果;return;}for (選擇：本節(jié)點(diǎn)所連接的其他節(jié)點(diǎn)) {處理節(jié)點(diǎn);dfs(圖，選擇的節(jié)點(diǎn)); // 遞歸回溯，撤銷處理結(jié)果}
}

• Java代碼實(shí)現(xiàn)

鄰接矩陣表示的圖

public class DFSTraversalRecursive {private int[][] adjacencyMatrix; // 鄰接矩陣private boolean[] visited; // 用于標(biāo)記節(jié)點(diǎn)是否被訪問過private int numNodes; // 節(jié)點(diǎn)數(shù)量public DFSTraversalRecursive(int[][] matrix) {this.adjacencyMatrix = matrix;this.numNodes = matrix.length;this.visited = new boolean[numNodes];}// 遞歸實(shí)現(xiàn)的深度優(yōu)先搜索遍歷public void dfsTraversalRecursive(int startNode) {visited[startNode] = true; // 標(biāo)記當(dāng)前節(jié)點(diǎn)為已訪問System.out.print(startNode + " "); // 輸出當(dāng)前節(jié)點(diǎn)for (int i = 0; i < numNodes; i++) {// 如果存在從當(dāng)前節(jié)點(diǎn)到節(jié)點(diǎn) i 的邊，并且節(jié)點(diǎn) i 還未被訪問過if (adjacencyMatrix[startNode][i] == 1 && !visited[i]) {dfsTraversalRecursive(i); // 遞歸調(diào)用，從節(jié)點(diǎn) i 開始深度優(yōu)先搜索}}}
}

鄰接表表示的圖

public class DFSTraversalAdjacencyList {private List<List<Integer>> adjacencyList; // 鄰接表存儲(chǔ)圖的結(jié)構(gòu)private boolean[] visited; // 標(biāo)記節(jié)點(diǎn)是否被訪問過// 構(gòu)造函數(shù)，初始化鄰接表和visited數(shù)組public DFSTraversalAdjacencyList(int numNodes) {this.adjacencyList = new ArrayList<>();for (int i = 0; i < numNodes; i++) {this.adjacencyList.add(new ArrayList<>());}this.visited = new boolean[numNodes];}// 添加邊到鄰接表public void addEdge(int source, int destination) {adjacencyList.get(source).add(destination);}// 遞歸實(shí)現(xiàn)的深度優(yōu)先搜索遍歷public void dfsTraversalRecursive(int startNode) {visited[startNode] = true; // 標(biāo)記當(dāng)前節(jié)點(diǎn)為已訪問System.out.print(startNode + " "); // 輸出當(dāng)前節(jié)點(diǎn)// 遍歷當(dāng)前節(jié)點(diǎn)的所有鄰居節(jié)點(diǎn)for (int neighbor : adjacencyList.get(startNode)) {if (!visited[neighbor]) {dfsTraversalRecursive(neighbor); // 遞歸調(diào)用，從鄰居節(jié)點(diǎn)開始深度優(yōu)先搜索}}}

2.廣度優(yōu)先搜索理論基礎(chǔ)(bfs)

• 使用場景

廣搜的搜索方式就適合于解決兩個(gè)點(diǎn)之間的最短路徑問題。因?yàn)閺V搜是從起點(diǎn)出發(fā)，以起始點(diǎn)為中心一圈一圈進(jìn)行搜索，一旦遇到終點(diǎn)，記錄之前走過的節(jié)點(diǎn)就是一條最短路

• Java代碼實(shí)現(xiàn)

鄰接矩陣表示的圖

public class BFSTraversalAdjacencyMatrix {private int[][] adjacencyMatrix; // 鄰接矩陣存儲(chǔ)圖的結(jié)構(gòu)private boolean[] visited; // 標(biāo)記節(jié)點(diǎn)是否被訪問過public BFSTraversalAdjacencyMatrix(int numNodes) {this.adjacencyMatrix = new int[numNodes][numNodes]; // 初始化鄰接矩陣this.visited = new boolean[numNodes]; // 初始化visited數(shù)組}// 添加邊到鄰接矩陣public void addEdge(int source, int destination) {adjacencyMatrix[source][destination] = 1;}// 廣度優(yōu)先搜索遍歷public void bfsTraversal(int startNode) {Queue<Integer> queue = new LinkedList<>(); // 創(chuàng)建一個(gè)隊(duì)列用于BFS遍歷queue.add(startNode); // 將起始節(jié)點(diǎn)加入隊(duì)列visited[startNode] = true; // 標(biāo)記起始節(jié)點(diǎn)為已訪問while (!queue.isEmpty()) {int currentNode = queue.poll(); // 出隊(duì)列一個(gè)節(jié)點(diǎn)System.out.print(currentNode + " "); // 輸出當(dāng)前節(jié)點(diǎn)for (int i = 0; i < adjacencyMatrix.length; i++) {if (adjacencyMatrix[currentNode][i] == 1 && !visited[i]) {queue.add(i); // 將未訪問的鄰居節(jié)點(diǎn)加入隊(duì)列visited[i] = true; // 標(biāo)記鄰居節(jié)點(diǎn)為已訪問}}}}
}

鄰接表表示的圖

public class BFSTraversalAdjacencyList {private LinkedList<Integer>[] adjacencyList; // 鄰接表存儲(chǔ)圖的結(jié)構(gòu)private boolean[] visited; // 標(biāo)記節(jié)點(diǎn)是否被訪問過public BFSTraversalAdjacencyList(int numNodes) {// 初始化鄰接表this.adjacencyList = new LinkedList[numNodes];for (int i = 0; i < numNodes; i++) {adjacencyList[i] = new LinkedList<Integer>();}// 初始化visited數(shù)組this.visited = new boolean[numNodes];}// 添加邊到鄰接表public void addEdge(int source, int destination) {adjacencyList[source].add(destination);}// 廣度優(yōu)先搜索遍歷public void bfsTraversal(int startNode) {Queue<Integer> queue = new LinkedList<>(); // 創(chuàng)建一個(gè)隊(duì)列用于BFS遍歷queue.add(startNode); // 將起始節(jié)點(diǎn)加入隊(duì)列visited[startNode] = true; // 標(biāo)記起始節(jié)點(diǎn)為已訪問while (!queue.isEmpty()) {int currentNode = queue.poll(); // 出隊(duì)列一個(gè)節(jié)點(diǎn)System.out.print(currentNode + " "); // 輸出當(dāng)前節(jié)點(diǎn)for (int neighbor : adjacencyList[currentNode]) {if (!visited[neighbor]) {queue.add(neighbor); // 將未訪問的鄰居節(jié)點(diǎn)加入隊(duì)列visited[neighbor] = true; // 標(biāo)記鄰居節(jié)點(diǎn)為已訪問}}}}
}