Definition des Diagramms
Graph besteht aus einem endlichen nicht leeren Eckpunkt und einer Reihe von Kanten zwischen Scheitelpunkten. Es wird normalerweise als: g (v, e) dargestellt, wobei G ein Diagramm darstellt, v der Satz von Scheitelpunkten in Graph G und e der Satz von Kanten in Graph G.
Regie Graph
Gerichtete Kante: Wenn die Kante vom Scheitelpunkt VI bis VJ eine Richtung hat, wird diese Kante als gerichtete Kante bezeichnet, die ebenfalls zum Bogen (ARC) wird. Es wird durch eine geordnete <vi, vj> dargestellt. VI wird als Bogenschwanz bezeichnet und VJ wird als Bogenkopf bezeichnet.
Ungeordnetes Diagramm
Unerregende Kante: Wenn die Kante zwischen Scheitelpunkten VI und VJ keine Richtung hat, wird diese Kante als ungerichtete Kante (Kante) bezeichnet und durch ein ungeordnetes Paar (VI, VJ) dargestellt.
Einfaches Bild
Einfaches Diagramm: In der Graphenstruktur wird dieses Bild als einfaches Diagramm bezeichnet.
Bildklasse
Zeigt einen Scheitelpunkt an
Der erste Schritt beim Erstellen einer Grafikklasse besteht darin, eine Scheitelpunktklasse zum Speichern von Scheitelpunkten und Kanten zu erstellen. Diese Klasse fungiert genauso wie die Knotenklasse verknüpfter Listen und binärer Suchbäume. Die Scheitelpunktklasse hat zwei Datenmitglieder: einen, um den Scheitelpunkt und den anderen zu identifizieren, um anzugeben, ob er zugegriffen wurde. Sie werden als Label bezeichnet und wurden jeweils besucht.
Die Codekopie lautet wie folgt:
Funktion Scheitelpunkt (Label) {
this.label = label;
}
Wir speichern alle Scheitelpunkte in einem Array und in der Grafikklasse können wir sie durch ihre Position im Array auf sie verweisen
Zeigt die Kante an
Die tatsächlichen Informationen des Diagramms werden am "Rand" gespeichert, da sie die Struktur des Diagramms beschreiben. Ein übergeordneter Knoten eines binären Baums kann nur zwei untergeordnete Knoten haben, aber die Struktur des Diagramms ist viel flexibler. Ein Scheitelpunkt kann eine Kante oder mehrere Kanten mit ihm angeschlossen haben.
Wir werden die Methode zur Darstellung von Kanten des Diagramms verwenden, um eine Adjazenztabelle oder ein Adjazenztabellen -Array zu werden. Es wird ein Array gespeichert, das aus einer Liste benachbarter Scheitelpunkte von Scheitelpunkten besteht
Erstellen Sie eine Grafik
Definieren Sie die folgende Grafikklasse:
Die Codekopie lautet wie folgt:
Funktionsgrafik (v) {
this.vertices = v; // Scheitelpunkte bis zum Höhepunkt
this.edges = 0;
this.adj = [];
für (var i = 0; i <this.vertices; ++ i) {
this.adj [i] = [];
this.adj [i] .push ('');
}
this.adDedge = addiert;
this.toString = toString;
}
In dieser Klasse wird aufgezeichnet, wie viele Kanten ein Diagramm repräsentiert und eine Länge und die Anzahl der Scheitelpunkte des Diagramms verwendet, um die Anzahl der Scheitelpunkte aufzuzeichnen.
Die Codekopie lautet wie folgt:
Funktion addledge () {
this.adj [v] .push (w);
this.adj [w] .push (v);
this.edges ++;
}
Hier verwenden wir eine für die Schleife, um für jedes Element im Array ein Subtarray hinzuzufügen, um alle benachbarten Scheitelpunkte zu speichern und alle Elemente in leere Zeichenfolgen zu initialisieren.
Der Traversal des Bildes
Tiefe Priorität Traversal
TiefefirstSearch, auch als Tiefenforschung bezeichnet, wird kurz als DFS bezeichnet.
Auf der Suche nach einem Schlüssel in einem Raum, egal in welchem Raum Sie beginnen, können Sie nach den Ecken des Raumes, dem Nachttisch, Nachttischen, unter Betten, Kleiderschränken, Fernsehschränken usw. nacheinander suchen, um keine blinden Stellen zu verpassen. Nachdem Sie alle Schubladen und Lagerschränke gesucht und dann nach dem nächsten Raum gesucht haben.
Tiefenprioritätssuche:
Tiefe-First-Suche bedeutet, auf einen Scheitelpunkt zuzugreifen, der nicht besucht wurde, ihn als Zugriff markiert und dann rekursiv auf andere Scheitelpunkte zugreift, die in der Adjazenztabelle des anfänglichen Scheitelpunkts nicht besucht wurden.
Fügen Sie der Grafikklasse ein Array hinzu:
Die Codekopie lautet wie folgt:
this.marked = []; // Speichern Sie die besuchten Eckpunkte
für (var i = 0; i <this.vertices; ++ i) {
this.marked [i] = false; // initialisieren auf false
}
Tiefe-First-Suchfunktion:
Die Codekopie lautet wie folgt:
Funktion DFS (v) {
this.marked [v] = true;
// Wenn hier keine Aussage erforderlich ist
if (this.adj [v]! = undefiniert) {
print ("besucht vertex:" + v);
für jedes (var w in this.adj [v]) {
if (! this.marked [w]) {
this.dfs (w);
}
}
}
}
Breite-First-Suche
BREIDNESS-FRIRST SUCHE (BFS) ist eine Blindsuchmethode mit dem Zweck, alle Knoten im Diagramm systematisch zu erweitern und zu untersuchen, um Ergebnisse zu finden. Mit anderen Worten, es berücksichtigt den möglichen Ort des Ergebniss nicht und sucht das gesamte Bild gründlich, bis das Ergebnis gefunden wurde.
Die Breit-First-Suche beginnt mit dem ersten Scheitelpunkt und versuchen Sie, den Scheitelpunkt so nah wie möglich an ihn zuzugreifen, wie in der folgenden Abbildung gezeigt:
Sein Arbeitsprinzip ist:
1. Finden Sie zuerst ungerückte Scheitelpunkte neben dem aktuellen Scheitelpunkt und fügen Sie sie der besuchten Scheitelpunkte und der Warteschlange hinzu.
2. Nehmen Sie dann den nächsten Scheitelpunkt V aus dem Diagramm heraus und fügen Sie es der besuchten Vertice -Liste hinzu
3. Fügen Sie schließlich alle nicht besuchten Eckpunkte neben V zur Warteschlange hinzu
Das Folgende ist die Definition der Suchfunktion der Breite zuerst:
Die Codekopie lautet wie folgt:
Funktion BFS (s) {
var queue = [];
this.marked = true;
queue.push (s); // add am Ende der Warteschlange hinzufügen
while (queue.length> 0) {
var v = queue.shift (); // Entfernen Sie aus dem Teamleiter
if (v == undefiniert) {
print ("besucht vertex:" + v);
}
für jedes (var w in this.adj [v]) {
if (! this.marked [w]) {
this.edgeto [w] = v;
this.marked [w] = true;
queue.push (w);
}
}
}
}
Kürzester Weg
Bei der Durchführung einer Breite-First-Suche wird automatisch der kürzeste Weg von einem Scheitelpunkt zu einem anderen angeschlossenen Scheitelpunkt gefunden
Bestimmen Sie den Pfad
Um den kürzesten Pfad zu finden, müssen wir den Suchalgorithmus mit Breite-First-Such ändern, um den Pfad von einem Scheitelpunkt zum anderen aufzuzeichnen. Wir brauchen ein Array, um alle Kanten des nächsten Scheitelpunkts von einem Scheitelpunkt zu speichern. Wir nennen diesen Array Edgeto
Die Codekopie lautet wie folgt:
this.edgeto = []; // Fügen Sie diese Zeile der Grafikklasse hinzu
// BFS -Funktion
Funktion BFS (s) {
var queue = [];
this.marked = true;
queue.push (s); // add am Ende der Warteschlange hinzufügen
while (queue.length> 0) {
var v = queue.shift (); // Entfernen Sie aus dem Teamleiter
if (v == undefiniert) {
print ("besucht vertex:" + v);
}
für jedes (var w in this.adj [v]) {
if (! this.marked [w]) {
this.edgeto [w] = v;
this.marked [w] = true;
queue.push (w);
}
}
}
}
Topologischer Sortieralgorithmus
Die topologische Sortierung sortiert alle Scheitelpunkte eines gerichteten Diagramms, so dass gerichtete Kanten vom vorderen Scheitelpunkt auf den hinteren Scheitelpunkt punkten.
Der topologische Sortieralgorithmus ähnelt BFS. Der Unterschied besteht darin, dass der topologische Sortieralgorithmus die Zugriffsscheitelpunkte nicht sofort ausgibt, sondern auf alle benachbarten Eckpunkte im aktuellen vertex benachbarten Tabelle zugreift. Bis diese Liste erschöpft ist, wird der aktuelle Scheitelpunkt nicht in den Stapel gedrückt.
Der topologische Sortieralgorithmus ist in zwei Funktionen aufgeteilt. Die erste Funktion ist topsort (), mit dem der Sortiervorgang festgelegt und eine Helferfunktion Topsorthelper () aufgerufen und dann die sortierte Vertex -Liste angezeigt wird.
Die Hauptarbeit des Topologie -Sortieralgorithmus erfolgt in der rekursiven Funktion Topsorthelper (), die den aktuellen Scheitelpunkt markiert, wie er zugegriffen wird, und dann rekursiv auf jeden Scheitelpunkt in der aktuellen Vertex -Adjazenz -Tabelle zugreift, wobei diese Scheitelpunkte wie zugegriffen markiert werden. Drücken Sie zum Schluss den aktuellen Scheitelpunkt in den Stapel.
Die Codekopie lautet wie folgt:
// topsort () Funktion
Funktion topsort () {
var stack = [];
var besucht = [];
für (var i = 0; i <this.vertices; i ++) {
besucht [i] = false;
}
für (var i = 0; i <this.vertices; i ++) {
if (besucht [i] == false) {
topsorthelper (ich, besuchte, stapel);
}
}
für (var i = 0; i <stack.length; i ++) {
if (stack [i]! = undefined && stack [i]! = false) {
print (this.vertexlist [stack [i]]);
}
}
}
// topsorthelper () Funktion
Funktion Topsorthelper (V, besucht, stapel) {
besucht [v] = true;
für jedes (var w in this.adj [v]) {
if (! besucht [w]) {
topsorthelper (besucht [w], besucht, stapel);
}
}
stack.push (v);
}