Breitensuche in Python

Gepostet: 2019-12-01 15:55, Zuletzt aktualisiert: 2019-12-14 13:39

def bfs(graph, start):
    """
    Implementation of Breadth-First-Search (BFS) using adjacency matrix.
    This returns nothing (yet), it is meant to be a template for whatever you want to do with it,
    e.g. finding the shortest path in a unweighted graph.
    This has a runtime of O(|V|^2) (|V| = number of Nodes), for a faster implementation see @see ../fast/BFS.java (using adjacency Lists)
    :param graph: an adjacency-matrix-representation of the graph where (x,y) is True if the the there is an edge between nodes x and y.
    :param start: the node to start from.
    :return: Array array containing the shortest distances from the given start node to each other node
    """
    # A Queue to manage the nodes that have yet to be visited, intialized with the start node
    queue = [start]
    # A boolean array indicating whether we have already visited a node
    visited = [False] * len(graph)
    # (The start node is already visited)
    visited[start] = True
    # Keeping the distances (might not be necessary depending on your use case)
    distances = [float("inf")] * len(
        graph)  # Technically no need to set initial values since every node is visted exactly once
    # (the distance to the start node is 0)
    distances[start] = 0
    # While there are nodes left to visit...
    while len(queue) > 0:
        print("Visited nodes: " + str(visited))
        print("Distances: " + str(distances))
        node = queue.pop(0)
        print("Removing node " + str(node) + " from the queue...")
        # ...for all neighboring nodes that haven't been visited yet....
        for i in range(len(graph[node])):
            if graph[node][i] and not visited[i]:
                # Do whatever you want to do with the node here.
                # Visit it, set the distance and add it to the queue
                visited[i] = True
                distances[i] = distances[node] + 1
                queue.append(i)
                print("Visiting node " + str(i) + ", setting its distance to " + str(
                    distances[i]) + " and adding it to the queue")

    print("No more nodes in the queue. Distances: " + str(distances))
    return distances

Über den Algorithmus und die Programmiersprache in diesem Snippet:

Breitensuche Algorithmus

Der Breitensuchalgorithmus (Breadth-first-search, BFS) ist ein Algorithmus, der verwendet wird, um das Problem des kürzesten Pfades in einem Graphen ohne Kantengewichte zu lösen (d.h. ein Diagramm, in dem alle Knoten den gleichen “Abstand” voneinander haben und entweder verbunden sind oder nicht). Dies bedeutet, dass bei einer Anzahl von Knoten und den Kanten zwischen ihnen der Breitensuchalgorithmus den kürzesten Weg vom angegebenen Startknoten zu allen anderen Knoten findet.

Beschreibung des Algorithmus

Das Grundprinzip des Breitensuchalgorithmus besteht darin, den aktuellen Knoten (den Startknoten am Anfang) zu nehmen und dann alle seine Nachbarn, die wir noch nicht besucht haben, zu einer Warteschlange hinzuzufügen. Fahren Sie mit dem nächsten Knoten in der Warteschlange fort (in einer Warteschlange, die der “älteste” Knoten ist). Bevor wir der Warteschlange einen Knoten hinzufügen, setzen wir seinen Abstand auf den Abstand des aktuellen Knotens plus 1 (da alle Kanten gleich gewichtet sind), wobei der Abstand zum Startknoten 0 ist. Dies wird wiederholt, bis sich keine Knoten mehr in der Warteschlange befinden (alle Knoten werden besucht).

Im Einzelnen führt dies zu den folgenden Schritten:

Initialisieren Sie die Entfernung zum Startknoten als 0. Die Entfernungen zu allen anderen Knoten müssen nicht initialisiert werden, da jeder Knoten genau einmal besucht wird.
Setzen Sie alle Knoten auf “nicht besucht”.
Fügen Sie den ersten Knoten zur Warteschlange hinzu und kennzeichnen Sie ihn als besucht.
Während sich Knoten in der Warteschlange befinden:
1. Nehmen Sie einen Knoten aus der Warteschlange
2. Fügen Sie für alle Knoten daneben, die wir noch nicht besucht haben, sie der Warteschlange hinzu, stellen Sie ihre Entfernung auf die Entfernung zum aktuellen Knoten plus 1 ein und legen Sie sie als “besucht” fest.

Am Ende sind die Abstände zu allen Knoten korrekt.

Beispiel des Algorithmus

Betrachten Sie das folgende Diagramm:

Die Schritte, die der Algorithmus in diesem Diagramm ausführt, wenn der Knoten 0 als Startpunkt angegeben wird, sind:

Besuche Knoten 0
Besuchte Knoten: [wahr, falsch, falsch, falsch, falsch, falsch], Entfernungen: [0, 0, 0, 0, 0, 0]
1. Knoten 0 aus der Warteschlange entfernen …
2. Besuchen Sie Knoten 1, setzen Sie seinen Abstand auf 1 und fügen Sie ihn der Warteschlange hinzu
3. Besuchen Sie Knoten 2, setzen Sie seinen Abstand auf 1 und fügen Sie ihn der Warteschlange hinzu
Besuchte Knoten: [wahr, wahr, wahr, falsch, falsch, falsch], Entfernungen: [0, 1, 1, 0, 0, 0]
1. Entfernen von Knoten 1 aus der Warteschlange …
2. Besuchen Sie Knoten 3, setzen Sie seinen Abstand auf 2 und fügen Sie ihn der Warteschlange hinzu
3. Besuchen Sie Knoten 4, stellen Sie seinen Abstand auf 2 ein und fügen Sie ihn der Warteschlange hinzu
Besuchte Knoten: [wahr, wahr, wahr, wahr, wahr, falsch], Entfernungen: [0, 1, 1, 2, 2, 0]
1. Entfernen von Knoten 2 aus der Warteschlange …
2. Keine benachbarten, nicht besuchten Knoten
Besuchte Knoten: [wahr, wahr, wahr, wahr, wahr, falsch], Entfernungen: [0, 1, 1, 2, 2, 0]
1. Entfernen von Knoten 3 aus der Warteschlange …
2. Besuchen Sie Knoten 5, stellen Sie seinen Abstand auf 3 ein und fügen Sie ihn der Warteschlange hinzu
Besuchte Knoten: [wahr, wahr, wahr, wahr, wahr, wahr], Entfernungen: [0, 1, 1, 2, 2, 3]
1. Entfernen von Knoten 4 aus der Warteschlange …
2. Keine benachbarten, nicht besuchten Knoten
Besuchte Knoten: [wahr, wahr, wahr, wahr, wahr, wahr], Entfernungen: [0, 1, 1, 2, 2, 3]
1. Entfernen von Knoten 5 aus der Warteschlange …
Keine Knoten mehr in der Warteschlange. Endabstände: [0, 1, 1, 2, 2, 3]

Laufzeitkomplexität des Algorithmus

Die Laufzeitkomplexität der Breitensuche beträgt O(|E| + |V|) (|V| = Anzahl der Knoten, |E| = Anzahl der Kanten), wenn Adjazenzlisten verwendet werden. Wenn wir einfach alle Knoten durchsuchen, um in jedem Schritt verbundene Knoten zu finden, und mithilfe einer Matrix nachsehen, ob zwei Knoten benachbart sind, steigt die Laufzeitkomplexität auf O(|V|^2).

Abhängig vom Diagramm spielt dies möglicherweise keine Rolle, da die Anzahl der Kanten bis zu |V|^2 betragen kann, wenn alle Knoten miteinander verbunden sind.

Speicherplatzkomplexität des Algorithmus

Die Speicherplatzkomplexität der Breitensuche hängt auch davon ab, wie sie implementiert ist, und entspricht der Laufzeitkomplexität.

Breitensuche Algorithmus in anderen Programmierspraches:

Breitensuche in allen Programmiersprachen

Python

Python™ ist eine interpretierte Sprache, die für viele Zwecke verwendet wird, von der eingebetteten Programmierung bis zur Webentwicklung, wobei einer der größten Anwendungsfälle die Datenwissenschaft ist.

In Python zu “Hello World”

Das Wichtigste zuerst - so können Sie Ihre erste Codezeile in Python ausführen:

Laden Sie die neueste Version von Python von python.org herunter und installieren Sie sie. Sie können auch eine frühere Version herunterladen, wenn Ihr Anwendungsfall dies erfordert. Viele Technologien erfordern dies aufgrund der mit Python 3 eingeführten Änderungen weiterhin.
Öffnen Sie ein Terminal, stellen Sie sicher, dass der Befehl “python” oder “python3” funktioniert und dass der Befehl, den Sie verwenden, sich auf die Version bezieht, die Sie gerade installiert haben, indem Sie “python3 —version” oder “python —version” ausführen. Wenn der Fehler “Befehl nicht gefunden” (oder ähnliches) angezeigt wird, starten Sie die Befehlszeile, und, falls dies nicht hilft, Ihren Computer neu. Wenn das Problem weiterhin besteht, finden Sie hier einige hilfreiche Fragen zu StackOverflow für Windows, Mac und Linux.
Sobald dies funktioniert, können Sie das folgende Snippet ausführen: print("Hello World"). Sie haben zwei Möglichkeiten, dies auszuführen: 3.1 Führen Sie “python” in der Befehlszeile aus, fügen Sie einfach das Code-Snippet ein und drücken Sie die Eingabetaste (Drücken Sie “STRG + D” oder schreiben Sie “exit ()” und drücken Sie die Eingabetaste, um das Programm zu beenden). 3.2 Speichern Sie das Snippet in einer Datei und nennen Sie es etwas, das mit “.py” endet, z.B. hello_world.py und führepython path / to / hello_world.py aus. Tipp: Verwenden Sie den Befehl ls (dir in Windows), um herauszufinden, welche Dateien sich in dem Ordner befinden, in dem sich Ihre Befehlszeile gerade befindet.

Das wars schon! Beachten Sie, dass das Drucken von etwas auf die Konsole in Python nur eine einzige Zeile ist - diese niedrige Eintrittsbarriere und das Fehlen von erforderlichem Boilerplate-Code machen einen großen Teil der Attraktivität von Python aus.

Grundlagen in Python

Um in Python implementierte Algorithmen und Technologien zu verstehen, muss man zunächst verstehen, wie grundlegende Programmierkonzepte in dieser bestimmten Sprache aussehen.

Variablen und Arithmetik

Variablen in Python sind wirklich einfach. Sie müssen weder einen Datentyp deklarieren noch deklarieren, dass Sie eine Variable definieren. Python weiß das implizit.

a = 1
b = {'c':2}

print(a + b['c']) # prints 3

Arrays

Das Arbeiten mit Arrays ist in Python ähnlich einfach:

arr = ["Hello", "World"]

print(arr[0]) # Hello
print(arr[1]) # World
# print(arr[2]) # IndexError

arr.append("!")

print(arr[2]) # !

Wie diejenigen von Ihnen, die mit anderen Programmiersprachen wie Java vertraut sind, möglicherweise bereits bemerkt haben, handelt es sich nicht um native Arrays, sondern um Listen, die wie Arrays gekleidet sind. Dies wird durch die Tatsache deutlich, dass keine Größe angegeben werden muss und Elemente nach Belieben angehängt werden können. Tatsächlich druckt print (type (arr)) <class ‘list’> `. Dies bedeutet, dass Arrays in Python erheblich langsamer sind als in Programmiersprachen niedrigerer Ebene. Es gibt jedoch Pakete wie numpy, die echte Arrays implementieren, die erheblich schneller sind.

Bedingungen

Wie die meisten Programmiersprachen kann Python “if-else”-Anweisungen ausführen:

value = 1
if value==1:
    print("Value is 1")
elif value==2:
    print("Value is 2")
else:
    print("Value is something else")

Python hat jedoch keine “case”-Anweisungen, die andere Sprachen wie Java haben. Meiner Meinung nach kann dies durch die Einfachheit der “if”-Anweisungen entschuldigt werden, die den “syntaktischen Zucker” von “case” -Anweisungen überflüssig machen.

Schleifen

Python unterstützt sowohl “for” - als auch “while” -Schleifen sowie “break” - und “continue” -Anweisungen. Es gibt zwar keine “do-while” -Schleifen, aber eine Reihe von integrierten Funktionen, die das Schleifen sehr bequem machen, wie “enumerate” oder “range”. Hier sind einige Beispiele:

value = 10
while value > 0:
    print(value)
    value -= 1

for index, character in enumerate("banana"):
    print("The %d-th letter is a %s" % (index + 1, character))

Beachten Sie, dass Python nicht die gemeinsame Iteratorvariablensyntax anderer Sprachen verwendet (z. B. for (int i = 0; i <arr.length; i ++) in Java) - hierfür kann die Funktion enumerate verwendet werden.

Funktionen

Funktionen in Python sind einfach zu definieren und erfordern zum Guten oder Schlechten keine Angabe von Rückgabe- oder Argumenttypen. Optional kann ein Standardwert für Argumente angegeben werden:

def print_something(something="Hello World"):
    print(something)
    return "Success"

print_something()
print(print_something("banana"))

(Dies druckt “Hallo Welt”, “Banane” und dann “Erfolg”)

Syntax

Sie haben vielleicht bemerkt, dass Python keine geschweiften Klammern ({}) verwendet, um Codeblöcke in Bedingungen, Schleifen, Funktionen usw. zu umgeben. Dies liegt daran, dass Python als Teil seiner Syntax von Einrückungen (Leerzeichen) abhängt. Während Sie in Java beliebig viele Leerzeichen (Leerzeichen, Tabulatoren, Zeilenumbrüche) hinzufügen und löschen können, ohne das Programm zu ändern, wird die Syntax in Python dadurch unterbrochen. Dies bedeutet auch, dass keine Semikolons erforderlich sind, was in anderen Sprachen ein häufiger Syntaxfehler ist.

Fortgeschrittene Kenntnisse in Python

Python wurde erstmals 1990 veröffentlicht und ist ein Multi-Paradigma. Das bedeutet, dass es in erster Linie zwingend und funktional ist, aber auch objektorientierte und reflektierende Elemente enthält. Es ist dynamisch typisiert, bietet jedoch seit Version 3.5 Syntax für die schrittweise Eingabe. Für weitere Informationen hat Python einen großartigen Artikel Wikipedia.

Andere Algorithmen in Python:

Alle Algorithmen in Python