Définition du diagramme
Le graphique est composé d'un ensemble de sommets non vides finis et d'un ensemble de bords entre les sommets. Il est généralement représenté comme: g (v, e), où g représente un graphique, V est l'ensemble des sommets dans le graphique G, et E est l'ensemble des bords dans le graphique G.
Graphique dirigé
Edge dirigé: Si le bord du sommet VI à VJ a une direction, ce bord est appelé bord dirigé, qui devient également un arc (arc). Il est représenté par un <vi, vj> ordonné. VI est appelé la queue d'arc et VJ est appelé la tête d'arc.
Diagramme désordonné
Bord non dirigée: Si le bord entre les sommets VI à VJ n'a pas de direction, ce bord est appelé bord non dirigé (bord) et est représenté par une paire non ordonnée (VI, VJ).
Image simple
Diagramme simple: dans la structure du graphique, s'il n'y a pas de sommet à son propre bord et que le même bord n'apparaît pas à plusieurs reprises, cette image est appelée diagramme simple.
Classe d'images
Indique un sommet
La première étape de la création d'une classe de graphe consiste à créer une classe de sommet pour enregistrer les sommets et les bords. Cette classe fonctionne de la même manière que la classe de nœuds des listes liées et des arbres de recherche binaires. La classe Vertex a deux membres de données: l'une pour identifier le sommet et l'autre pour indiquer si elle a été accessible. Ils sont nommés étiquettes et ont été visités respectivement.
La copie de code est la suivante:
fonction de fonction (label) {
this.label = label;
}
Nous enregistrons tous les sommets dans un tableau, et dans la classe graphique, nous pouvons nous référer à eux par leur position dans le tableau
Indique le bord
Les informations réelles du graphique sont stockées sur le "bord" car elles décrivent la structure du graphique. Un nœud parent d'un arbre binaire ne peut avoir que deux nœuds enfants, mais la structure du graphique est beaucoup plus flexible. Un sommet peut avoir un bord ou plusieurs bords qui y sont connectés.
Nous utiliserons la méthode de représentation des bords du graphique pour devenir une table d'adjacence ou un tableau de table d'adjacence. Il stockera un tableau composé d'une liste de sommets adjacents de sommets
Construire un graphique
Définissez la classe graphique suivante:
La copie de code est la suivante:
graphique de fonction (v) {
this.vertices = v; // sommets au point culminant
this.edges = 0;
this.adj = [];
pour (var i = 0; i <this.vertices; ++ i) {
this.adj [i] = [];
this.adj [i] .push ('');
}
this.adDedge = Addge;
this.toString = toString;
}
Cette classe enregistre le nombre d'arêtes qu'un graphique représente et utilise une longueur et le nombre de sommets du graphique pour enregistrer le nombre de sommets.
La copie de code est la suivante:
fonction AddgeGe () {
this.adj [v] .push (w);
this.adj [w] .push (v);
this.edges ++;
}
Ici, nous utilisons une boucle pour ajouter un sous-réseau pour chaque élément du tableau afin de stocker tous les sommets adjacents et d'initialiser tous les éléments en chaînes vides.
La traversée de l'image
Priorité de profondeur Transfert
DepthFirstSearch, également connu sous le nom de DepthFirstSearch, est appelé DFS pour faire court.
Par exemple, à la recherche d'une clé dans une pièce, quelle que soit la pièce que vous commencez, vous pouvez rechercher les coins de la pièce, des tables de chevet, des tables de chevet, sous des lits, des armoires, des armoires télévisées, etc. une par une, afin de ne manquer aucun angle mort. Après avoir recherché tous les tiroirs et armoires de rangement, puis rechercher la pièce suivante.
Recherche de priorité en profondeur:
La recherche en profondeur d'abord signifie accéder à un sommet qui n'a pas été visité, le marquant comme accessible, puis accéder à d'autres sommets qui n'ont pas été visités dans le tableau d'adjacence du sommet initial.
Ajoutez un tableau à la classe Graph:
La copie de code est la suivante:
this.marked = []; // Enregistrer les sommets visités
pour (var i = 0; i <this.vertices; ++ i) {
this.marked [i] = false; // initialiser à false
}
Fonction de recherche en profondeur d'abord:
La copie de code est la suivante:
fonction dfs (v) {
this.marked [v] = true;
// Si la déclaration n'est pas nécessaire ici
if (this.adj [v]! = Undefined) {
print ("Vertex visité:" + v);
pour chaque (var w dans ce.adj [v]) {
if (! this.marked [w]) {
this.dfs (w);
}
}
}
}
Recherche de largeur
La recherche de largeur de large (BFS) est une méthode de recherche aveugle, dans le but de l'expansion systématique et de l'examen de tous les nœuds du graphique pour trouver des résultats. En d'autres termes, il ne prend pas en compte l'emplacement possible du résultat et recherche à fond l'image entière jusqu'à ce que le résultat soit trouvé.
La recherche de largeur d'abord commence par le premier sommet et essayez d'accéder au sommet le plus près possible, comme le montre la figure suivante:
Son principe de travail est:
1. Trouvez d'abord les sommets non atteints adjacents au sommet actuel et ajoutez-les à la liste et à la file d'attente des sommets visités;
2. Ensuite, retirez le sommet suivant V à partir du graphique et ajoutez-le à la liste Vertice visité
3. Enfin ajouter tous les sommets non visités adjacents à V à la file d'attente
Ce qui suit est la définition de la fonction de recherche de l'étendue:
La copie de code est la suivante:
fonction bfs (s) {
var queue = [];
this.marked = true;
queue.push (s); // ajouter à la fin de la file d'attente
while (queue.length> 0) {
var v = queue.shift (); // retirer du chef d'équipe
if (v == Undefined) {
print ("Vertex visité:" + v);
}
pour chaque (var w dans ce.adj [v]) {
if (! this.marked [w]) {
this.edgeto [w] = v;
this.Marked [w] = true;
queue.push (w);
}
}
}
}
Chemin le plus court
Lors de la recherche d'une largeur de largeur, le chemin le plus court d'un sommet à un autre sommet connecté est automatiquement trouvé
Déterminer le chemin
Pour trouver le chemin le plus court, nous devons modifier l'algorithme de recherche en largeur pour enregistrer le chemin d'un sommet à un autre. Nous avons besoin d'un tableau pour enregistrer tous les bords du sommet suivant d'un sommet. Nous nommons ce tableau Edgeto
La copie de code est la suivante:
this.edgeto = []; // ajouter cette ligne à la classe graphique
// Fonction BFS
fonction bfs (s) {
var queue = [];
this.marked = true;
queue.push (s); // ajouter à la fin de la file d'attente
while (queue.length> 0) {
var v = queue.shift (); // retirer du chef d'équipe
if (v == Undefined) {
print ("Vertex visité:" + v);
}
pour chaque (var w dans ce.adj [v]) {
if (! this.marked [w]) {
this.edgeto [w] = v;
this.Marked [w] = true;
queue.push (w);
}
}
}
}
Algorithme de tri topologique
Le tri topologique trie tous les sommets d'un graphique dirigé, de sorte que les bords dirigés pointent du sommet avant au sommet arrière.
L'algorithme de tri topologique est similaire à BFS. La différence est que l'algorithme de tri topologique ne sort pas immédiatement les sommets accessibles, mais accède plutôt à tous les sommets adjacents dans la table adjacente du sommet actuel. Jusqu'à ce que cette liste soit épuisée, le sommet actuel ne sera pas poussé dans la pile.
L'algorithme de tri topologique est divisé en deux fonctions. La première fonction est TopSort (), qui est utilisée pour définir le processus de tri et appeler une fonction d'assistance topsorthelper (), puis afficher la liste de sommets triée.
Le travail principal de l'algorithme de tri de topologie est effectué dans la fonction récursive Topsorthelper (), qui marque le sommet actuel comme accessible, puis accède à chaque sommet dans le tableau de contiguïté du sommet actuel, marquant ces sommets comme accessible. Enfin, poussez le sommet actuel dans la pile.
La copie de code est la suivante:
// fonction topsort ()
fonction topsort () {
var stack = [];
var visité = [];
for (var i = 0; i <this.vertices; i ++) {
visité [i] = false;
}
for (var i = 0; i <this.vertices; i ++) {
if (visité [i] == false) {
this.topsorthelper (i, visité, pile);
}
}
pour (var i = 0; i <stack.length; i ++) {
if (pile [i]! = undefined && pile [i]! = false) {
print (this.vertexlist [pile [i]]);
}
}
}
// fonction topsorthelper ()
fonction topsorthelper (v, visité, pile) {
visité [v] = true;
pour chaque (var w dans ce.adj [v]) {
if (! visité [w]) {
this.topsorthelper (visité [w], visité, pile);
}
}
stack.push (v);
}