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

感谢上Di_123 2024-08-28 14:31:01 阅读 50

正式开启图论了,作为一个前端工程师,这个代码随想录真的刷新了我对于算法的认知,每天都在学习新东西。

别着急、放轻松、慢慢来。

一、图论理论基础

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

二、深搜理论基础

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

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

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

关键就两点:

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

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

<code>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]存在一条有向边)。

有空给补上吧。

四、广搜理论基础

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

讲解的很全面,

所谓广搜(bfs)是一圈一圈的搜索过程,深搜(dfs)是一条路跑到黑然后再回溯。



声明

本文内容仅代表作者观点,或转载于其他网站,本站不以此文作为商业用途
如有涉及侵权,请联系本站进行删除
转载本站原创文章,请注明来源及作者。