Breitensuche in Javascript

Gepostet: , Zuletzt aktualisiert:

/**
 * 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
 */
const bfs = function (graph, start) {
    //A Queue to manage the nodes that have yet to be visited
    var queue = [];
    //Adding the node to start from
    queue.push(start);
    //A boolean array indicating whether we have already visited a node
    var visited = [];
    //(The start node is already visited)
    visited[start] = true;
    // Keeping the distances (might not be necessary depending on your use case)
    var distances = []; // 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 (queue.length > 0) {
        console.log("Visited nodes: " + visited);
        console.log("Distances: " + distances);
        var node = queue.shift();
        console.log("Removing node " + node + " from the queue...");
        //...for all neighboring nodes that haven't been visited yet....
        for (var i = 1; i < graph[node].length; i++) {
            if (graph[node][i] && !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.push(i);
                console.log("Visiting node " + i + ", setting its distance to " + distances[i] + " and adding it to the queue");

            }
        }
    }
    console.log("No more nodes in the queue. Distances: " + distances);
    return distances;
};

module.exports = {bfs};

Ü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:

  1. 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.
  2. Setzen Sie alle Knoten auf “nicht besucht”.
  3. Fügen Sie den ersten Knoten zur Warteschlange hinzu und kennzeichnen Sie ihn als besucht.
  4. 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:

Grafik für die erste Breitensuche

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

  1. Besuche Knoten 0
  2. 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
  3. 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
  4. 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
  5. 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
  6. 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
  7. Besuchte Knoten: [wahr, wahr, wahr, wahr, wahr, wahr], Entfernungen: [0, 1, 1, 2, 2, 3]

    1. Entfernen von Knoten 5 aus der Warteschlange …
  8. 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.

JavaScript

JavaScript ist eine interpretierte Skriptsprache, die zuvor hauptsächlich in Webseiten verwendet wurde (die in Browsern ausgeführt werden) und seitdem über node.js auch für Back-End- und andere Aufgaben beliebt ist

Während es einen Großteil seiner Syntax von Java entlehnt, ist es eine ganz andere Sprache und sollte nicht verwechselt werden.

Getting to “Hello World” in JavaScript

Das Wichtigste zuerst - hier erfahren Sie, wie Sie Ihre erste Codezeile in JavaScript ausführen können. Wenn Sie JavaScript für das Backend verwenden möchten, lesen Sie das Kapitel zum Drucken von Hello World mit Node.js. Wenn Sie JavaScript im Frontend (d. H. Auf Webseiten) verwenden möchten, lesen Sie das Kapitel zum Drucken von Hello World im Browser.

Getting to “Hello World” in JavaScript using the browser

  1. Erstellen Sie eine Datei mit dem Namen hello_world.html
  2. Öffnen Sie es mit einem Texteditor (z. B. Sublime Text oder nur mit dem Standard-Windows-Editor).
  3. Fügen Sie den folgenden Codeausschnitt ein:
<html>
<head>
    <script type="application/javascript">
        // This prints to the browsers console
        console.log("Hello World")
        // This opens a popup
        alert("Hello world")
    </script>
</head>
<body>
    (Website content)
</body>
</html>
  1. Öffnen Sie diese Datei mit Ihrem Browser (indem Sie den Speicherort in die Adressleiste eingeben).
  2. Sie sollten ein Popup mit der Aufschrift “Hallo Welt” sehen.
  3. Wenn Sie die Browserkonsole verwenden (z. B. in Chrome: Rechtsklick -> Überprüfen), wird diese auch dort gedruckt.

Der Grund, warum wir das Skript in HTML verpacken, ist, dass der Browser das JavaScript ansonsten nicht ausführt, sondern nur dessen Inhalt anzeigt.

Getting to “Hello World” in JavaScript using Node.js

  1. Laden Sie die neueste Version von Node.js von nodejs.org herunter und installieren Sie sie. Sie können auch eine frühere Version herunterladen, wenn Ihr Anwendungsfall dies erfordert.
  2. Öffnen Sie ein Terminal und stellen Sie sicher, dass der Befehl node funktioniert. Wenn der Fehler “Befehl nicht gefunden” (oder ähnlich) 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 jede Plattform:

  3. Sobald dies funktioniert, kopieren Sie das folgende Snippet in eine Datei mit dem Namen hello_world.js:

    console.log("Hello World");
  4. Wechseln Sie das Verzeichnis, indem Sie “cd path / to / helloworld” eingeben und dann “node helloworld.js” ausführen. Dies sollte “Hello World” auf Ihrem Terminal drucken.

Das ist es! Beachten Sie, dass die Eintrittsbarriere ähnlich niedrig ist wie bei Python und vielen anderen Skriptsprachen.

Fundamentals in JavaScript

Um in JavaScript implementierte Algorithmen und Technologien zu verstehen, muss man zunächst verstehen, wie grundlegende Programmierkonzepte in dieser bestimmten Sprache aussehen. Jedes der folgenden Snippets kann mit Node.js einzeln ausgeführt werden, da kein Boilerplate erforderlich ist. Im Browser muss der Code wie im Hello World-Beispiel für den oben gezeigten Browser von HTML umgeben sein.

Variables and Arithmetic

Variablen in JavaScript werden dynamisch typisiert, dh der Inhalt einer Variablen wird zur Laufzeit festgelegt und muss beim Schreiben des Codes nicht angegeben werden.

var number = 5;
var decimalNumber = 3.25;
var result = number * decimalNumber;
var callout = "The number is ";
// In this instance, the values are concatenated rather than added because one of them is a String.
console.log(callout + result);

Dies wird “The number is 16.25” drucken.

Arrays

Arrays in JavaScript werden als Objekte implementiert, wobei der Index nur der Name der Eigenschaft ist. Dies macht sie dynamisch dimensioniert. Die gesamten Konzepte von Objekten und Arrays werden in JavaScript zusammengeführt, wie das folgende Snippet zeigt.

var integers = {}; // initialized as object
integers[3] = 42; // assigned using array index
console.log(integers["3"]); // Accessed using property name, prints "42"

var strings = ["Hello"]; // strings[0] is now Hi
strings[2] = "World"; // index 1 skipped
strings.beautiful = "Beautiful" // Assigned using property name

console.log(strings[0] + " " + strings["beautiful"] + " " + strings[2]); // Prints "Hello World"

Conditions

Wie die meisten Programmiersprachen kann JavaScript “if-else” -Anweisungen ausführen. Darüber hinaus kann JavaScript auch “switch-case” -Anweisungen ausführen.

var value = 5;
if(value === 5){
    console.log("Value is 5");
} else if(value < 5){
    console.log("Value is less than 5");
} else {
    console.log("Value is something else");
}

switch (value){
    case 1:
        console.log("Value is 1");
        break; // Don't go further down the cases
    case 2:
        console.log("Value is 2");
        break; // Don't go further down the cases
    case 3:
        console.log("Value is 3");
        break; // Don't go further down the cases
    case 4:
        console.log("Value is 4");
        break; // Don't go further down the cases
    case 5:
        console.log("Value is 5");
        break; // Don't go further down the cases
    default:
        console.log("Value is something else");
}

Der obige JavaScript-Code gibt zweimal “Wert ist 5” aus.

Schleifen

JavaScript unterstützt sowohl for-, while- als auch do while-Schleifen. Die Anweisungen break undcontinue werden ebenfalls unterstützt. Das folgende Beispiel zeigt die Unterschiede:

var value = 2;
for (var i = 0; i < value; i++) {
    console.log(i);
}
while (value > 0) {
    console.log(value);
    value--;
}
do {
    console.log(value);
    value--;
} while (value > 0);

Dadurch wird Folgendes auf das Terminal gedruckt:

0
1
2
1
0

Beachten Sie die letzte “0”: Sie wird gedruckt, weil in der “do-while” -Schleife im Vergleich zur “while” -Schleife. Der Codeblock wird mindestens einmal ausgeführt, bevor die Bedingung überprüft wird.

Funktionen

Funktionen in JavaScript können mit vielen verschiedenen Syntaxen deklariert werden, z. B. als Objekteigenschaften, als Variablen oder in neueren JavaScript-Versionen als Teil einer Klasse.

Hier ist ein Beispiel für eine JavaScript-Funktion als Variable:

var my_function = function(){
    console.log("Hello World")
}

my_function()

Hier ist ein Beispiel für eine JavaScript-Funktion als Objekteigenschaft:

var function_object = {}
function_object.my_function = function(){
    console.log("Hello World")
}

function_object.my_function()

Und hier ist ein Beispiel für den Aufruf einer Funktion eines Objekts einer Klasse:

class FunctionClass {
    my_function(){
        console.log("Hello World")
    }
}

new FunctionClass().my_function();

(Alle diese Beispiele drucken “Hello World”.)

Syntax

Wie bereits erwähnt, teilt JavaScript einen Großteil seiner Syntax mit Java. JavaScript erfordert die Verwendung von geschweiften Klammern ({}), um Codeblöcke in Bedingungen, Schleifen, Funktionen usw.; Es sind nicht immer Semikolons am Ende von Anweisungen erforderlich, aber ihre Verwendung wird empfohlen, da ihre Verwendung bedeutet, dass die Verwendung von Leerzeichen für die bevorzugte Formatierung (z. B. Einrücken von Codeteilen) den Code nicht beeinflusst.

Fortgeschrittenes Wissen in JavaScript

JavaScript wurde erstmals 1993 veröffentlicht und ist ein Multi-Paradigma.

Es ist in erster Linie ereignisgesteuert und funktional, folgt aber auch objektorientierten und imperativen Paradigmen. Es ist dynamisch typisiert, bietet jedoch in neueren Versionen und Dialekten wie TypeScript eine gewisse statische Typisierung. Für weitere Informationen hat JavaScript einen großartigen Artikel Wikipedia.