我在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<>(); } }}
2 回答
一只斗牛犬
TA貢獻1784條經驗 獲得超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
解釋
我做出的設計決策是為了避免在圖中的每個節點上復制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
HUWWW
TA貢獻1874條經驗 獲得超12個贊
您需要創建一個單獨的類來保存圖形的節點。這些節點不能是靜態的，因為它們都有唯一的頂點。從那里開始，其余的非常相似。
public class Node {
public String name;
public ArrayList<Node> vertices;
public void addEdge(Node node) {
edges.add(node);
}
}
添加回答
舉報
0/150
提交
取消