java 积累递归深度_java - 用于递归深度优先搜索以存储路径的额外空间 - 堆栈内存溢出...

叁歲伎倆 2022-11-09 11:19 131阅读 0赞

我使用深度优先搜索来识别有向加权图中的路径，同时重新访问属于循环的节点，并根据行进的总距离设置截止条件，或者从源节点停止。

据我所知，对于递归，深度优先搜索不需要显式堆栈结构，所以我想知道是否可以通过某种方式在没有显式堆栈的情况下进一步简化我的代码：

public class DFSonWeightedDirectedGraph \{

private static final String START = "A";

private static final String END = "E";

private int pathLength = 0;

private int stops = 0;

public static void main(String\[\] args) \{

//this is a directed weighted graph

WeightedDirectedGraph graph = new WeightedDirectedGraph();

graph.addEdge("A", "B", 15);

graph.addEdge("A", "D", 15);

graph.addEdge("A", "E", 27);

//(...) more edges added

Stack visited = new Stack();

visited.push(START);

new DFSonWeightedDirectedGraph().depthFirst(graph, visited);

\}

private void depthFirst(WeightedDirectedGraph graph, Stack visited) \{

Collection> tree\_of\_children

= graph.get\_tree\_of\_children(visited.peek());

for (Map.Entry child : tree\_of\_children) \{

if(pathLength + child.getValue()>= 20)\{

continue;

\}

visited.push(child.getKey());

pathLength += child.getValue();

stops += 1;

if (child.getKey().equals(END)) \{

printPath(visited);

\}

depthFirst(graph, visited);

visited.pop();

pathLength -= child.getValue();

stops -= 1;

\}

\}

private void printPath(Stack visited) \{

for (String node : visited) \{

System.out.print(node);

System.out.print(" ");

\}

System.out.println("\[path length: "+pathLength +

" stops made: " + stops +"\]");

\}

\}

但是，没有显式堆栈结构的其他递归实现通常会考虑已经访问过的节点，通过将它们着色为白色，灰色或黑色。 所以，在我允许重访的情况下，需要记录路径，是否需要显式堆栈？ 感谢您提供更简单的替代方案。

发表评论取消回复

表情：

评论列表（有 0 条评论，131人围观）

还没有评论，来说两句吧...

相关阅读

相关递归调用与栈溢出：Java深度优先搜索示例

递归调用是一种在程序中调用自身的方法，它常用于解决可以分解为相似子问题的问题，比如深度优先搜索（DFS）。在Java中，递归调用可能会导致栈溢出错误，尤其是当递归调用的深度过大

小鱼儿/ 2024年11月11日 23:06/ 0 赞/ 26 阅读

相关递归-深度优先搜索（模板、回溯、剪枝、记忆化）

目录简介可视化方向问题自顶向下思路模板举例自底向上思路模板举例回溯思路模板举例剪枝记忆化举例递归与栈

心已赠人/ 2022年12月06日 01:26/ 0 赞/ 256 阅读

相关 java 积累递归深度_java - 用于递归深度优先搜索以存储路径的额外空间 - 堆栈内存溢出...

我使用深度优先搜索来识别有向加权图中的路径，同时重新访问属于循环的节点，并根据行进的总距离设置截止条件，或者从源节点停止。据我所知，对于递归，深度优先搜索不需要显式堆栈结构

叁歲伎倆/ 2022年11月09日 11:19/ 0 赞/ 132 阅读

相关 java递归堆栈溢出_Java递归中的堆栈溢出错误

我正在尝试实现一个返回200万以下所有素数之和的代码.我有一个isPrime(int x)方法,如果数字是素数,则返回true.这里是： public static bool

古城微笑少年丶/ 2022年10月23日 11:24/ 0 赞/ 193 阅读

相关深度优先搜索 dfs可视化【递归 && 非递归】

打印了栈的大小，总觉得dfs不能直观的感受，打印了一下变化的过程 include <iostream> include <set> inclu

亦凉/ 2022年10月09日 04:49/ 0 赞/ 195 阅读

相关 java深度优先、非递归深度优先、广度优先迷宫求解可视化

本文将从以下几个维度来求解迷宫最终路径 1、深度优先递归求解最终路径 2、非递归深度优先走迷宫求解最终路径 3、广度优先走迷宫求解最终路径通用工具类

╰+攻爆jí腚メ/ 2022年05月24日 04:42/ 0 赞/ 203 阅读

相关无向图非递归的深度优先非递归遍历

// // main.cpp // Tu // // Created by 李奕昕 on 2018/6/16. // Copyr

小咪咪/ 2022年05月22日 08:27/ 0 赞/ 236 阅读

相关图的深度优先遍历代码递归

实现图的深度优先遍历,如下图: ![这里写图片描述][70] include <iostream> include <stdio.h>//注意 i

谁践踏了优雅/ 2022年05月22日 06:40/ 0 赞/ 206 阅读

相关树的广度优先遍历和深度优先遍历（递归非递归 Java实现）

[树的广度优先遍历和深度优先遍历（递归非递归、Java实现）][Java] 在编程生活中，我们总会遇见树性结构，这几天刚好需要对树形结构操作，就记录下自己的操

布满荆棘的人生/ 2022年04月10日 06:19/ 0 赞/ 222 阅读

相关树的广度优先遍历和深度优先遍历（递归非递归、Java实现）

在编程生活中，我们总会遇见树性结构，这几天刚好需要对树形结构操作，就记录下自己的操作方式以及过程。现在假设有一颗这样树，（是不是二叉树都没关系，原理都是一样的） ![1242

「爱情、让人受尽委屈。」/ 2021年09月16日 13:50/ 0 赞/ 382 阅读