在Java中，如何将这个BreadthFirstSearch转换成静态方法？

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

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

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数组列表，而使用visited散列将节点存储在childNode => parentNode对中。这样，一旦我找到了目标节点，我就可以一步一个脚印地创建路径，而不是为每个节点构建一条路径，因为大多数节点最终都不会指向任何地方。这在空间和时间上更有效；Python使用[] + []O（n）list串联操作符很容易破坏时间复杂性。你知道吗

使用child => parentvisitedHashMap在Java中编写代码也比较简单，因为Java没有轻量级的Pair/Tuple/struct可以方便地将不同类型存储为队列中的节点。要完成在Python中将2元素列表传递到队列中所做的工作，您必须编写自己的Pair类，使用两个ArrayDeques，或者避免泛型并使用casting，所有这些都很难看（尤其是最后一个，这也是不安全的）。你知道吗

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

类似地，在Python中，您会发现使用deque collection的性能最好，它为您的所有排队需求提供了一个快速的popleft操作。此外，在Python实现中，散列中的每个键都指向set，这是可以的，但是当列表可以做到这一点时，它似乎是一个不必要的结构（您已经切换到Java中的基本数组）。如果您不操纵图形，只在邻居上迭代，这似乎是理想的。你知道吗

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

另一个值得一提的假设是：确保您的图不包含null，因为visited散列依赖于null来指示子级没有父级，并且是搜索的开始。你知道吗