这个广度优先搜索在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<>();
            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 1

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

public class Node {
    public String name;
    public ArrayList<Node> vertices;
    public void addEdge(Node node) {
        edges.add(node);
    }
}

Answer 2

翻译辛苦了。让我提供我的代码，然后是解释：

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

说明

我做出了设计决定，避免在图中的每个节点上复制 path ArrayList，以支持 visited 散列，该散列将节点存储在 childNode => parentNode 对中。这样，一旦我找到了目标节点，我就会回溯我的步骤以一次性创建路径，而不是为每个节点构建路径，其中大部分最终无处可去。这在 space 和时间上更有效率； Python 使用 [] + [] O(n) 列表连接运算符很容易破坏你的时间复杂度。

使用 child => parent visited HashMap 也更易于在 Java 中编码，它没有轻量级 Pair/Tuple/ struct 可以方便的将不同的类型存储为队列中的节点。要执行您在 Python 中所做的将 2 元素列表传递到队列中的操作，您要么必须编写自己的 Pair class，要么使用两个 ArrayDeques，要么避免泛型和使用转换，所有这些都很丑陋（尤其是最后一个，也是不安全的）。

我在您的代码中注意到的另一个问题是将 ArrayList 用作队列。在列表的前面插入和删除是一个 O(n) 操作，因为列表中的所有元素都必须在底层数组中向前或向后移动以保持顺序。 Java 中的最佳队列结构是 ArrayDeque, which offers O(1) add and removal at both ends and is not thread safe, unlike the Queue 集合。

同样，在 Python 中，您会发现使用 deque collection 性能最佳，它提供了一个快速的 popleft 操作来满足您的所有排队需求。此外，在您的 Python 实现中，散列中的每个键都指向一个 set，这没关系，但是当列表可以执行时似乎是一个不必要的结构（您已切换到原始数组Java)。如果您不操纵图形而只迭代邻居，这似乎很理想。

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

另一个值得一提的假设：确保你的图表不包含 null，因为 visited 哈希依赖于 null 来表明 child 没有 parent 并且是搜索的开始。

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

How would this Breadth-First-Search be converted into a static method in Java?

java

python

search

breadth-first-search

输出

说明