Jak prześledzić ścieżkę w przeszukiwaniu wszerz?

Jak prześledzić ścieżkę przeszukiwania wszerz, tak jak w poniższym przykładzie:

Jeśli szukasz klucza 11, zwróć najkrótszą listę łączącą od 1 do 11.

[1, 4, 7, 11]

Najpierw powinieneś spojrzeć na http://en.wikipedia.org/wiki/Breadth-first_search .

Poniżej znajduje się szybka realizacja, w której użyłem listy do reprezentowania kolejki ścieżek.

# 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')

Innym podejściem byłoby zachowanie odwzorowania z każdego węzła na jego rodzica, a podczas inspekcji sąsiedniego węzła, zarejestrowanie jego rodzica. Po zakończeniu wyszukiwania po prostu prześledź wstecz zgodnie z mapowaniem nadrzędnym.

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')

Powyższe kody są oparte na założeniu, że nie ma cykli.

Bardzo podobała mi się pierwsza odpowiedź qiao! Jedyne, czego tu brakuje, to oznaczyć wierzchołki jako odwiedzone.

Dlaczego musimy to zrobić?
Wyobraźmy sobie, że jest inny węzeł numer 13 połączony z węzłem 11. Teraz naszym celem jest znalezienie węzła 13.
Po krótkim uruchomieniu kolejka będzie wyglądać następująco:

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

Zauważ, że istnieją DWIE ścieżki z numerem węzła 10 na końcu.
Co oznacza, że ​​ścieżki z węzła numer 10 zostaną sprawdzone dwukrotnie. W tym przypadku nie wygląda to tak źle, ponieważ węzeł numer 10 nie ma żadnych dzieci .. Ale może być naprawdę zły (nawet tutaj sprawdzimy ten węzeł dwa razy bez powodu ..)
Węzeł numer 13 nie jest w te ścieżki, aby program nie powrócił przed dotarciem do drugiej ścieżki z węzłem numer 10 na końcu .. i sprawdzimy to ponownie ..

Brakuje nam tylko zestawu do oznaczania odwiedzanych węzłów i nie sprawdzania ich ponownie.
Oto kod qiao po modyfikacji:

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)

Wynik programu będzie:

[1, 4, 7, 11, 13]

Bez zbędnych ponownych sprawdzeń.

Bardzo łatwy kod. Ciągle dołączasz ścieżkę za każdym razem, gdy odkryjesz węzeł.

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]))

Pomyślałem, że spróbuję to zakodować dla zabawy:

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

Jeśli chcesz cykli, możesz dodać to:

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

Podoba mi się zarówno pierwsza odpowiedź @Qiao, jak i dodatek @ Or. Ze względu na nieco mniej przetwarzania chciałbym dodać do odpowiedzi Ora.

W odpowiedzi @ Or, śledzenie odwiedzonego węzła jest świetne. Możemy także zezwolić programowi na wcześniejsze zakończenie pracy niż obecnie. W pewnym momencie pętli for current_neighbourbędzie musiało być end, a kiedy to nastąpi, zostanie znaleziona najkrótsza ścieżka i program może powrócić.

Zmodyfikowałbym metodę w następujący sposób, zwróć szczególną uwagę na pętlę 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)

Wynik i wszystko inne będzie takie samo. Jednak przetworzenie kodu zajmie mniej czasu. Jest to szczególnie przydatne na większych wykresach. Mam nadzieję, że to pomoże komuś w przyszłości.