Implementierung von Diagrammen in JavaScript

Ein Graph ist eine nichtlineare Datenstruktur, die eine Reihe von Scheitelpunkten (auch Knoten genannt) und die Beziehungen (oder Kanten) zwischen ihnen darstellt. Scheitelpunkte stellen Entitäten oder Objekte dar, während Kanten Beziehungen oder Verbindungen zwischen Scheitelpunkten darstellen. Mithilfe von Diagrammen können viele verschiedene Arten von Beziehungen modelliert werden, beispielsweise soziale Netzwerke, Transportsysteme oder Informationsflüsse.

Es gibt zwei Haupttypen von Graphen: gerichtete Graphen (auch gerichtete Graphen genannt) und ungerichtete Graphen. In einem gerichteten Graphen haben Kanten eine Richtung und können nur in einer Richtung durchlaufen werden, d. h. vom Startscheitelpunkt zum Endscheitelpunkt. In einem ungerichteten Graphen haben Kanten keine Richtung und können in beide Richtungen durchlaufen werden.

Implementierung von Bildern in JavaScript

Graphen können mithilfe von Adjazenzmatrizen oder Adjazenzlisten implementiert werden. Hier implementieren wir Diagramme in JavaScript mithilfe von Adjazenzlisten.

Diagrammklasse erstellen

Hier erstellen wir einen Entwurf des Grafikunterrichts.

class Graph {
   constructor() {
      this.adjacencyList = {};
   }
}

Scheitelpunkte hinzufügen

Diese Funktion fügt dem Diagramm einen neuen Scheitelpunkt (oder Knoten) hinzu, indem sie einen neuen Schlüssel im adjacencyList-Objekt erstellt und ein leeres Array als Wert angibt. Der neue Scheitelpunkt dient als Schlüssel und das leere Array wird zum Speichern seiner Nachbarn verwendet.

addVertex(vertex) {
   if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
}

Kanten hinzufügen

Diese Funktion fügt eine neue Kante zwischen zwei Eckpunkten hinzu. Es akzeptiert zwei Parameter: vertex1 und vertex2 und fügt vertex2 zum Nachbarn-Array von vertex1 hinzu und umgekehrt. Dadurch entsteht eine Verbindung zwischen den beiden Eckpunkten.

addEdge(vertex1, vertex2) {
   this.adjacencyList[vertex1].push(vertex2);
   this.adjacencyList[vertex2].push(vertex1);
}

Diagramm drucken

Diese Funktion protokolliert das Diagramm in der Konsole. Es durchläuft jeden Scheitelpunkt im adjacencyList-Objekt und zeichnet den Scheitelpunkt und seine Nachbarn auf.

print() {
   for (const [vertex, edges] of Object.entries(this.adjacencyList)) {
      console.log(`${vertex} -> ${edges.join(", ")}`);
   }
}

Beispiel

Im folgenden Beispiel definieren wir ein Diagramm und fügen dem Diagramm Scheitelpunkte und Kanten hinzu. Drucken Sie abschließend das Diagramm aus.

class Graph {
   constructor() {
      this.adjacencyList = {};
   }
   addVertex(vertex) {
      if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
   }
   addEdge(vertex1, vertex2) {
      this.adjacencyList[vertex1].push(vertex2);
      this.adjacencyList[vertex2].push(vertex1);
   }
   print() {
      for (const [vertex, edges] of Object.entries(this.adjacencyList)) {
         console.log(`${vertex} -> ${edges.join(", ")}`);
      }
   }
}
const graph = new Graph();
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
graph.addVertex("D");
graph.addEdge("A", "B");
graph.addEdge("A", "C");
graph.addEdge("B", "D");
graph.addEdge("C", "D");
console.log("Graph:");
graph.print();

Ausgabe

Graph:
A -> B, C
B -> A, D
C -> A, D
D -> B, C

Kante löschen

Diese Funktion löscht die Kante zwischen zwei Eckpunkten. Es benötigt zwei Parameter: vertex1 und vertex2 und filtert vertex2 aus dem Nachbararray von vertex1 und umgekehrt.

removeEdge(vertex1, vertex2) {
   this.adjacencyList[vertex1] = this.adjacencyList[vertex1].filter(
      (v) => v !== vertex2
   );
   this.adjacencyList[vertex2] = this.adjacencyList[vertex2].filter(
      (v) => v !== vertex1
   );
}

Scheitelpunkte löschen

Diese Funktion entfernt einen Scheitelpunkt aus dem Diagramm. Es nimmt ein Scheitelpunktargument und entfernt zunächst alle mit diesem Scheitelpunkt verbundenen Kanten. Anschließend wird der Schlüssel aus dem adjacencyList-Objekt entfernt.

removeVertex(vertex) {
   while (this.adjacencyList[vertex].length) {
      const adjacentVertex = this.adjacencyList[vertex].pop();
      this.removeEdge(vertex, adjacentVertex);
   }
   delete this.adjacencyList[vertex];
}

Beispiel

Im folgenden Beispiel definieren wir ein Diagramm, fügen Eckpunkte und Kanten hinzu und drucken dann das Diagramm aus. Wir entfernen eine Kante AC aus dem Diagramm und drucken schließlich das resultierende Diagramm aus.

class Graph {
   constructor() {
      this.adjacencyList = {};
   }
   addVertex(vertex) {
      if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
   }
   addEdge(vertex1, vertex2) {
      this.adjacencyList[vertex1].push(vertex2);
      this.adjacencyList[vertex2].push(vertex1);
   }
   removeEdge(vertex1, vertex2) {
      this.adjacencyList[vertex1] = this.adjacencyList[vertex1].filter(
         (v) => v !== vertex2
      );
      this.adjacencyList[vertex2] = this.adjacencyList[vertex2].filter(
         (v) => v !== vertex1
      );
   }
   removeVertex(vertex) {
      while (this.adjacencyList[vertex].length) {
         const adjacentVertex = this.adjacencyList[vertex].pop();
         this.removeEdge(vertex, adjacentVertex);
      }
      delete this.adjacencyList[vertex];
   }
   print() {
      for (const [vertex, edges] of Object.entries(this.adjacencyList)) {
         console.log(`${vertex} -> ${edges.join(", ")}`);
      }
   }
}
const graph = new Graph();
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
graph.addVertex("D");
graph.addEdge("A", "B");
graph.addEdge("A", "C");
graph.addEdge("B", "D");
graph.addEdge("C", "D");
console.log("Initial Graph:");
graph.print();
console.log("Graph after removal of edge AC:")
graph.removeEdge("A","C");
graph.print();

Ausgabe

Initial Graph:
A -> B, C
B -> A, D
C -> A, D
D -> B, C
Graph after removal of edge AC:
A -> B
B -> A, D
C -> D
D -> B, C

Graph-Traversal-Methode

Graph-Traversal bezieht sich auf den Prozess, alle Scheitelpunkte (oder Knoten) eines Diagramms zu besuchen und die damit verbundenen Informationen zu verarbeiten. Das Durchlaufen von Graphen ist eine wichtige Operation in Graphalgorithmen und wird für Aufgaben wie das Finden des kürzesten Pfades zwischen zwei Knoten, das Erkennen von Zyklen und das Auffinden verbundener Komponenten verwendet.

Es gibt zwei Hauptmethoden für die Graphdurchquerung: Breitensuche (Breadth First Search, BFS) und Tiefensuche (Depth First Search, DFS)

A. Breitensuche (BFS)

Es wird mit der Funktion widthFirstSearch() implementiert. Diese Funktion implementiert den Breitensuchalgorithmus und verwendet den Startparameter, den Startscheitelpunkt. Es verwendet eine Warteschlange, um die zu besuchenden Scheitelpunkte zu verfolgen, ein Ergebnisarray zum Speichern besuchter Scheitelpunkte und ein Besuchsobjekt, um bereits besuchte Scheitelpunkte zu verfolgen. Die Funktion fügt zunächst den Startscheitelpunkt zur Warteschlange hinzu und markiert ihn als besucht. Wenn die Warteschlange dann nicht leer ist, nimmt es den ersten Scheitelpunkt aus der Warteschlange, fügt ihn dem Ergebnisarray hinzu und markiert ihn als besucht. Anschließend werden alle nicht besuchten Nachbarn zur Warteschlange hinzugefügt. Dieser Vorgang wird fortgesetzt, bis alle Scheitelpunkte besucht wurden und das resultierende Array als Ergebnis des BFS zurückgegeben wird.

breadthFirstSearch(start) {
   const queue = [start];
   const result = [];
   const visited = {};
   let currentVertex;
   visited[start] = true;
   while (queue.length) {
      currentVertex = queue.shift();
      result.push(currentVertex);
         this.adjacencyList[currentVertex].forEach((neighbor) => {
            if (!visited[neighbor]) {
               visited[neighbor] = true;
               queue.push(neighbor);
            }
         });
      }
      return result;
   }
}

B. Tiefensuche

Die Tiefensuchmethode implementiert den DFS-Algorithmus mithilfe der rekursiven internen Funktion dfs, die Scheitelpunkte als Parameter verwendet. Die Funktion verwendet das besuchte Objekt, um die besuchten Scheitelpunkte zu verfolgen und fügt jeden besuchten Scheitelpunkt dem Ergebnisarray hinzu. Die Funktion markiert zunächst den aktuellen Scheitelpunkt als besucht und fügt ihn dem Ergebnisarray hinzu. Anschließend iteriert es über alle Nachbarn des aktuellen Scheitelpunkts und ruft rekursiv die dfs-Funktion für jeden nicht besuchten Nachbarn auf. Dieser Prozess wird fortgesetzt, bis alle Scheitelpunkte besucht wurden und das resultierende Array als Ergebnis von DFS zurückgegeben wird.

depthFirstSearch(start) {
   const result = [];
   const visited = {};
   const adjacencyList = this.adjacencyList;
   (function dfs(vertex) {
      if (!vertex) return null;
      visited[vertex] = true;
      result.push(vertex);
      adjacencyList[vertex].forEach(neighbor => {
         if (!visited[neighbor]) {
            return dfs(neighbor);
         }
      });
   })(start);
   return result;
}

Beispiel

Im folgenden Beispiel demonstrieren wir die Breitensuche (Breadth First Search, BFS) und die Tiefensuche (Depth First Search, DFS).

class Graph {
   constructor() {
      this.adjacencyList = {};
   }
   addVertex(vertex) {
      if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
   }
   addEdge(vertex1, vertex2) {
      this.adjacencyList[vertex1].push(vertex2);
      this.adjacencyList[vertex2].push(vertex1);
   }
   print() {
      for (const [vertex, edges] of Object.entries(this.adjacencyList)) {
         console.log(`${vertex} -> ${edges.join(", ")}`);
      }
   }
   breadthFirstSearch(start) {
      const queue = [start];
      const result = [];
      const visited = {};
      let currentVertex;
      visited[start] = true;
      while (queue.length) {
         currentVertex = queue.shift();
         result.push(currentVertex);
         this.adjacencyList[currentVertex].forEach((neighbor) => {
            if (!visited[neighbor]) {
               visited[neighbor] = true;
               queue.push(neighbor);
            }
         });
      }
      return result;
   }
   depthFirstSearch(start) {
      const result = [];
      const visited = {};
      const adjacencyList = this.adjacencyList;
      (function dfs(vertex) {
         if (!vertex) return null;
         visited[vertex] = true;
         result.push(vertex);
         adjacencyList[vertex].forEach(neighbor => {
            if (!visited[neighbor]) {
               return dfs(neighbor);
            }
         });
      })(start);
      return result;
   }
}
const graph = new Graph();
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
graph.addVertex("D");
graph.addEdge("A", "B");
graph.addEdge("A", "C");
graph.addEdge("B", "D");
graph.addEdge("C", "D");
console.log("Initial Graph:");
graph.print();
console.log("BFS: "+graph.breadthFirstSearch('A'));
console.log("DFS: "+graph.depthFirstSearch('A'));

Ausgabe

Initial Graph:
A -> B, C
B -> A, D
C -> A, D
D -> B, C
BFS: A,B,C,D
DFS: A,B,D,C

Fazit

Ein Diagramm ist eine nützliche Datenstruktur, die zur Darstellung von Beziehungen und Verbindungen zwischen Objekten verwendet werden kann. Die Implementierung von Diagrammen in JavaScript kann mithilfe verschiedener Techniken erfolgen, einschließlich der Verwendung von Adjazenzlisten oder Adjazenzmatrizen. Die in dieser Antwort demonstrierte Graph-Klasse verwendet eine Adjazenzlistendarstellung, bei der jeder Scheitelpunkt als Schlüssel in einem Objekt und seine entsprechende Kante als Wert dieses Schlüssels in einem Array gespeichert wird.

Die Graph-Klasse implementiert Methoden zum Hinzufügen von Scheitelpunkten und Kanten zu einem Diagramm, zum Drucken des Diagramms und zum Durchführen von Tiefensuche und Breitensuche.

Das obige ist der detaillierte Inhalt vonImplementierung von Diagrammen in JavaScript. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!