【代码随想录Day48】图论Part01

图论理论基础

题目链接/文章讲解：图论理论基础 | 代码随想录

深搜理论基础

题目链接/文章讲解：深度优先搜索理论基础 | 代码随想录

98. 所有可达路径

题目链接/文章讲解：代码随想录

class Solution {// 存储所有从源节点到目标节点的路径List<List<Integer>> result = new ArrayList<>();// 存储当前路径的节点List<Integer> path = new LinkedList<>();// 主函数，接收图的邻接矩阵并开始深度优先搜索public List<List<Integer>> allPathsSourceTarget(int[][] graph) {// 从源节点（节点0）开始，添加到当前路径中path.add(0);// 调用DFS函数，开始搜索路径dfs(graph, 0);// 返回所有找到的路径return result;}// 深度优先搜索函数public void dfs(int[][] graph, int startIndex) {// 如果当前节点是目标节点（最后一个节点），则将当前路径添加到结果中if (startIndex == graph.length - 1) {result.add(new ArrayList<>(path)); // 将当前路径的副本添加到结果return; // 结束当前递归}// 遍历当前节点的所有邻接节点for (int i = 0; i < graph[startIndex].length; i++) {// 将邻接节点添加到当前路径path.add(graph[startIndex][i]);// 递归调用DFS，继续搜索下一个节点dfs(graph, graph[startIndex][i]);// 回溯：从当前路径中移除最后添加的节点path.removeLast();}}
}

广搜理论基础

题目链接/文章讲解：广度优先搜索理论基础 | 代码随想录