企业官网建设流程全解析

思路：深度优先搜索的基础题目。

1.确认递归函数和参数：

（1）首先需要存一个用来遍历的图。

（2）存一个当前遍历的节点，定义为x。

（3）需要存一个n表示终点。在遍历的时候，当x == n时，表明找到了终点。

（4）单一路径和路径集合可以放在全局变量。

vector<vector<int>> result; // 收集符合条件的路径 vector<int> path; // 0节点到终点的路径 // x：目前遍历的节点 // graph：存当前的图 // n：终点 void dfs (const vector<vector<int>>& 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 List<List<Integer>> allPathsSourceTarget(int[][] graph) { // 从0到1暴力搜索即可 List<List<Integer>> res = new ArrayList<>(); List<Integer> path = new ArrayList<>(); path.add(0); //将起始节点0加入路径 dfs(res,path,graph,0,graph.length); return res; } private void dfs(List<List<Integer>> res,List<Integer> 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 List<List<Integer>> allPathsSourceTarget(int[][] graph) { List<List<Integer>> res = new ArrayList<>(); List<Integer> 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(List<List<Integer>> res, List<Integer> 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); //回溯，撤销本节点 } } } }