当前位置：首页 > news >正文

打卡50天------图论

news 来源：原创 2024/9/20 3:57:47

正式开启图论了，作为一个前端工程师，这个代码随想录真的刷新了我对于算法的认知，每天都在学习新东西。别着急、放轻松、慢慢来。

一、图论理论基础

讲解了很多东西，但是在前端开发过程中很少用到吧，主要是学习算法的思路。

二、深搜理论基础

了解一下深搜的原理和过程，其实对于深搜和广搜我自己也写过一篇博客，是我个人的理解，但是没有卡尔总结的全面，如此看来真的是小巫见大巫了。

我自己的博客：我理解的深搜与广搜

我自己理解完深搜理论基础之后，在图上画了画，然后又尝试自己写代码给写出来了。

关键就两点：

搜索方向，是认准一个方向搜，直到碰壁之后再换方向
换方向是撤销原路径，改为节点链接的下一个路径，回溯的过程。

在回顾一下回溯法的代码框架：

void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {处理节点;backtracking(路径，选择列表); // 递归回溯，撤销处理结果}
}

深搜三部曲：

确认递归函数，参数
```
void dfs(参数)
```
确认终止条件
终止条件很重要，很多同学写dfs的时候，之所以容易死循环，栈溢出等等这些问题，都是因为终止条件没有想清楚。
```
if (终止条件) {存放结果;return;
}
```
终止添加不仅是结束本层递归，同时也是我们收获结果的时候。
另外，其实很多dfs写法，没有写终止条件，其实终止条件写在了，下面dfs递归的逻辑里了，也就是不符合条件，直接不会向下递归。这里如果大家不理解的话，没关系，后面会有具体题目来讲解。
处理目前搜索节点出发的路径
一般这里就是一个for循环的操作，去遍历目前搜索节点所能到的所有节点。
```
for (选择：本节点所连接的其他节点) {处理节点;dfs(图，选择的节点); // 递归回溯，撤销处理结果
}
```

三、所有可达路径

leetcode题目链接：797.所有可能的路径

题目描述：

给你一个有 n 个节点的 有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）

graph[i] 是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点 graph[i][j]存在一条有向边）。