<p>基本上,问题在于以下代码块:</p>
<pre><code> queue.append(src)
distanceDict[src] = 0
visited = set()
while (len(queue) > 0):
curr = queue.pop(0)
visited.add(curr)
for vertex in self.vertList[curr]:
if vertex not in visited:
queue.append(vertex)
distanceDict[vertex] = distanceDict[curr] + 1
</code></pre>
<p>我将尝试用以下基本图表来解释这一点:</p>
<p><a href="https://i.stack.imgur.com/A5ezE.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/A5ezE.png" alt="enter image description here"/></a></p>
<p>假设,您需要在下图中找到从顶点<code>1</code>到顶点<code>3</code>的最短路径。使用上述实现,您将有以下迭代:</p>
<ol>
<li>将顶点<code>1</code>添加到队列<code>Q</code>,并将其距离设置为<code>0</code></li>
<li>接下来,在<code>while</code>循环中从<code>Q</code>弹出<code>1</code>,并将其标记为已访问</li>
<li>接下来,访问它的所有邻居并将它们添加到队列<code>Q</code></李>
</ol>
<p>因此,此时,不同对象的状态如下所示:</p>
<p>我们在队列<code>Q</code>中有顶点<code>2</code>和<code>3</code>,而<code>distance</code>字典将作为<code>distance[1] = 0, distance[2] = 1, distance[3] = 1</code>,这就是问题的开始,因为我们还没有将顶点<code>2</code>和<code>3</code>添加到<code>visited</code>如果我们从其他邻居处再次访问这些顶点,我们将在下一次迭代中再次开始更新这些顶点的距离</p>
<ol start=“4”>
<li>再次回到我们的算法,现在我们再次转到<code>while</code>循环的开始,从它开始<code>pop</code>顶点<code>2</code>,并将其标记为已访问</李>
<li>当我们下一步通过其未访问的邻居时,我们将再次访问我们已经访问过的<code>3</code>,并将使用不正确的值更新<code>distance</code>字典</李>
</ol>
<p>访问vertex<code>2</code>及其相邻对象后,不同对象的状态如下:</p>
<p>我们在队列中有顶点<code>3</code>,距离字典将为<code>distance[1] = 0, distance[2] = 1, distance[3] = 2</code><code>distance[3]</code>被错误地更新了,正如我们在迭代中看到的那样</p>
<p>然而,修复是非常直接的,在这里,我们需要在访问顶点之后将其标记为已访问,这样我们就不会通过其他邻居将其再次放入队列中</p>
<p>到目前为止,您已经猜到BFS函数的正确实现应该如下所示:</p>
<pre><code>from collections import defaultdict
global INT_MAX
INT_MAX = 3 ** 38
class Graph:
def __init__(self):
self.vertList = defaultdict(list)
def addEdge(self, u, v):
self.vertList[u].append(v)
def distanceBFS(self, src, target):
queue = []
queue.append(src)
distanceDict = {}
for v in self.vertList:
distanceDict[v] = INT_MAX
distanceDict[src] = 0
visited = set()
visited.add(src)
while (len(queue) > 0):
curr = queue.pop(0)
for vertex in self.vertList[curr]:
if vertex not in visited:
queue.append(vertex)
visited.add(vertex)
distanceDict[vertex] = distanceDict[curr] + 1
print(distanceDict[target])
def solveSnakesLadder(self):
snakeLadderDict = {2: 13, 5: 2, 9: 18, 18: 11, 17: -13, 20: -14, 24: -8, 25: 10, 32: -2, 34: -22}
# we have 36 boxes > i
# we can throw a dice at each of these 36 boxes and it can be from 1 to 6
# j is new position on the board after throwing a dice
for i in range(0, 37):
for dice in range(1, 7):
j = i + dice
if j in snakeLadderDict:
j += snakeLadderDict[j]
if j <= 36:
self.addEdge(i, j)
self.distanceBFS(0, 36)
g = Graph()
g.solveSnakesLadder()
</code></pre>