Wie kann ich den Pfad in einer Breitensuche verfolgen?

104

Wie verfolgen Sie den Pfad einer Breitensuche, so dass im folgenden Beispiel:

Wenn Sie nach einem Schlüssel suchen 11, geben Sie die kürzeste Liste zurück, die 1 bis 11 verbindet.

[1, 4, 7, 11]
Christopher Markieta
quelle
6
Es war eigentlich eine alte Aufgabe, bei der ich vor Monaten einem Freund geholfen habe, basierend auf dem Kevin-Bacon-Gesetz. Meine endgültige Lösung war sehr schlampig. Ich habe im Grunde eine weitere Breitensuche durchgeführt, um zurückzuspulen und zurückzuverfolgen. Ich werde keine bessere Lösung finden.
Christopher Markieta
21
Ausgezeichnet. Ich denke darüber nach, ein altes Problem erneut zu betrachten, um eine bessere Antwort zu finden, um eine bewundernswerte Eigenschaft eines Ingenieurs zu sein. Ich wünsche Ihnen alles Gute für Ihr Studium und Ihre Karriere.
Peter Rowell
1
Vielen Dank für das Lob, ich glaube nur, wenn ich es jetzt nicht lerne, werde ich wieder mit dem gleichen Problem konfrontiert sein.
Christopher Markieta

Antworten:

193

Sie sollten zuerst auf http://en.wikipedia.org/wiki/Breadth-first_search schauen .


Unten ist eine schnelle Implementierung, in der ich eine Liste von Listen verwendet habe, um die Warteschlange von Pfaden darzustellen.

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

Ein anderer Ansatz wäre, eine Zuordnung von jedem Knoten zu seinem übergeordneten Knoten beizubehalten und bei der Inspektion des benachbarten Knotens seinen übergeordneten Knoten aufzuzeichnen. Wenn die Suche abgeschlossen ist, führen Sie einfach eine Rückverfolgung gemäß der übergeordneten Zuordnung durch.

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

Die obigen Codes basieren auf der Annahme, dass es keine Zyklen gibt.

Qiao
quelle
2
Das ist ausgezeichnet! Mein Denkprozess hat mich dazu gebracht, an die Erstellung einer Art Tabelle oder Matrix zu glauben. Ich muss noch etwas über Grafiken lernen. Danke dir.
Christopher Markieta
Ich habe auch versucht, einen Back-Tracing-Ansatz zu verwenden, obwohl dies viel sauberer zu sein scheint. Wäre es möglich, ein Diagramm zu erstellen, wenn Sie nur den Anfang und das Ende kennen, aber keinen der dazwischen liegenden Knoten? Oder noch ein anderer Ansatz als Grafiken?
Christopher Markieta
@ChristopherM Ich habe Ihre Frage nicht verstanden :(
Qiao
1
Ist es möglich, den ersten Algorithmus so anzupassen, dass alle Pfade von 1 bis 11 zurückgegeben werden (vorausgesetzt, es gibt mehr als einen)?
Maria Ines Parnisari
1
Es wird empfohlen, collection.deque anstelle einer Liste zu verwenden. Die Komplexität von list.pop (0) ist O (n), während deque.popleft () O (1) ist
Omar_0x80
23

Die erste Antwort von Qiao hat mir sehr gut gefallen! Das einzige, was hier fehlt, ist, die Scheitelpunkte als besucht zu markieren.

Warum müssen wir das tun?
Stellen wir uns vor, dass ein weiterer Knoten Nummer 13 mit Knoten 11 verbunden ist. Jetzt ist es unser Ziel, Knoten 13 zu finden.
Nach einem kurzen Lauf sieht die Warteschlange folgendermaßen aus:

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

Beachten Sie, dass es am Ende ZWEI Pfade mit der Knotennummer 10 gibt.
Dies bedeutet, dass die Pfade von Knoten Nummer 10 zweimal überprüft werden. In diesem Fall sieht es nicht so schlecht aus, weil Knoten Nummer 10 keine Kinder hat. Aber es könnte wirklich schlecht sein (auch hier werden wir diesen Knoten ohne Grund zweimal überprüfen.)
Knoten Nummer 13 ist nicht in Diese Pfade, damit das Programm nicht zurückkehrt, bevor es zum zweiten Pfad mit Knoten Nummer 10 am Ende gelangt. Und wir werden es erneut überprüfen.

Wir vermissen lediglich einen Satz, um die besuchten Knoten zu markieren und nicht erneut zu überprüfen.
Dies ist der Code von qiao nach der Änderung:

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)

Die Ausgabe des Programms lautet:

[1, 4, 7, 11, 13]

Ohne die Unccecery erneut zu prüfen ..

Oder Kazaz
quelle
6
Es kann nützlich sein, collections.dequefür queuelist.pop (0) O(n)Speicherbewegungen zu verwenden. Wenn Sie der Nachwelt halber DFS ausführen möchten, legen Sie einfach fest, path = queue.pop()in welchem ​​Fall sich die Variable queuetatsächlich wie eine verhält stack.
Sudhi
11

Sehr einfacher Code. Sie hängen den Pfad jedes Mal an, wenn Sie einen Knoten entdecken.

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]))
SeasonalShot
quelle
2
Ich finde Ihren Code im Vergleich zu anderen Antworten sehr lesbar. Vielen Dank!
Mitko Rusev
8

Ich dachte, ich würde versuchen, dies zum Spaß zu programmieren:

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

Wenn Sie Zyklen möchten, können Sie Folgendes hinzufügen:

for i, j in for_front: # allow cycles, add this code
    if i in graph:
        del graph[i]
Robert King
quelle
nachdem Sie die next_for_front erstellt haben. Eine Folgefrage, was ist, wenn das Diagramm Schleifen enthält? ZB wenn Knoten 1 eine Kante hatte, die sich wieder mit sich selbst verbindet? Was ist, wenn der Graph mehrere Kanten zwischen zwei Knoten hat?
Robert King
1

Ich mag sowohl die erste Antwort von @Qiao als auch die Hinzufügung von @ Or. Um etwas weniger zu verarbeiten, möchte ich die Antwort von Or ergänzen.

In der Antwort von @ Or ist es großartig, den besuchten Knoten zu verfolgen. Wir können auch zulassen, dass das Programm früher als derzeit beendet wird. Irgendwann in der for-Schleife muss der current_neighbourder sein end, und sobald dies geschieht, wird der kürzeste Pfad gefunden und das Programm kann zurückkehren.

Ich würde die Methode wie folgt modifizieren, genau auf die for-Schleife achten

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)

Die Ausgabe und alles andere wird gleich sein. Die Verarbeitung des Codes dauert jedoch weniger lange. Dies ist besonders nützlich bei größeren Diagrammen. Ich hoffe das hilft jemandem in der Zukunft.

Darie Dorlus
quelle