这个广度优先搜索将如何转换为 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):

  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"));

}

到目前为止，这是我拥有的 Java：

    public class BreadthFirstSearch{

    ///NOT DONE YET

    public static ArrayList<String> BFS(Map<String, String[]> graph, String start, String target) {

            List<String> path = new ArrayList<>();

            path.add(start);

            List<String> vertexAndPath = new ArrayList<>();

            vertexAndPath.add(start);

            vertexAndPath.add(path.get(0));

            ArrayList<String> queue = new ArrayList<>();

            queue.add(vertexAndPath.get(0));

            queue.add(vertexAndPath.get(1));

            Set<String> visited = new HashSet<String>();

            while(!queue.isEmpty()) {

                String currentVertex = queue.remove(0);

                String curVerValue = currentVertex;

                path.add(currentVertex);

                .

                .

                .

            }

        }

}

Answer 2

您需要创建一个单独的类来保存图形的节点。这些节点不能是静态的，因为它们都有唯一的顶点。从那里其余的非常相似。

public class Node {

    public String name;

    public ArrayList<Node> vertices;

    public void addEdge(Node node) {

        edges.add(node);

    }

}