我用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);
.
.
.
}
}
}
在翻译上做得很好。让我提供我的代码，然后解释一下：
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
解释
我做出的设计决定是避免在图形中的每个节点上复制pathArrayList，而支持将节点存储在childNode => parentNode对中的visited哈希。这样，一旦我找到了目标节点，我就会回溯我的步骤，一次性创建路径，而不是为每个节点构建路径，其中大部分最终都无处可去。这在空间和时间上更有效;Python 很容易使用[] + []O(n) 列表连接运算符破坏您的时间复杂度。
使用child => parentvisitedHashMap在Java中编码也更简单，Java没有轻量级的Pair/Tuple/struct，可以方便地将不同类型的节点存储为队列中的节点。要完成你在 Python 中所做的将 2 元素列表传递到队列中，你必须编写自己的Pair类，使用两个 ArrayDeque，或者避免泛型并使用强制转换，所有这些都是丑陋的(尤其是最后一个，这也是不安全的)。
我在您的代码中注意到的另一个问题是将 ArrayList 用作队列。在列表前面插入和删除是 O(n) 操作，因为列表中的所有元素都必须在基础数组中向前或向后移动以保持排序。Java 中的最佳队列结构是 ArrayDeque，它在两端提供 O(1) 添加和删除，并且不像 Queue 集合那样是线程安全的。
同样，在 Python 中，您会发现使用 deque 集合的性能最好，该集合为您的所有排队需求提供了快速popleft操作。此外，在您的 Python 实现中，哈希中的每个键都指向一个set，这没关系，但当列表可以时，这似乎是不必要的结构(您已经切换到 Java 中的原始数组)。如果您不操作图形而只是迭代邻居，这似乎是理想的。
请注意，此代码还假定每个节点在哈希中都有一个表示图形的键，就像您的输入一样。如果您计划输入节点在哈希中可能没有键的图形，则需要确保用containsKey检查包装graph.get(curr)以避免崩溃。
另一个值得一提的假设是：确保你的图不包含null，因为visited哈希依赖于null来指示子项没有父项，并且是搜索的开始。
您需要创建一个单独的类来保存图形的节点。这些节点不可能是静态的，因为它们都有唯一的顶点。从那里开始，其余的非常相似。
public class Node {
public String name;
public ArrayList<Node> vertices;
public void addEdge(Node node) {
edges.add(node);
}
}