首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

JS图递归与迭代DFS阶差

是一个关于JavaScript中图的深度优先搜索(DFS)算法的递归和迭代实现的问题。

深度优先搜索是一种用于遍历或搜索图的算法,它从一个顶点开始,沿着一条路径尽可能深入地访问图中的顶点,直到无法继续前进,然后回溯到前一个顶点,继续探索其他路径。DFS可以用递归和迭代两种方式实现。

递归实现DFS的思路是,从起始顶点开始,递归地访问与当前顶点相邻的未访问过的顶点,直到所有顶点都被访问过。递归实现DFS的代码如下:

代码语言:txt
复制
function dfsRecursive(graph, start, visited) {
  visited[start] = true;
  console.log(start);

  for (let neighbor of graph[start]) {
    if (!visited[neighbor]) {
      dfsRecursive(graph, neighbor, visited);
    }
  }
}

const graph = {
  A: ['B', 'C'],
  B: ['A', 'D', 'E'],
  C: ['A', 'F'],
  D: ['B'],
  E: ['B', 'F'],
  F: ['C', 'E']
};

const visited = {};
dfsRecursive(graph, 'A', visited);

迭代实现DFS的思路是,使用栈来保存待访问的顶点,从起始顶点开始,将其入栈,然后循环执行以下步骤:出栈一个顶点,访问该顶点并将其标记为已访问,将与该顶点相邻的未访问过的顶点入栈。直到栈为空为止。迭代实现DFS的代码如下:

代码语言:txt
复制
function dfsIterative(graph, start) {
  const stack = [start];
  const visited = {};

  while (stack.length > 0) {
    const vertex = stack.pop();
    if (!visited[vertex]) {
      visited[vertex] = true;
      console.log(vertex);
      for (let neighbor of graph[vertex]) {
        stack.push(neighbor);
      }
    }
  }
}

const graph = {
  A: ['B', 'C'],
  B: ['A', 'D', 'E'],
  C: ['A', 'F'],
  D: ['B'],
  E: ['B', 'F'],
  F: ['C', 'E']
};

dfsIterative(graph, 'A');

这两种实现方式都可以用于解决图相关的问题,如查找路径、连通性检测等。递归实现DFS的优点是简洁易懂,但对于大规模的图可能会导致栈溢出。迭代实现DFS的优点是不会出现栈溢出的问题,但代码相对复杂一些。

腾讯云提供了一系列与云计算相关的产品,如云服务器、云数据库、云存储等。具体推荐的产品和产品介绍链接地址可以根据具体需求和场景来选择,可以参考腾讯云官方网站(https://cloud.tencent.com/)获取更详细的信息。

页面内容是否对你有帮助?
有帮助
没帮助

相关·内容

青蛙跳台阶

,y_{t+n} 的方程,称为分方程。出现在分方程中的未知函数下标的最大差称为分方程的。...分方程可以化简为形如: 如果 f(t)=0 ,那么上面就是 n 线性齐次分方程; 如果 f(t) \neq 0 ,那么上面就是 n 线性非齐次分方程。...因为上面的递归实现,虽然每次递归都会有开辟两个分支,按理说递归调用了 多少次,就开辟了多大的栈空间,按照这个逻辑,那么空间复杂度时间复杂应该是一样的, 都是 O(2^n) 。...6.迭代递归实现虽然简单易于理解,但是 O(2^n) 的时间复杂度和 O(n) 的空间却让人无法接受,下面采用迭代的方式来实现,时间复杂度为 O(n),空间复杂度为 O(1)。...递归等式如下: 8.2 具体实现 递归等式是一个以2为公比的等比数列,所以递归迭代实现起来都比较简单。

94920
  • 青蛙跳台阶问题暨斐波那契数列

    ,注意t的取值是离散的 一分:Δyt=yt+1−yt=f(t+1)−f(t)\Delta y_t=y_{t+1}-y_t=f(t+1)-f(t) 二分: image.png 分方程的定义...分方程可以化简为形如: image.png 如果f(t)=0f(t)=0,那么上面就是n线性齐次分方程; 如果f(t)=0f(t)=0,那么上面就是n线性非齐次分方程。...因为上面的递归实现,虽然每次递归都会有开辟两个分支,按理说递归调用了 多少次,就开辟了多大的栈空间,按照这个逻辑,那么空间复杂度时间复杂应该是一样的, 都是O(2n)O(2^n)。...4.迭代实现 递归实现虽然简单易于理解,但是O(2n)O(2^n)的时间复杂度和O(n)的空间却让人无法接受,下面迭代法的具体实现,比较简单,就不再赘述实现步骤。...递归等式如下: image.png 6.2具体实现 递归等式是一个以2为公比的等比数列,所以递归迭代实现起来都比较简单,参考如下: //递归法 //时间复杂度O(n),空间复杂度O(n) int

    1K22

    重学前端(四)-数据结构算法

    Set set是es6新出的一种数据结构,Set对象是值的集合,你可以按照插入的顺序迭代它的元素。 Set中的元素只会出现一次,即 Set 中的元素是唯一的。...如果图中不存在环,则称该是无环的。如果图中任何两个顶点间都存在路径,则该是连通的,如上图就是一个连通。如果的边没有方向,则该是无向,上图所示为无向,反之则称为有向, ?...那么在我们的js中,同样的没有我们同样的可以使用数组和对象来表示一个,如果用数组去表示,就会给起一个名字叫做邻接矩阵,而我们如果将数组和对象混用那么就起个名字叫做邻接表,本质上就是表示上的不同 邻接矩阵...(一看就懂) 我们只需记住时间复杂度量级有: 常数O(1) 对数O(logN) 线性O(n) 线性对数O(nlogN) 平方O(n²) 立方O(n³) K次方O(n^k) 指数(2^n)...// 1. 1 + 1 // 2. 2 // =======分析========= // 首先我们假设只有3,那么我先定义好,我最后一步可以是两

    50410

    前端leetcde算法面试套路之二叉树4

    前端就该用JS写算法 -- 树 -- 简单的那 30%这里优先选择了 LeetCode 热题 HOT 100 中的树题,毕竟刷题的边际收益就是冲击需要算法的面试,所以 Hot 优先级更高。...二叉树的遍历递归遍历递归的时候前中后序都能直接处理完了递归是前中后序遍历最简单也是最容易出理解的方法,不懂的画个就好了迭代遍历 -- 双色标记法使用颜色标记节点状态,新节点为白色,已经访问的节点为灰色...,就好像我们做非排序题排序的时候,sort 一下就好了,但是一旦面试官问到用另外的迭代方式的时候,我们再套个模板,会比记住多个迭代写法要简单,毕竟内存容量有限,而后续遍历的迭代写法确实挺坑的,能省一点内存就省一点吧...递归是前中后序遍历最简单也是最容易出理解的方法,不懂的画个就好了 */var inorderTraversal = function(root) { const ret = [] const...DFS, 而自低向上,是递归,需要dfs 到了底部,然后归到根节点,所以这里用的是 recursion 作为方法名。

    23620

    前端leetcde算法面试套路之二叉树

    前端就该用JS写算法 -- 树 -- 简单的那 30%这里优先选择了 LeetCode 热题 HOT 100 中的树题,毕竟刷题的边际收益就是冲击需要算法的面试,所以 Hot 优先级更高。...二叉树的遍历递归遍历递归的时候前中后序都能直接处理完了递归是前中后序遍历最简单也是最容易出理解的方法,不懂的画个就好了迭代遍历 -- 双色标记法使用颜色标记节点状态,新节点为白色,已经访问的节点为灰色...,就好像我们做非排序题排序的时候,sort 一下就好了,但是一旦面试官问到用另外的迭代方式的时候,我们再套个模板,会比记住多个迭代写法要简单,毕竟内存容量有限,而后续遍历的迭代写法确实挺坑的,能省一点内存就省一点吧...递归是前中后序遍历最简单也是最容易出理解的方法,不懂的画个就好了 */var inorderTraversal = function(root) { const ret = [] const...DFS, 而自低向上,是递归,需要dfs 到了底部,然后归到根节点,所以这里用的是 recursion 作为方法名。

    25040

    leetcde算法面试套路之二叉树

    前端就该用JS写算法 -- 树 -- 简单的那 30%这里优先选择了 LeetCode 热题 HOT 100 中的树题,毕竟刷题的边际收益就是冲击需要算法的面试,所以 Hot 优先级更高。...二叉树的遍历递归遍历递归的时候前中后序都能直接处理完了递归是前中后序遍历最简单也是最容易出理解的方法,不懂的画个就好了迭代遍历 -- 双色标记法使用颜色标记节点状态,新节点为白色,已经访问的节点为灰色...,就好像我们做非排序题排序的时候,sort 一下就好了,但是一旦面试官问到用另外的迭代方式的时候,我们再套个模板,会比记住多个迭代写法要简单,毕竟内存容量有限,而后续遍历的迭代写法确实挺坑的,能省一点内存就省一点吧...递归是前中后序遍历最简单也是最容易出理解的方法,不懂的画个就好了 */var inorderTraversal = function(root) { const ret = [] const...DFS, 而自低向上,是递归,需要dfs 到了底部,然后归到根节点,所以这里用的是 recursion 作为方法名。

    22130

    AAAI2020| 当推荐系统邂逅线性残GCN

    GCNs的核心思想是多层叠加,每层迭代执行以下两步:节点嵌入卷积邻域聚合;其次是由神经网络参数化的节点嵌入的非线性变换,因此,可以有效地捕获节点的高阶相似度。...作者证明,通过线性残学习,所提出的模型退化为一个线性模型,有效地利用user-item结构进行推荐,而且目前基于GCN的推荐模型相比,这种提出的模型更易于训练以及可以扩展到大型数据集。...⑵ 残偏好预测 具有预定义的深度K,线性嵌入的递归传播将在第K层停止,输出嵌入矩阵 ? 。对于每个用户(物品), ? 捕获到k二部的相似性。...作者推测一个可能的原因是,在第k层,每个节点的嵌入被二部的k邻居平滑。...R-GC-MC没有表现出GC-MC相当的性能,作者猜测可能的原因是GC-MC是基于一邻域聚集的。对于一邻域,每个邻域都有有限的邻域,过度平滑效应不适用于一邻域。

    88740

    递归算法的时间复杂度分析

    实际上,这个问题是数学上求解渐近的问题,而递归方程的形式多种多样,其求解方法也是不一而足,比较常用的有以下四种方法: (1)代入法(Substitution Method) 代入法的基本步骤是先推测递归方程的显式解...(2)迭代法(Iteration Method) 迭代法的基本步骤是迭代地展开递归方程的右端,使之成为一个非递归的和式,然后通过对和式的估计来达到对方程左端即方程的解的估计。...(4)分方程法(Difference Formula Method) 可以将某些递归方程看成分方程,通过解差分方程的方法来解递归方程,然后对解作出渐近估计。...这里涉及的三类情况,都是拿f(n)nlogb a 作比较,而递归方程解的渐近由这两个函数中的较大者决定。...(n)的同

    1.9K50

    【骗分利器】模拟退火模板及我猜你问

    但在朴素的 DFS 中,我们是将每个任务依次分给每个工人,并递归此过程。 对应的递归树其实是一颗高度为 n 的 k 树。...因为将 n 个数划分为 k 份,等效于用 n 个数构造出一个「特定排列」,然后对「特定排列」进行固定模式的任务分配逻辑,就能实现「答案」「最优排列」的对应关系。...,落入「局部最优」(WA)的概率越高;系数越高 TLE 风险越大) double hi = 1e8, lo = 1e-4, fa = 0.90; // 迭代次数,变化速率同理...如果是 WA 了,一般我是优先调大 fa 参数,使降温变慢,来变相增加迭代次数;如果是 TLE 了,一般是优先调小 fa 参数,使降温变快,减小迭代次数。总迭代参数 N 也是同理。...但绝对是在你已经彻底理解「剪枝 DFS」和我没写的「状态压缩 DP」之后再去了解。 Q5. 在「剪枝 DFS」中为什么「优先分配空闲工人」的做法是对的? 首先要明确,递归树还是那棵递归树。

    64010

    CVPR2021 | NTIRE2021竞赛三冠一亚方案BasicVSR++,Vid4新巅峰29.04dB

    本文对BasicVSR进行了重设计,提出了二网格传播(grid propgation)光流引导形变对齐。通过采用增强版传播对齐,所得BasicVSR++可以更有效的利用未对齐视频的空时信息。...给定输入视频,首先采用残模块提取对每一帧提取特征;然后这些特征在二网络传播机制中进行信息传播,其中对齐部分采用光流引导形变对齐;完成信息传播后,汇聚集成后的特征用于生成输出图像。...通过集成上述两个成分,我们按照如下方式设计了二网格传播。假设 表示输入图像, 表示通过多个残模块提取的特征, 表示在第i时间步长第j传播分支的特征。...训练过程中优化器为Adam,Cosine Annealing学习衰减机制,主网络光流网络的学习率分别设置为 。总共迭代此输为600K,光流网络的权值在前5000次迭代过程中固定。...vid4 上面几个给出了所提方案在不同测试集上的视觉效果对比,可以看到:BasicVSR++成功的复原了图像的纹理细节。 Ablation Study ?

    1.5K20

    动态规划(一):爬楼梯

    题目 一个 的楼梯,每次能走 1~2 ,问走到 一共多少种走法 分析 因为每次能走 1~2 ,所以第 的前一个状态可以是第 ,或第 ,且只有这两种情况。...迭代形式 递归形式算法的时间复杂度呈指数级增长,所以这种算法较为不现实。观察递推关系式: 可以发现,每个阶梯数的函数值,只与其前两项的函数值有关,所以不妨由低到高进行推导。...矩阵形式 根据递推关系式,对二分方程构造矩阵: 根据 的递推关系式, 可得: import numpy as np import math def climbingStairs_matrix(n...拓展形式 当步长调整为 1~ 时,问走到 一共多少种走法 递归形式 def climbingStairs(n, m): if n == 0: return 1...更新为 ,增加步长 的大小关系判断。

    72120

    《python算法教程》Day5 - DFS遍历(邻接字典)DFS简介代码示例

    这篇笔记的主要内容为运用DFS(深度优先搜索,depth first search)对(邻接字典)进行遍历。 DFS简介 在解决问题的时候,需要对整个进行遍历,以获取整个的节点信息。...此时遍历的思路是根据当前访问的点,访问其邻接点,最终使得整个的节点均被访问。此时,访问邻接节点的策略有DFS(深度优先搜索)和BFS(广度优先搜索)。...代码示例 以下将根据下图给出递归版和迭代版的深度优先搜索代码。 ?...DAG.JPG 递归DFS #递归DFS def dfs(G,s,S=None,res=None): if S is None: #储存已经访问节点 S=set...'d':{'e','f'}, 'e':{'f'}, 'f':{} } res=dfs(G,'a') print(res) 迭代DFS #迭代DFS def dfs(G,s)

    2.8K110

    递归算法时间复杂度分析

    类似的,我们也可以用迭代法求解汉诺塔递归求解时的时间复杂度。但遗憾的是,迭代法一般适用于一的递推方程。...对于二及以上(即T(n)依赖它前面更多个递归项T(n)依赖它前面更多个递归项)的递推方程,迭代法将导致迭代后的项太多,从而使得求和公式过于复杂,因此需要将递推方程化简,利用消法等技巧将高阶递推方程化为一递推方程...不过递归树模型更直观,同时递归树也克服了二及更高阶递推方程不方便迭代展开的痛点。...按照这个公式,我们可以计算【迭代法】中提到的例子:O(f(n))=O(n2),容易计算另外一个的是O(n),他们不等,所以取较大的O(n2)。太简单了,不是吗?   ...---- 【分方程法】可以将某些递归方程看成分方程,通过解差分方程的方法来解递归方程,然后对解作出渐近估计。

    2.3K20

    迭代加深搜索(的路径查找)

    同时,由于它在层数上采用BFS思想来逐步扩大DFS的搜索深度,因此能够解决DFS可能陷入递归无法返回的问题,并避免BFS可能导致的队列空间爆炸问题。...深度优先搜索广度优先搜索的选择:深度优先搜索(DFS)和广度优先搜索(BFS)都可以用于解决八数码问题。由于我们希望找到的是最短解决方案,因此BFS通常更适合,因为它会首先探索较浅层的节点。...比较空间复杂度:DFS的空间复杂度通常较低,因为它只需要保存从源节点到当前节点的路径信息。然而,在最坏情况下,当退化为链状时,DFS可能需要存储图中节点数相同数量的信息。...深度优先搜索辅助方法 dfs:该方法递归地遍历,从当前节点 current 开始搜索目标节点 goal。如果当前节点就是目标节点,则创建一个新的 Path 对象并返回。...否则,遍历当前节点的所有邻居节点,并对每个邻居节点递归调用 dfs 方法。如果在邻居节点中找到路径,将该路径当前节点合并(添加到路径的开头),并返回合并后的路径。

    6710

    java算法刷题02——深度优先搜索广度优先搜索

    先通过一道特别经典的题目来回顾下DFS算法。 T1 无向的遍历 对下图的各个节点遍历,且不重复 解法如下。...,原来dfs就是使用递归来实现阿。...如果可以用这样的逻辑去思考递归算法,后续做题就更加简单了。 除了深度优先搜索遍历,广度优先搜索也常常应用于树和的算法问题。先来实现两个简单的题目。...遍历收尾两行,同时首位两行第一个最后一个元素已经被dfs递归过,无需重复递归 for (int i = 1; i < m - 1; i++) {...您是不是觉得似曾相识,怎么那么像岛屿数量那道题,不过,这可岛屿那道题不同,这是一个的类型题,我们需要构建一个。那么要怎么求解呢?

    58310

    前端工程师leetcode算法面试必备-二叉树深度广度遍历1

    二叉树是的子集,因而同样适用以下两种搜索思想:DFS(深度优先搜索):**沿着根节点递归下去,遇到叶子节点则向上回溯**;BFS (广度优先搜索):**按照二叉树的层次访问,通常采用队列保存每个层次的节点...上一篇中也提到可以采用尾递归的书写方式,让 JavaScript 引擎去将递归优化成迭代,从而解决性能上的问题。但是在一些情况下,尾递归并没有那么好写,所以本文会同时给出递归迭代的解决方案。  ...图片2、DFS  采用 DFS 搜索思想,需要注意在递归的过程中记录当前节点的层次信息:图片三、145. 二叉树的后序遍历给定一个二叉树,返回它的 后序 遍历。  ...:1、递归实现 DFS  从定义中,大家应该能够想象到递归的代码如何书写:图片参考视频:传送门2、迭代实现 DFS  本道题目采用迭代实现 DFS 不太容易理解,主要由于迭代不能像递归那样向上回溯,所以迭代向下遍历的过程中...在简单难度中,会介绍该算法的基本知识实现,另外两个难度,着重讲解解题的思路。  如果本文对您有所帮助,可以点赞或者关注来鼓励博主。

    41420

    前端工程师leetcode算法面试必备-二叉树深度广度遍历

    二叉树是的子集,因而同样适用以下两种搜索思想: DFS(深度优先搜索):**沿着根节点递归下去,遇到叶子节点则向上回溯**; BFS (广度优先搜索):**按照二叉树的层次访问,通常采用队列保存每个层次的节点...上一篇中也提到可以采用尾递归的书写方式,让 JavaScript 引擎去将递归优化成迭代,从而解决性能上的问题。 但是在一些情况下,尾递归并没有那么好写,所以本文会同时给出递归迭代的解决方案。   ...图片 2、DFS   采用 DFS 搜索思想,需要注意在递归的过程中记录当前节点的层次信息: 图片 参考视频:传送门 三、145. 二叉树的后序遍历 给定一个二叉树,返回它的 后序 遍历。   ...: 1、递归实现 DFS   从定义中,大家应该能够想象到递归的代码如何书写: 图片 2、迭代实现 DFS   本道题目采用迭代实现 DFS 不太容易理解,主要由于迭代不能像递归那样向上回溯,所以迭代向下遍历的过程中...在简单难度中,会介绍该算法的基本知识实现,另外两个难度,着重讲解解题的思路。

    36120

    前端工程师leetcode算法面试之二叉树深度广度遍历

    二叉树是的子集,因而同样适用以下两种搜索思想:DFS(深度优先搜索):**沿着根节点递归下去,遇到叶子节点则向上回溯**;BFS (广度优先搜索):**按照二叉树的层次访问,通常采用队列保存每个层次的节点...上一篇中也提到可以采用尾递归的书写方式,让 JavaScript 引擎去将递归优化成迭代,从而解决性能上的问题。但是在一些情况下,尾递归并没有那么好写,所以本文会同时给出递归迭代的解决方案。  ...图片2、DFS  采用 DFS 搜索思想,需要注意在递归的过程中记录当前节点的层次信息:图片三、145. 二叉树的后序遍历给定一个二叉树,返回它的 后序 遍历。  ...:1、递归实现 DFS  从定义中,大家应该能够想象到递归的代码如何书写:图片参考视频:传送门2、迭代实现 DFS  本道题目采用迭代实现 DFS 不太容易理解,主要由于迭代不能像递归那样向上回溯,所以迭代向下遍历的过程中...在简单难度中,会介绍该算法的基本知识实现,另外两个难度,着重讲解解题的思路。  如果本文对您有所帮助,可以点赞或者关注来鼓励博主。

    30840

    Deblurring with Parameter Selective Sharing and Nested Skip Connections

    在传统的迭代图像去模糊算法的驱动下,我们假设在子网络的各个阶段非线性模块之间也存在尺度内的参数共享。在这种策略下,每个阶段的转换模块共享相同的参数,如对模糊特征迭代应用固定的求解器。...如图3(c)所示,子网一个编码器阶段的结构由(b)演化为(c),其中迭代使用相同的模块进行非线性变换。...我们将其称为4(a)所示的一。假设输入 也是由另一个一函数产生的,则可将其代入式(2)。经验上,残的残拟合比原残映射更容易。...进一步将二函数扩展到三函数如 ?4(c)为三函数。递归可以继续推导出更高阶的剩余函数。...可以将高阶残函数分组到一个嵌套模块中,以改进信息流,更好地处理网络中的梯度消失问题。虽然在[19,33]中堆叠的重块有许多短期跳过连接,但它只是堆叠了一剩余函数。

    1.9K10
    领券