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