网站建设知识点佛山企业网站建设公司推荐

网站建设知识点,佛山企业网站建设公司推荐,怎样查企业注册信息查询,wordpress如何返回之前更新的版本思路#xff1a;深度优先搜索的基础题目。1.确认递归函数和参数#xff1a;#xff08;1#xff09;首先需要存一个用来遍历的图。#xff08;2#xff09;存一个当前遍历的节点#xff0c;定义为x。#xff08;3#xff09;需要存一个n表示终点。在遍历的时候#x…思路深度优先搜索的基础题目。1.确认递归函数和参数1首先需要存一个用来遍历的图。2存一个当前遍历的节点定义为x。3需要存一个n表示终点。在遍历的时候当x n时表明找到了终点。4单一路径和路径集合可以放在全局变量。vectorvectorint result; // 收集符合条件的路径 vectorint path; // 0节点到终点的路径 // x目前遍历的节点 // graph存当前的图 // n终点 void dfs (const vectorvectorint graph, int x, int n) {2.确认终止条件当当前遍历的节点为节点n的时候就找到了一条从出发点到终止点的路径。// 当前遍历的节点x 到达节点n if (x n) { // 找到符合条件的一条路径 result.push_back(path); return; }3.处理当前搜索节点出发的路径接下来是走当前遍历节点x的下一个节点。1首先要找到x节点指向了哪些节点遍历方式如下for (int i 1; i n; i) { // 遍历节点x链接的所有节点 if (graph[x][i] 1) { // 找到 x指向的节点就是节点i } }2接下来就是将选中的x所指向的节点加入到单一路径来。path.push_back(i); // 遍历到的节点加入到路径中来3进入下一层递归。dfs(graph, i, n); // 进入下一层递归4最后就是回溯的过程撤销本次添加节点的操作。5该过程的整体代码如下所示for (int i 1; i n; i) { // 遍历节点x链接的所有节点 if (graph[x][i] 1) { // 找到 x链接的节点 path.push_back(i); // 遍历到的节点加入到路径中来 dfs(graph, i, n); // 进入下一层递归 path.pop_back(); // 回溯撤销本节点 } }附代码一邻接表写法class Solution { public ListListInteger allPathsSourceTarget(int[][] graph) { // 从0到1暴力搜索即可 ListListInteger res new ArrayList(); ListInteger path new ArrayList(); path.add(0); //将起始节点0加入路径 dfs(res,path,graph,0,graph.length); return res; } private void dfs(ListListInteger res,ListInteger path,int[][] graph,int x,int n){ //找到一条符合条件的路径 if(x n - 1){ res.add(new ArrayList(path)); return; } for(int i : graph[x]){ //寻找x指向的节点 path.add(i); //遍历到的节点加入到路径上来 dfs(res,path,graph,i,n); //进入下一层递归 path.remove(path.size() - 1); //回溯撤销本节点 //path.removeLast(); } } }二邻接矩阵写法class Solution { public ListListInteger allPathsSourceTarget(int[][] graph) { ListListInteger res new ArrayList(); ListInteger path new ArrayList(); // 初始化邻接矩阵 int n graph.length; boolean[][] adjMatrix new boolean[n][n]; //因为Leetcode给的是邻接表格式所以需要手动将邻接表转换为邻接矩阵 //根据输入构建邻接矩阵 for (int i 0; i n; i) { for (int neighbor : graph[i]) { adjMatrix[i][neighbor] true; } } // 将起始节点0加入路径 path.add(0); dfs(res, path, adjMatrix, 0, n); return res; } private void dfs(ListListInteger res, ListInteger path, boolean[][] adjMatrix, int x, int n) { //找到一条符合条件的路径 if (x n - 1) { res.add(new ArrayList(path)); return; } // 遍历所有可能的邻居节点 for (int i 0; i n; i) { if (adjMatrix[x][i]) { // 如果存在从x到i的边 path.add(i); //遍历到的节点i加入到路径上来 dfs(res, path, adjMatrix, i, n); //进入下一层递归 path.remove(path.size() - 1); //回溯撤销本节点 } } } }