Как проследить путь в широте первого поиска?

мне очень понравился первый ответ Цяо! Единственное, чего здесь не хватает, это отметить вершины как посещенные.

Почему мы должны это делать?
Давайте представим, что есть еще один узел номер 13, подключенный от узла 11. Теперь наша цель-найти узел 13.
После небольшого прогона очередь будет выглядеть так:

[[1, 2, 6], [1, 3, 10], [1, 4, 7], [1, 4, 8], [1, 2, 5, 9], [1, 2, 5, 10]]

обратите внимание, что есть два пути с номером узла 10 в конце.
Это означает, что на пути от узла 10 будет проверено дважды. В этом случае это выглядит не так уж плохо, потому что узел № 10 не имеет детей.. Но это может быть очень плохо (даже здесь мы проверим этот узел дважды без причины..)
Номер узла 13 не находится в этих путях, поэтому программа не вернется до достижения второго пути с номером узла 10 в конце..И мы его перепроверим..

все, что нам не хватает, это набор, чтобы отметить посещенные узлы и не проверять их снова..
Это код Цяо после изменения:

graph = {
    1: [2, 3, 4],
    2: [5, 6],
    3: [10],
    4: [7, 8],
    5: [9, 10],
    7: [11, 12],
    11: [13]
}


def bfs(graph_to_search, start, end):
    queue = [[start]]
    visited = set()

    while queue:
        # Gets the first path in the queue
        path = queue.pop(0)

        # Gets the last node in the path
        vertex = path[-1]

        # Checks if we got to the end
        if vertex == end:
            return path
        # We check if the current node is already in the visited nodes set in order not to recheck it
        elif vertex not in visited:
            # enumerate all adjacent nodes, construct a new path and push it into the queue
            for current_neighbour in graph_to_search.get(vertex, []):
                new_path = list(path)
                new_path.append(current_neighbour)
                queue.append(new_path)

            # Mark the vertex as visited
            visited.add(vertex)


print bfs(graph, 1, 13)

вывод программы будет:

[1, 4, 7, 11, 13]

без ненужных перепроверок..

Я думал, что попробую закодировать это для удовольствия:

graph = {
        '1': ['2', '3', '4'],
        '2': ['5', '6'],
        '5': ['9', '10'],
        '4': ['7', '8'],
        '7': ['11', '12']
        }

def bfs(graph, forefront, end):
    # assumes no cycles

    next_forefront = [(node, path + ',' + node) for i, path in forefront if i in graph for node in graph[i]]

    for node,path in next_forefront:
        if node==end:
            return path
    else:
        return bfs(graph,next_forefront,end)

print bfs(graph,[('1','1')],'11')

# >>>
# 1, 4, 7, 11

Если вы хотите циклов вы можете добавить это:

for i, j in for_front: # allow cycles, add this code
    if i in graph:
        del graph[i]

очень простой код. Вы продолжаете добавлять путь каждый раз, когда обнаруживаете узел.

graph = {
         'A': set(['B', 'C']),
         'B': set(['A', 'D', 'E']),
         'C': set(['A', 'F']),
         'D': set(['B']),
         'E': set(['B', 'F']),
         'F': set(['C', 'E'])
         }
def retunShortestPath(graph, start, end):

    queue = [(start,[start])]
    visited = set()

    while queue:
        vertex, path = queue.pop(0)
        visited.add(vertex)
        for node in graph[vertex]:
            if node == end:
                return path + [end]
            else:
                if node not in visited:
                    visited.add(node)
                    queue.append((node, path + [node]))

мне нравится как первый ответ @Qiao, так и добавление @Or. Ради немного меньшей обработки я хотел бы добавить к ответу Or.

в ответе @Or отслеживание посещенного узла отлично. Мы также можем позволить программе выйти раньше, чем она есть в настоящее время. В какой-то момент в цикле for current_neighbour должны быть end, и как только это произойдет, будет найден самый короткий путь, и программа может вернуться.

Я бы изменил метод следующим образом, заплатите близко внимание на цикл for

graph = {
1: [2, 3, 4],
2: [5, 6],
3: [10],
4: [7, 8],
5: [9, 10],
7: [11, 12],
11: [13]
}


    def bfs(graph_to_search, start, end):
        queue = [[start]]
        visited = set()

    while queue:
        # Gets the first path in the queue
        path = queue.pop(0)

        # Gets the last node in the path
        vertex = path[-1]

        # Checks if we got to the end
        if vertex == end:
            return path
        # We check if the current node is already in the visited nodes set in order not to recheck it
        elif vertex not in visited:
            # enumerate all adjacent nodes, construct a new path and push it into the queue
            for current_neighbour in graph_to_search.get(vertex, []):
                new_path = list(path)
                new_path.append(current_neighbour)
                queue.append(new_path)

                #No need to visit other neighbour. Return at once
                if current_neighbour == end
                    return new_path;

            # Mark the vertex as visited
            visited.add(vertex)


print bfs(graph, 1, 13)

выход и все остальное будет таким же. Однако обработка кода займет меньше времени. Это особенно полезно на больших графиках. Я надеюсь, это поможет кому-то в будущем.