Eine ausführliche Analyse der Prinzipien des BFS-Algorithmus mit illustrierten Erklärungen und Python-Code zur Implementierung des BFS-Algorithmus.

BFS, auch Breitensuche genannt, ist ein rekursiver Algorithmus wie der DFS-Algorithmus. Der Unterschied besteht darin, dass der BFS-Algorithmus eine Warteschlange verwendet, um alle Zielknoten zu durchlaufen und dabei Schleifen zu vermeiden.

Veranschaulichung des Funktionsprinzips des BFS-Algorithmus

Nehmen Sie als Beispiel einen ungerichteten Graphen mit 5 Knoten, wie unten gezeigt:

Ab Knoten 0 fügt der BFS-Algorithmus ihn zunächst in die Liste „Besucht“ ein und alle Nachbarknoten werden in eine Warteschlange gestellt.

Als nächstes besuchen Sie Knoten 1 am Anfang der Warteschlange und gehen Sie zu Knoten neben Knoten 1. Da Knoten 0 bereits besucht wurde, wird Knoten 2 besucht.

Knoten 2 hat einen unbesuchten Nachbarknoten 4, aber da Knoten 4 am Ende der Warteschlange steht, wollen wir zuerst Knoten 3 am Anfang der Warteschlange besuchen.

Nur Knoten 4 bleibt in der Warteschlange, der nicht besucht wurde, daher wird Knoten 4 zuletzt besucht.

Zu diesem Zeitpunkt ist die Breitendurchquerung dieses ungerichteten Graphen abgeschlossen.

Pseudocode des BFS-Algorithmus

create a queue Q 
mark v as visited and put v into Q 
while Q is non-empty 
remove the head u of Q 
mark and enqueue all (unvisited) neighbours of u

Python-Code zur Implementierung des BFS-Algorithmus

import collections
def bfs(graph, root):
    visited, queue = set(), collections.deque([root])
    visited.add(root)

while queue:
        vertex = queue.popleft()
        print(str(vertex) + " ", end="")

        for neighbour in graph[vertex]:
            if neighbour not in visited:
                visited.add(neighbour)
                queue.append(neighbour)

if __name__ == '__main__':
    graph = {0: [1, 2], 1: [2], 2: [3], 3: [1, 2]}
    print("Following is Breadth First Traversal: ")
    bfs(graph, 0)

Das obige ist der detaillierte Inhalt vonEine ausführliche Analyse der Prinzipien des BFS-Algorithmus mit illustrierten Erklärungen und Python-Code zur Implementierung des BFS-Algorithmus.. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!