Definition des Diagramms
Der Graph besteht aus einer endlichen, nicht leeren Menge von Scheitelpunkten und einer Menge von Kanten zwischen den Scheitelpunkten. Er wird normalerweise ausgedrückt als: G(V,E), wobei G einen Graphen darstellt und V der Scheitelpunkt des Graphen G ist . Menge, E ist die Menge der Kanten im Graphen G.
Gerichteter Graph
Gerichtete Kante: Wenn die Kante vom Scheitelpunkt Vi nach Vj eine Richtung hat, wird diese Kante als gerichtete Kante oder auch als Bogen (Arc) bezeichnet und durch ein geordnetes Paar dargestellt, das als Vi bezeichnet wird ist der Bogenschwanz und Vj wird der Bogenkopf genannt.
Ungeordneter Graph
Ungerichtete Kante: Wenn die Kante zwischen den Eckpunkten 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: Wenn in der Diagrammstruktur keine Kante von einem Scheitelpunkt zu sich selbst vorhanden ist und dieselbe Kante nicht wiederholt erscheint, wird ein solches Diagramm als einfaches Diagramm bezeichnet.
Grafiken
stellt den Scheitelpunkt
dar
Der erste Schritt beim Erstellen einer Diagrammklasse besteht darin, eine Vertex-Klasse zu erstellen, um Scheitelpunkte und Kanten zu speichern. Die Funktion dieser Klasse ist dieselbe wie die der Knotenklasse der verknüpften Liste und des binären Suchbaums. Die Vertex-Klasse verfügt über zwei Datenelemente: eines, das den Vertex identifiziert, und einen booleschen Wert, der angibt, ob er besucht wurde. Sie heißen label bzw. wasVisited.
Funktion Vertex(label){
This.label = label;
}
Wir speichern alle Scheitelpunkte in einem Array und in der Graph-Klasse können sie anhand ihrer Position im Array referenziert werden
stellt eine Kante dar
Die eigentlichen Informationen des Diagramms werden an den „Kanten“ gespeichert, da sie die Struktur des Diagramms beschreiben. Ein übergeordneter Knoten eines Binärbaums kann nur zwei untergeordnete Knoten haben, aber die Struktur des Diagramms ist viel flexibler. Mit einem Scheitelpunkt können eine Kante oder mehrere Kanten verbunden sein.
Wir nennen die Methode zur Darstellung der Kanten eines Diagramms eine Adjazenzliste oder ein Adjazenzlisten-Array. Es wird ein Array gespeichert, das aus einer Liste benachbarter Scheitelpunkte eines Scheitelpunkts besteht
Konstruktionsdiagramm
Definieren Sie eine Graph-Klasse wie folgt:
Funktion Graph(v){
This.vertices = v;//höchster Punkt der Vertices
This.edges = 0;
This.adj = [];
for(var i =0;I
This.adj[i] = [];
This.adj[i].push('');
}
This.addEdge = addEdge;
This.toString = toString;
}
Diese Klasse zeichnet auf, wie viele Kanten ein Diagramm darstellt, und zeichnet die Anzahl der Scheitelpunkte mithilfe einer Länge und der Anzahl der Scheitelpunkte im Diagramm auf.
Funktion addEdge(){
This.adj[v].push(w);
This.adj[w].push(v);
This.edges ;
}
Hier verwenden wir eine for-Schleife, um jedem Element im Array ein Unterarray hinzuzufügen, um alle angrenzenden Scheitelpunkte zu speichern, und alle Elemente mit leeren Zeichenfolgen zu initialisieren.
Diagrammdurchlauf
Tiefendurchquerung
DepthFirstSearch, auch Tiefensuche genannt, wird als DFS bezeichnet.
Wenn Sie beispielsweise nach einem Schlüssel in einem Zimmer suchen, können Sie von jedem Raum aus nacheinander die Ecken, Nachttische, Betten, Unterbetten, Kleiderschränke, Fernsehschränke usw. durchsuchen , um keine Sackgasse zu verpassen, suchen Sie nach dem Durchsuchen aller Schubladen und Lagerschränke nach dem nächsten Raum.
Tiefensuche:
Die Tiefensuche besteht darin, einen nicht besuchten Scheitelpunkt zu besuchen, ihn als besucht zu markieren und dann rekursiv auf andere nicht besuchte Scheitelpunkte in der Adjazenzliste des ursprünglichen Scheitelpunkts zuzugreifen
Fügen Sie ein Array zur Graph-Klasse hinzu:
this.marked = [];//Speichern Sie die besuchten Scheitelpunkte
for(var i=0;i
This.marked[i] = false;//Initialisiert auf false
}
Tiefensuchfunktion:
Funktion dfs(v){
This.marked[v] = true;
//Die if-Anweisung ist hier nicht erforderlich
If(this.adj[v] != undefiniert){
print("Besuchter Scheitelpunkt: " v );
for every(var w in this.adj[v]){
If(!this.marked[w]){
This.dfs(w);
}
}
}
}
Breitensuche
Die Breitensuche (BFS) ist eine blinde Suchmethode, die darauf abzielt, alle Knoten im Diagramm systematisch zu erweitern und zu untersuchen, um Ergebnisse zu finden. Mit anderen Worten: Es berücksichtigt nicht die möglichen Positionen der Ergebnisse und durchsucht das gesamte Diagramm gründlich, bis die Ergebnisse gefunden werden.
Die Breitensuche beginnt am ersten Scheitelpunkt und versucht, Scheitelpunkte so nah wie möglich daran zu finden, wie unten gezeigt:
Sein Funktionsprinzip ist:
1. Suchen Sie zunächst die nicht besuchten Scheitelpunkte neben dem aktuellen Scheitelpunkt und fügen Sie sie der Liste und Warteschlange der besuchten Scheitelpunkte hinzu
2. Nehmen Sie dann den nächsten Scheitelpunkt v aus dem Diagramm und fügen Sie ihn der Liste der besuchten Scheitelpunkte
hinzu
3. Fügen Sie schließlich alle nicht besuchten Scheitelpunkte neben v zur Warteschlange hinzu
Im Folgenden finden Sie die Definition der Breitensuchfunktion:
Funktion bfs(s){
var queue = [];
This.marked = true;
Queue.push(s);//Am Ende der Warteschlange hinzufügen
While(queue.length>0){
var v = queue.shift();//Vom Kopf der Warteschlange entfernen
If(v == undefiniert){
print("Visited vertex: " v);
}
for every(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 Breitensuche wird automatisch der kürzeste Weg von einem Scheitelpunkt zu einem anderen verbundenen Scheitelpunkt gefunden
Bestimmen Sie den Weg
Um den kürzesten Pfad zu finden, müssen Sie den Breitensuchalgorithmus ändern, um den Pfad von einem Scheitelpunkt zum anderen aufzuzeichnen. Wir benötigen ein Array, um alle Kanten von einem Scheitelpunkt zum nächsten zu speichern Array-EdgeTo
Code kopieren Der Code lautet wie folgt:
this.edgeTo = [];//Füge diese Zeile zur Graph-Klasse hinzu
//bfs-Funktion
Funktion bfs(s){
var queue = [];
This.marked = true;
Queue.push(s);//Am Ende der Warteschlange hinzufügen
While(queue.length>0){
var v = queue.shift();//Vom Kopf der Warteschlange entfernen
If(v == undefiniert){
print("Visited vertex: " v);
}
for every(var w in this.adj[v]){
If(!this.marked[w]){
This.edgeTo[w] = v;
This.marked[w] = true;
queue.push(w);
}
}
}
}
Topologischer Sortieralgorithmus
Topologische Sortierung sortiert alle Scheitelpunkte des gerichteten Graphen so, dass die gerichteten Kanten von den vorherigen Scheitelpunkten zu den späteren Scheitelpunkten zeigen.
Der topologische Sortieralgorithmus ähnelt BFS. Der Unterschied besteht darin, dass der topologische Sortieralgorithmus die besuchten Scheitelpunkte nicht sofort ausgibt. Stattdessen werden alle benachbarten Scheitelpunkte in der Adjazenzliste des aktuellen Scheitelpunkts aufgerufen Die Liste ist im Stapel erschöpft.
Der topologische Sortieralgorithmus ist in zwei Funktionen unterteilt: topSort(), mit der der Sortiervorgang eingerichtet und eine Hilfsfunktion topSortHelper() aufgerufen und dann die sortierte Scheitelpunktliste angezeigt wird
Die Hauptarbeit des topologischen Sortieralgorithmus wird in der rekursiven Funktion topSortHelper() abgeschlossen. Diese Funktion markiert den aktuellen Scheitelpunkt als besucht und greift dann rekursiv auf jeden Scheitelpunkt in der aktuellen Scheitelpunkt-Nachbarschaftsliste zu, um diese Scheitelpunkte als besucht zu markieren. Abschließend wird der aktuelle Scheitelpunkt auf den Stapel verschoben.
//topSort()-Funktion
Funktion topSort(){
var stack = [];
var besuchte = [];
for(var i =0;i
besuchte[i] = false;
}
for(var i = 0;i
If(visited[i] == false){
This.topSortHelper(i,visited,stack);
}
}
for(var i = 0;i
If(stack[i] !=undefiniert && stack[i] != false){
print(this.vertexList[stack[i]]);
}
}
}
//topSortHelper()-Funktion
Funktion topSortHelper(v,visited,stack){
besuchte[v] = true;
for every(var w in this.adj[v]){
If(!visited[w]){
This.topSortHelper(visited[w],visited,stack);
}
}
stack.push(v);
}
