python - 关于使用 BFS 使用 Python 查找最短路径的问题

Question

我对 python 很陌生，目前正在解决来自hackerearth 的问题。（https://www.hackerearth.com/practice/algorithms/graphs/breadth-first-search/practice-problems/algorithm/monk-and-the-islands/）但需要一些帮助。问题是使用 BFS 算法找到从起始节点到结束节点的最短距离。我尝试了几种不同的方法，例如保持遍历节点的计数器并尝试遍历存储输入但没有成功的字典。任何帮助是极大的赞赏。

from collections import defaultdict

for i in range(int(input())):
    x = defaultdict(list)
    number_of_islands, number_of_pairs = list(map(int, input().split()))
    for i in range(number_of_pairs):
        island1, island2 = list(map(int, input().split()))
        x[island1].append(island2) 
        x[island2].append(island1) 
    startNode = min(x)
    visitedNodes = []
    queue = [startNode]
    while queue:
        (currentNode) = queue.pop(0)
        print('current', currentNode) # display currentNode
        print('visited', visitedNodes) # display visitedNodes
        visitedNodes.append(currentNode)
        for nextNode in x[currentNode]:
            if nextNode not in visitedNodes:
                queue.append(nextNode)

标签： pythonbreadth-first-searchshortest-path