代码随想录算法训练营第四十九天|图论深搜和广搜理论基础、卡码网98 可达路径

参考文章均来自代码随想录之前离散数学学了有关图的基础知识 又过了一遍后续忘记查看参考文章即可参考文章链接深度优先搜索理论基础广度优先搜索理论基础卡码网98 可达路径题目链接主要掌握邻接矩阵和邻接表的手搓感觉分析过程和回溯差不多 之前确实没怎过做过图 直接照抄代码了 后面要多理解理解还要注意ACM模式的输入输出邻接矩阵法#includeiostream#includevectorusingnamespacestd;vectorvectorintresult;// 收集符合条件的路径vectorintpath;// 1节点到终点的路径voiddfs(constvectorvectorintgraph,intx,intn){// 当前遍历的节点x 到达节点nif(xn){// 找到符合条件的一条路径result.push_back(path);return;}for(inti1;in;i){// 遍历节点x链接的所有节点if(graph[x][i]1){// 找到 x链接的节点path.push_back(i);// 遍历到的节点加入到路径中来dfs(graph,i,n);// 进入下一层递归path.pop_back();// 回溯撤销本节点}}}intmain(){intn,m,s,t;cinnm;// 节点编号从1到n所以申请 n1 这么大的数组vectorvectorintgraph(n1,vectorint(n1,0));while(m--){cinst;// 使用邻接矩阵 表示无线图1 表示 s 与 t 是相连的graph[s][t]1;}path.push_back(1);// 无论什么路径已经是从0节点出发dfs(graph,1,n);// 开始遍历// 输出结果if(result.size()0)cout-1endl;for(constvectorintpa:result){for(inti0;ipa.size()-1;i){coutpa[i] ;}coutpa[pa.size()-1]endl;}}邻接表法#includeiostream#includevector#includelistusingnamespacestd;vectorvectorintresult;// 收集符合条件的路径vectorintpath;// 1节点到终点的路径voiddfs(constvectorlistintgraph,intx,intn){if(xn){// 找到符合条件的一条路径result.push_back(path);return;}for(inti:graph[x]){// 找到 x指向的节点path.push_back(i);// 遍历到的节点加入到路径中来dfs(graph,i,n);// 进入下一层递归path.pop_back();// 回溯撤销本节点}}intmain(){intn,m,s,t;cinnm;// 节点编号从1到n所以申请 n1 这么大的数组vectorlistintgraph(n1);// 邻接表while(m--){cinst;// 使用邻接表 表示 s - t 是相连的graph[s].push_back(t);}path.push_back(1);// 无论什么路径已经是从0节点出发dfs(graph,1,n);// 开始遍历// 输出结果if(result.size()0)cout-1endl;for(constvectorintpa:result){for(inti0;ipa.size()-1;i){coutpa[i] ;}coutpa[pa.size()-1]endl;}}