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