这个广度优先搜索将如何转换为 Java 中的静态方法？

Question

我用 Python 编写了这个静态方法来进行广度优先搜索。但是，我主要使用Java，我想了解数据结构如何转换为Java，给定泛型等。我的代码是：

def bfs(graph, start_vertex, target_value):

  path = [start_vertex] #a list that contains start_vertex

  vertex_and_path = [start_vertex, path] #a list that contains start_vertex and path

  bfs_queue = [vertex_and_path]

  visited = set() #visited defined as an empty set

  while bfs_queue: #while the queue is not empty

    current_vertex, path = bfs_queue.pop(0) #removes element from queue and sets both equal to that first element

    visited.add(current_vertex) #adds current vertex to visited list

    for neighbor in graph[current_vertex]: #looks at all neighboring vertices

      if neighbor not in visited: #if neighbor is not in visited list

        if neighbor is target_value: #if it's the target value

          return path + [neighbor] #returns path with neighbor appended

        else:

          bfs_queue.append([neighbor, path + [neighbor]]) #recursive call with path that has neighbor appended

我会使用它的图表是：

myGraph = { //I'm not sure how to structure this in Java

    'lava': set(['sharks', 'piranhas']),

    'sharks': set(['lava', 'bees', 'lasers']),

    'piranhas': set(['lava', 'crocodiles']),

    'bees': set(['sharks']),

    'lasers': set(['sharks', 'crocodiles']),

    'crocodiles': set(['piranhas', 'lasers'])

  }

我会这样称呼它

public static void main(String[] args){

    System.out.println(bfs(myGraph, "crocodiles", "bees"));

}

Answer 1

我用 Python 编写了这个静态方法来进行广度优先搜索。但是，我主要使用Java，我想了解数据结构如何转换为Java，给定泛型等。我的代码是：def bfs(graph, start_vertex, target_value):&nbsp; path = [start_vertex] #a list that contains start_vertex&nbsp; vertex_and_path = [start_vertex, path] #a list that contains start_vertex and path&nbsp; bfs_queue = [vertex_and_path]&nbsp; visited = set() #visited defined as an empty set&nbsp; while bfs_queue: #while the queue is not empty&nbsp; &nbsp; current_vertex, path = bfs_queue.pop(0) #removes element from queue and sets both equal to that first element&nbsp; &nbsp; visited.add(current_vertex) #adds current vertex to visited list&nbsp; &nbsp; for neighbor in graph[current_vertex]: #looks at all neighboring vertices&nbsp; &nbsp; &nbsp; if neighbor not in visited: #if neighbor is not in visited list&nbsp; &nbsp; &nbsp; &nbsp; if neighbor is target_value: #if it's the target value&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return path + [neighbor] #returns path with neighbor appended&nbsp; &nbsp; &nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; bfs_queue.append([neighbor, path + [neighbor]]) #recursive call with path that has neighbor appended我会使用它的图表是：myGraph = { //I'm not sure how to structure this in Java&nbsp; &nbsp; 'lava': set(['sharks', 'piranhas']),&nbsp; &nbsp; 'sharks': set(['lava', 'bees', 'lasers']),&nbsp; &nbsp; 'piranhas': set(['lava', 'crocodiles']),&nbsp; &nbsp; 'bees': set(['sharks']),&nbsp; &nbsp; 'lasers': set(['sharks', 'crocodiles']),&nbsp; &nbsp; 'crocodiles': set(['piranhas', 'lasers'])&nbsp; }我会这样称呼它public static void main(String[] args){&nbsp; &nbsp; System.out.println(bfs(myGraph, "crocodiles", "bees"));}到目前为止，这是我拥有的 Java：&nbsp; &nbsp; public class BreadthFirstSearch{&nbsp; &nbsp; ///NOT DONE YET&nbsp; &nbsp; public static ArrayList<String> BFS(Map<String, String[]> graph, String start, String target) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; List<String> path = new ArrayList<>();&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; path.add(start);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; List<String> vertexAndPath = new ArrayList<>();&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; vertexAndPath.add(start);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; vertexAndPath.add(path.get(0));&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ArrayList<String> queue = new ArrayList<>();&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; queue.add(vertexAndPath.get(0));&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; queue.add(vertexAndPath.get(1));&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Set<String> visited = new HashSet<String>();&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; while(!queue.isEmpty()) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; String currentVertex = queue.remove(0);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; String curVerValue = currentVertex;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; path.add(currentVertex);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; .&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; .&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; .&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }}

Answer 2

您需要创建一个单独的类来保存图形的节点。这些节点不能是静态的，因为它们都有唯一的顶点。从那里其余的非常相似。public class Node {&nbsp; &nbsp; public String name;&nbsp; &nbsp; public ArrayList<Node> vertices;&nbsp; &nbsp; public void addEdge(Node node) {&nbsp; &nbsp; &nbsp; &nbsp; edges.add(node);&nbsp; &nbsp; }}