擅长:python、mysql、java
<p>您的算法中有两个错误。最重要的是:</p>
<pre><code>distanceDict[vertex] = distanceDict[curr] + 1
</code></pre>
<p>这可能会用更差的距离覆盖现有距离。所以你应该:</p>
<pre><code>distanceDict[vertex] = min(distanceDict[vertex], distanceDict[curr] + 1)
</code></pre>
<p>并且,<code>distanceDict</code>中缺少一个顶点,因为节点36没有传出边。这可能不是一个真正的错误,而是一个遗漏。但是,在图形中为<em>所有</em>节点设置一个条目是合乎逻辑的。因此,您应该处理这个问题,例如通过初始化:</p>
<pre><code>distanceDict[target] = INT_MAX
</code></pre>
<p>找到目标后退出循环也是一个好主意,这样可以避免不必要地访问所有其他节点,这永远不会改变结果</p>
<p>最后,不需要跟踪每个节点与源的距离,也不需要使用队列。如果分隔BFS遍历树的每个“级别”,则可以为每个级别使用新列表,并增加单个距离变量以跟踪它</p>
<pre><code>def distanceBFS(self, src, target):
distance = 0
visited = set()
frontier = [src]
while frontier:
if target in frontier:
return distance # found
visited.update(frontier)
frontier = [vertex for curr in frontier for vertex in self.vertList[curr]
if vertex not in visited]
distance += 1
return -1 # cannot be reached
</code></pre>
<p>请注意,此函数<em>返回距离</em>,因此仍需打印:</p>
<pre><code>print(self.distanceBFS(0, 36))
</code></pre>