leetcode hot100_part28_图论

作者：小舞很执着 | 2024-07-12 05:28:22

踩

200.岛屿数量

做完了这四题，总结一下，还是要掌握基本的dfs，bfs模版，都是在这些基础上变换的。

模版：

深度优先：


// 从某个节点u开始
DFS(u){
    访问u;
    for(对于u的每个相邻节点v){
        if(v没有被访问){
            DFS(v);
        }
    }
}

广度优先


BFS(){
    //广度优先不是递归而是循环
    某个节点u(or某些节点)入队列；
    while（队列非空）{
        队首元素u出队;
        for(对于u的每个相邻节点v){
            if(v未被访问){
                访问v;
                v入队;
            }
        }
    }    
}

想说的是，上述都是在一个联通分量里的遍历，如果要遍历图的所有联通分量就要for循环遍历每个没有访问过的节点。dfs一般单写个函数，而bfs直接是代码块。

200.岛屿数量

DFS

力扣那个最多赞的题解写的太好了。按照这个很容易写出dfs的解法，找不到的话力扣收藏了。

bfs

bfs的基本模版都忘了，看的王道的ppt简单复习了一下。这个方法和下一题的BFS遍历基本一样，某个岛屿节点入队后，while（队列非空，出队，遍历四周，岛屿节点入队）。

并查集

挖坑

994.腐烂的橘子

烂橘子这题有自己的思路，但是没实现。自己的思路就是借助上一题的模版，从每个烂橘子的地方开始dfs遍历，返回的是到边界最深的深度，也就是所在联通分量里最远的地方的距离。对于一个联通分量里的烂橘子，取最小的结果，然后取所有联通分量里最大的结果返回。

官方题解的思路是BFS，把每次扩散都当做下一层来看，而一开始所有腐烂的橘子是由一个想象的烂橘子扩散的。BFS只要一次遍历就能遍历所有，而dfs一次遍历只能拿到每个腐烂橘子的“最远距离”，而且用上一题那个模版遍历之后原数组就变了。

关于代码，主要分为两部分，初始化：第一批烂橘子入队列，map记录位置点和层数深度；

BFS：新橘子变烂，然后深度是上一层加一。最后的一层一定是最深的，因为就是按层遍历的。

还有就是数组的位置映射，code到行列的映射，code = r*C+c；不是r*R+c；别想当然，每行的个数是C不是R!

207.课程表

本质是拿到拓扑排序，有向无环图DAG才有拓扑排序。首先要知道什么是拓扑排序？基本的定义和特点。

DFS

拿到的拓扑排序的倒序，存放在一个栈中。算法的关键，对所有节点设置三个状态，未访问，正在访问，访问完成。从未访问的节点开始访问，遍历到的是正在访问，遍历完成的节点是该节点的所有相邻节点（该节点指向的节点）都完成访问。如果正在访问的节点的相邻节点的状态也是正在访问，则有环。仔细阅读题解吧。

二叉树的递归遍历也算是dfs，这里又有很多联想，前中后和dfs的区别？

BFS

借助入度实现，入度为0的节点先入队列，移除队首元素和它的边，再让入度为零的节点入队列，直到没有入度为零的点（有环）或者所有点都遍历了。这拿到的是拓扑正序。

代码实现的初始化部分也很重要，两种方法主要是边的关系用邻接表存储。搞清指向。感觉主要还是对队列这个数据结构api不熟悉。

208.实现Trie（前缀树）

前缀树也叫字典树，入门视频。

直接看这个：链接。over

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小舞很执着/article/detail/812767