BFS搜索算法

Question

我刚开始学习 Python，我正在尝试创建一个 bfs 算法，该算法可以采用加权图的顶点和 return bfs。最终，我需要将加权边添加到顶点，以便我可以计算行进的距离，但是我能够让 bfs 单独处理我的顶点。这是到目前为止的代码：

# Python implementation to find the
# shortest path in the graph using
# dictionaries

# Function to find the shortest
# path between two nodes of a graph
def BFS_SP(graph, start, goal):
    
    explored = []
    
    # Queue for traversing the
    # graph in the BFS
    queue = [[start]]
    
    # If the desired node is
    # reached
    if start == goal:
        print("Same Node")
        return
    
    # Loop to traverse the graph
    # with the help of the queue
    while queue:
        path = queue.pop(0)
        node = path[-1]
        
        # Condition to check if the
        # current node is not visited
        if node not in explored:
            neighbours = graph[node]
            
            # Loop to iterate over the
            # neighbours of the node
            for neighbour in neighbours:
                new_path = list(path)
                new_path.append(neighbour)
                queue.append(new_path)
                
                # Condition to check if the
                # neighbour node is the goal
                if neighbour == goal:
                    print("Shortest path = ", *new_path)
                    return
            explored.append(node)

    # Condition when the nodes
    # are not connected
    print("So sorry, but a connecting"\
                " path doesn't exist :(")
    return
# Driver Code
if __name__ == "__main__":
    
    # Graph using dictionaries
    graph = {
        'Arad':             ['Zerind', 'Timisoara', 'Sibiu'],
        'Bucharest':        ['Urziceni', 'Giurgiu', 'Pitesti', 'Fagaras'],
        'Craiova':          ['Dobreta', 'Pitesti', 'Rimnicu Vilcea'],
        'Dobreta':          ['Mehadia', 'Craiova'],
        'Eforie':           ['Hirsova'],
        'Fagaras':          ['Sibiu', 'Bucharest'],
        'Giurgiu':          ['Bucharest'],
        'Hirsova':          ['Eforie', 'Urziceni'],
        'Iasi':             ['Neamt', 'Vaslui'],
        'Lugoj':            ['Mehadia', 'Timisoara'],
        'Mehadia':          ['Lugoj', 'Dobreta'],
        'Neamt':            ['Iasi'],
        'Oradea':           ['Zerind', 'Sibiu'],
        'Pitesti':          ['Rimnicu Vilcea', 'Bucharest', 'Craiova'],
        'Rimnicu Vilcea':   ['Sibiu', 'Pitesti', 'Craiova'],
        'Sibiu':            ['Rimnicu Vilcea', 'Fagaras', 'Arad', 'Oradea'],
        'Timisoara':        ['Lugoj', 'Arad'],
        'Urziceni':         ['Bucharest', 'Hirsova'],
        'Vaslui':           ['Iasi', 'Urziceni'],
        'Zerind':           ['Oradea', 'Arad']
    }
    
    # Function Call
    BFS_SP(graph, 'Arad', 'Bucharest')

我需要我的图形数组看起来像这样：

graph = {
    'Arad':             [['Zerind', 75], ['Timisoara', 118], ['Sibiu', 140]],
    'Bucharest':        [['Urziceni', 85], ['Giurgiu', 90], ['Pitesti', 101], ['Fagaras', 211]],
    'Craiova':          [['Dobreta', 120], ['Pitesti', 138], ['Rimnicu Vilcea', 146]],
    'Dobreta':          [['Mehadia', 75], ['Craiova', 120]],
    'Eforie':           [['Hirsova', 86]],
    'Fagaras':          [['Sibiu', 99], ['Bucharest', 211]],
    'Giurgiu':          [['Bucharest', 90]],
    'Hirsova':          [['Eforie', 86], ['Urziceni', 98]],
    'Iasi':             [['Neamt', 87], ['Vaslui', 92]],
    'Lugoj':            [['Mehadia', 70], ['Timisoara', 111]],
    'Mehadia':          [['Lugoj', 70], ['Dobreta', 75]],
    'Neamt':            [['Iasi', 87]],
    'Oradea':           [['Zerind', 71], ['Sibiu', 151]],
    'Pitesti':          [['Rimnicu Vilcea', 97], ['Bucharest', 101], ['Craiova', 138]],
    'Rimnicu Vilcea':   [['Sibiu', 80], ['Pitesti', 97], ['Craiova', 146]],
    'Sibiu':            [['Rimnicu Vilcea', 80], ['Fagaras', 99], ['Arad', 140], ['Oradea', 151]],
    'Timisoara':        [['Lugoj', 111], ['Arad', 118]],
    'Urziceni':         [['Bucharest', 85], ['Hirsova', 98]],
    'Vaslui':           [['Iasi', 92], ['Urziceni', 142]],
    'Zerind':           [['Oradea', 71], ['Arad', 75]]
}

而且我对如何修改我的代码以将新版本的图形作为单个节点感到有些茫然。如果我根据需要在旧代码中实现我的新图形，我会收到一条错误消息：

Traceback (most recent call last):
  File "/Users/meikebuettner/hello/astar_test.py", line 79, in <module>
    BFS_SP(graph, 'Arad', 'Bucharest')
  File "/Users/meikebuettner/hello/astar_test.py", line 30, in BFS_SP
    neighbours = graph[node]
TypeError: unhashable type: 'list'

任何见解、帮助、想法或研究主题都将不胜感激！谢谢！！

Answer 1

问题是由于您将节点（新数据结构中的列表）添加到 new_path

引起的

for neighbour in neighbours: # neighbour: ['Rimnicu Vilcea', 97]
    ...
    new_path.append(neighbour)

new_path 预计只包含节点的名称，而不是名称和权重。

我们可以修正为：

for neighbour_node in neighbours:
    neighbour = neighbour_node[0]
    ...

此建议的原因：

neighbour_node 比邻居更正确，因为它代表节点，而不是邻居的名字。
我们可以在不修改那条线的情况下修复邻居和目标的比较

# Condition to check if the
# neighbour node is the goal
if neighbour == goal:

Note: there are several ways to fix your code, mine is just one. You can try the others like changing the data structure of path and new_path.

BFS搜索算法

BFS search algorithm

python

breadth-first-search