java - 如何将 Python 中的递归深度优先搜索转换为 Java？

Question

我正在尝试将此 Python 深度优先搜索转换为 Java。这是我的 Python 代码:

def dfs(graph, current_vertex, target_value, visited=None):
  if visited is None: #for when not a recursive call
    visited = [] #empty list

  visited.append(current_vertex) #adds current vertex to visited

  if current_vertex == target_value: #for when current_vertex is target value (ie target reached)
    return visited

  # Add your recursive case here:
  for neighbor in graph[current_vertex]: #checks each neighbor of curr, Remember that the graphs hold key-value pairs for each vertex and its set of connected vertices.
    if neighbor not in visited: #if neighbor has not been added to visited
      path = dfs(graph, neighbor, target_value, visited) #recursive call with new vertex, a visited list(now a list of at least one vertex value), graph and TV remain same

      if path: #if the path exists
        return path #return the path

#set with keys and values
the_most_dangerous_graph = {
    'lava': set(['sharks', 'piranhas']),
    'sharks': set(['lava', 'bees', 'lasers']),
    'piranhas': set(['lava', 'crocodiles']),
    'bees': set(['sharks']),
    'lasers': set(['sharks', 'crocodiles']),
    'crocodiles': set(['piranhas', 'lasers'])
  }

# Call dfs() below and print the result:
print(dfs(the_most_dangerous_graph, "crocodiles", "bees"))

我了解了该算法的总体思路:转到元素的子元素，直到遍历完所有子元素，开始弹出，直到到达具有未访问过的子元素的顶点，访问该顶点，并按访问顺序保存所有访问过的顶点。不过，我知道如何从 Java 开始使用递归。这是我得到的:

import java.util.*;

public class DepthFirstSearch {

    private static Set<String> DFSHelper(HashMap<String,String[]> graph, String currentValue,
            String targetValue, HashMap<String, String> visited, Stack<String> s) {
        Iterator it = graph.values().iterator();
        visited.put(currentValue, null);
        s.push(currentValue);
        System.out.println(s.peek());
        System.out.println(currentValue);
        //System.out.println(graph.get(currentValue));

        if(!s.isEmpty()) {
            String neighbor = it.next().toString();
            if(!visited.containsKey(neighbor)) {
                visited.put(neighbor,currentValue);
                currentValue = neighbor;
                return DFSHelper(graph,currentValue,targetValue,visited,s);
            }           
        }

        return visited.keySet();        
    }
    public static Set<String> DFS(HashMap<String,String[]> graph, String currentValue,
            String targetValue) {
        HashMap<String,String> visited = new HashMap<>(); 
        Stack<String> s = new Stack<String>();
        return DFSHelper(graph,currentValue,targetValue,visited,s);
    }

    public static void main(String[] args) {
        HashMap<String, String[]> myGraph = new HashMap<>();
        myGraph.put(
            "lava", new String[] {"sharks", "piranhas"}
        );
        myGraph.put(
            "sharks", new String[] {"lava", "bees", "lasers"}
        );
        myGraph.put(
            "piranhas", new String[] {"lava", "crocodiles"}
        );
        myGraph.put(
            "bees", new String[] {"sharks"}
        );
        myGraph.put(
            "lasers", new String[] {"sharks", "crocodiles"}
        );
        myGraph.put(
            "crocodiles", new String[] {"piranhas", "lasers"}
        );
        System.out.println(DFS(myGraph, "crocodiles", "bees"));
        System.out.println(DFS(myGraph, "crocodiles", "crocodiles"));
        System.out.println(DFS(myGraph, "crocodiles", "zebras"));
    }   
}

到目前为止，除了打印语句之外，我只获得了哈希码，而且我不确定我是否走在正确的轨道上。

Answer 1

您的输出看起来很糟糕，因为: it.next().toString();

迭代器定义为: Iterator it = graph.values().iterator();其中图表是:HashMap<String,String[]> graph
所以it.next()返回 String[]

使用 toString 打印数组将产生类似的输出

String[] array = {"crocodiles", "zebras"};
System.out.println(array.toString());

输出:

[Ljava.lang.String;@6a6824be

打印数组的更好方法是:System.out.println(Arrays.toString(array));
输出:

[crocodiles, zebras]

dfs的逻辑也有缺陷。如需帮助，请发布一个新问题，并包括图表的可视化和预期输出。