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

Как вы отслеживаете путь поиска в ширину, например, в следующем примере:

При поиске ключа 11верните самый короткий список, соединяющий с 1 по 11.

[1, 4, 7, 11]

Сначала вам следует взглянуть на http://en.wikipedia.org/wiki/Breadth-first_search .

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

# graph is in adjacent list representation
graph = {
        '1': ['2', '3', '4'],
        '2': ['5', '6'],
        '5': ['9', '10'],
        '4': ['7', '8'],
        '7': ['11', '12']
        }

def bfs(graph, start, end):
    # maintain a queue of paths
    queue = []
    # push the first path into the queue
    queue.append([start])
    while queue:
        # get the first path from the queue
        path = queue.pop(0)
        # get the last node from the path
        node = path[-1]
        # path found
        if node == end:
            return path
        # enumerate all adjacent nodes, construct a new path and push it into the queue
        for adjacent in graph.get(node, []):
            new_path = list(path)
            new_path.append(adjacent)
            queue.append(new_path)

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

Другой подход заключался бы в сохранении сопоставления каждого узла с его родителем и при проверке соседнего узла записывать его родительский узел. Когда поиск завершен, просто проследите в обратном направлении в соответствии с родительским отображением.

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

def backtrace(parent, start, end):
    path = [end]
    while path[-1] != start:
        path.append(parent[path[-1]])
    path.reverse()
    return path


def bfs(graph, start, end):
    parent = {}
    queue = []
    queue.append(start)
    while queue:
        node = queue.pop(0)
        if node == end:
            return backtrace(parent, start, end)
        for adjacent in graph.get(node, []):
            if node not in queue :
                parent[adjacent] = node # <<<<< record its parent 
                queue.append(adjacent)

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

Приведенные выше коды основаны на предположении, что циклов нет.

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

Зачем нам это нужно?
Представим себе, что есть еще один узел номер 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 в конце .. И мы перепроверим это ..

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

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 = {
         '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]))

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

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]

Мне нравится как первый ответ @Qiao, так и добавление @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)

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