<p>努力翻译。让我给出我的代码,然后解释一下:</p>
<pre><code>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"));
}
}
</code></pre>
<h3>输出</h3>
<pre class="lang-none prettyprint-override"><code>[crocodiles, lasers, sharks, bees]
[crocodiles]
null
</code></pre>
<hr/>
<h2>解释</h2>
<p>我做出的设计决定是为了避免在图中的每个节点上复制<code>path</code>数组列表,而使用<code>visited</code>散列将节点存储在<code>childNode => parentNode</code>对中。这样,一旦我找到了目标节点,我就可以一步一个脚印地创建路径,而不是为每个节点构建一条路径,因为大多数节点最终都不会指向任何地方。这在空间和时间上更有效;Python使用<code>[] + []</code>O(n)list串联操作符很容易破坏时间复杂性。你知道吗</p>
<p>使用<code>child => parent</code><code>visited</code>HashMap在Java中编写代码也比较简单,因为Java没有轻量级的<code>Pair</code>/<code>Tuple</code>/<code>struct</code>可以方便地将不同类型存储为队列中的节点。要完成在Python中将2元素列表传递到队列中所做的工作,您必须编写自己的<code>Pair</code>类,使用两个ArrayDeques,或者避免泛型并使用casting,所有这些都很难看(尤其是最后一个,这也是不安全的)。你知道吗</p>
<p>我在代码中注意到的另一个问题是使用ArrayList作为队列。列表前面的插入和删除是一个O(n)操作,因为列表中的所有元素都必须在底层数组中向前或向后移动才能保持顺序。Java中的最佳队列结构是<a href="https://docs.oracle.com/javase/7/docs/api/java/util/ArrayDeque.html" rel="nofollow noreferrer">ArrayDeque</a>,与<a href="https://docs.oracle.com/javase/7/docs/api/java/util/Queue.html" rel="nofollow noreferrer">Queue</a>集合不同,它在两端提供O(1)添加和删除,并且不是线程安全的。你知道吗</p>
<p>类似地,在Python中,您会发现使用<a href="https://docs.python.org/2/library/collections.html#collections.deque" rel="nofollow noreferrer">deque collection</a>的性能最好,它为您的所有排队需求提供了一个快速的<code>popleft</code>操作。此外,在Python实现中,散列中的每个键都指向<code>set</code>,这是可以的,但是当列表可以做到这一点时,它似乎是一个不必要的结构(您已经切换到Java中的基本数组)。如果您不操纵图形,只在邻居上迭代,这似乎是理想的。你知道吗</p>
<p>请注意,此代码还假定每个节点在表示图形的哈希中都有一个键,就像您的输入一样。如果您计划输入节点在散列中可能没有键的图,则需要确保用<code>graph.get(curr)</code>检查来包装<code>containsKey</code>,以避免崩溃。你知道吗</p>
<p>另一个值得一提的假设是:确保您的图不包含<code>null</code>,因为<code>visited</code>散列依赖于<code>null</code>来指示子级没有父级,并且是搜索的开始。你知道吗</p>