如何在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"));}到目前为止，这是我拥有的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<>();            }        }}

Answer 1

翻译上做得很好。让我提供我的代码，然后解释一下：

import java.util.*;

class BreadthFirstSearch {

    public static ArrayList<String> BFS(

        Map<String, String[]> graph, String start, String target

    ) {

        Map<String, String> visited = new HashMap<>();

        visited.put(start, null);

        ArrayDeque<String> deque = new ArrayDeque<>();

        deque.offer(start);

        while (!deque.isEmpty()) {

            String curr = deque.poll();

            if (curr.equals(target)) {

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

                path.add(curr);

                while (visited.get(curr) != null) {

                    curr = visited.get(curr);

                    path.add(curr);

                }

                Collections.reverse(path);

                return path;

            }

            for (String neighbor : graph.get(curr)) {

                if (!visited.containsKey(neighbor)) {

                    visited.put(neighbor, curr);

                    deque.offer(neighbor);

                }

            }

        }

        return null;

    }

    public static void main(String[] args) {

        Map<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(BFS(myGraph, "crocodiles", "bees"));

        System.out.println(BFS(myGraph, "crocodiles", "crocodiles"));

        System.out.println(BFS(myGraph, "crocodiles", "zebras"));

    }

}

输出

[crocodiles, lasers, sharks, bees]

[crocodiles]

null

解释

我做出的设计决策是为了避免在图中的每个节点上复制ArrayList，而是使用成对存储节点的哈希。这样，一旦我找到了目标节点，我就会回溯我的步骤，一次性创建路径，而不是为每个节点构建一个路径，其中大部分最终都无处可去。这在空间和时间上更有效率;Python使得使用O（n）列表串联运算符很容易破坏时间复杂性。pathvisitedchildNode => parentNode[] + []

使用HashMap在Java中编码也更容易，Java没有轻量级的//，可以方便地将不同类型的节点存储在队列中。要完成你在Python中将2元素列表传递到队列中所做的事情，你必须编写自己的类，使用两个ArrayDeques，或者避免泛型并使用强制转换，所有这些都很丑陋（特别是最后一个，这也是不安全的）。child => parentvisitedPairTuplestructPair

我在代码中注意到的另一个问题是将 ArrayList 用作队列。列表前面的插入和删除是 O（n） 操作，因为列表中的所有元素都必须在基础数组中向前或向后移动以保持排序。Java 中的最佳队列结构是 ArrayDeque，它在两端都提供 O（1） 添加和删除，并且与 Queue 集合不同，它不是线程安全的。

同样，在Python中，您会发现使用deque集合的性能最好，该集合为您的所有排队需求提供了快速操作。此外，在Python实现中，哈希中的每个键都指向一个，这是可以的，但是当列表可以时，这似乎是一个不必要的结构（你已经切换到Java中的原始数组）。如果您不操作图形而只是迭代邻居，则这似乎很理想。popleftset

请注意，此代码还假定每个节点在表示图形的哈希中都有一个键，就像您的输入一样。如果您计划输入节点在哈希中可能没有键的图形，则需要确保用检查来包装该图形以避免崩溃。graph.get(curr)containsKey

另一个值得一提的假设是：确保您的图形不包含 s，因为哈希依赖于指示子项没有父项并且是搜索的开始。nullvisitednull

Answer 2

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

public class Node {

    public String name;

    public ArrayList<Node> vertices;

    public void addEdge(Node node) {

        edges.add(node);

    }

}