图论01-DFS和BFS(深搜和广搜邻接矩阵和邻接表/Java)

1.深度优先理论基础(dfs)

• dfs的两个关键操作

搜索方向，是认准一个方向搜，直到碰壁之后再换方向
换方向是撤销原路径，改为节点链接的下一个路径，回溯的过程。

• dfs解题模板

void dfs(参数) {if (终止条件) {存放结果;return;}for (选择：本节点所连接的其他节点) {处理节点;dfs(图，选择的节点); // 递归回溯，撤销处理结果}
}

• Java代码实现

邻接矩阵表示的图

public class DFSTraversalRecursive {private int[][] adjacencyMatrix; // 邻接矩阵private boolean[] visited; // 用于标记节点是否被访问过private int numNodes; // 节点数量public DFSTraversalRecursive(int[][] matrix) {this.adjacencyMatrix = matrix;this.numNodes = matrix.length;this.visited = new boolean[numNodes];}// 递归实现的深度优先搜索遍历public void dfsTraversalRecursive(int startNode) {visited[startNode] = true; // 标记当前节点为已访问System.out.print(startNode + " "); // 输出当前节点for (int i = 0; i < numNodes; i++) {// 如果存在从当前节点到节点 i 的边，并且节点 i 还未被访问过if (adjacencyMatrix[startNode][i] == 1 && !visited[i]) {dfsTraversalRecursive(i); // 递归调用，从节点 i 开始深度优先搜索}}}
}

邻接表表示的图

public class DFSTraversalAdjacencyList {private List<List<Integer>> adjacencyList; // 邻接表存储图的结构private boolean[] visited; // 标记节点是否被访问过// 构造函数，初始化邻接表和visited数组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);}// 递归实现的深度优先搜索遍历public void dfsTraversalRecursive(int startNode) {visited[startNode] = true; // 标记当前节点为已访问System.out.print(startNode + " "); // 输出当前节点// 遍历当前节点的所有邻居节点for (int neighbor : adjacencyList.get(startNode)) {if (!visited[neighbor]) {dfsTraversalRecursive(neighbor); // 递归调用，从邻居节点开始深度优先搜索}}}

2.广度优先搜索理论基础(bfs)

• 使用场景

广搜的搜索方式就适合于解决两个点之间的最短路径问题。因为广搜是从起点出发，以起始点为中心一圈一圈进行搜索，一旦遇到终点，记录之前走过的节点就是一条最短路

• Java代码实现

邻接矩阵表示的图

public class BFSTraversalAdjacencyMatrix {private int[][] adjacencyMatrix; // 邻接矩阵存储图的结构private boolean[] visited; // 标记节点是否被访问过public BFSTraversalAdjacencyMatrix(int numNodes) {this.adjacencyMatrix = new int[numNodes][numNodes]; // 初始化邻接矩阵this.visited = new boolean[numNodes]; // 初始化visited数组}// 添加边到邻接矩阵public void addEdge(int source, int destination) {adjacencyMatrix[source][destination] = 1;}// 广度优先搜索遍历public void bfsTraversal(int startNode) {Queue<Integer> queue = new LinkedList<>(); // 创建一个队列用于BFS遍历queue.add(startNode); // 将起始节点加入队列visited[startNode] = true; // 标记起始节点为已访问while (!queue.isEmpty()) {int currentNode = queue.poll(); // 出队列一个节点System.out.print(currentNode + " "); // 输出当前节点for (int i = 0; i < adjacencyMatrix.length; i++) {if (adjacencyMatrix[currentNode][i] == 1 && !visited[i]) {queue.add(i); // 将未访问的邻居节点加入队列visited[i] = true; // 标记邻居节点为已访问}}}}
}

邻接表表示的图

public class BFSTraversalAdjacencyList {private LinkedList<Integer>[] adjacencyList; // 邻接表存储图的结构private boolean[] visited; // 标记节点是否被访问过public BFSTraversalAdjacencyList(int numNodes) {// 初始化邻接表this.adjacencyList = new LinkedList[numNodes];for (int i = 0; i < numNodes; i++) {adjacencyList[i] = new LinkedList<Integer>();}// 初始化visited数组this.visited = new boolean[numNodes];}// 添加边到邻接表public void addEdge(int source, int destination) {adjacencyList[source].add(destination);}// 广度优先搜索遍历public void bfsTraversal(int startNode) {Queue<Integer> queue = new LinkedList<>(); // 创建一个队列用于BFS遍历queue.add(startNode); // 将起始节点加入队列visited[startNode] = true; // 标记起始节点为已访问while (!queue.isEmpty()) {int currentNode = queue.poll(); // 出队列一个节点System.out.print(currentNode + " "); // 输出当前节点for (int neighbor : adjacencyList[currentNode]) {if (!visited[neighbor]) {queue.add(neighbor); // 将未访问的邻居节点加入队列visited[neighbor] = true; // 标记邻居节点为已访问}}}}
}