Structures de données et algorithmes JavaScript Graphiques et algorithmes de graphiques_Connaissances de base

Définition du graphique

Le graphe est composé d'un ensemble fini non vide de sommets et d'un ensemble d'arêtes entre les sommets. Il est généralement exprimé comme suit : G(V,E), où G représente un graphe et V est le sommet du graphe G. . Ensemble, E est l’ensemble des arêtes du graphe G.

Graphique orienté

Arête dirigée : Si l'arête allant du sommet Vi à Vj a une direction, alors cette arête est appelée une arête dirigée, également appelée arc (Arc), représentée par une paire ordonnée , Vi est appelé est la queue de l’arc et Vj est appelé la tête de l’arc.

Graphique non ordonné

Arête non orientée : Si l'arête entre les sommets Vi et Vj n'a pas de direction, cette arête est appelée arête non orientée (Edge) et est représentée par une paire non ordonnée (Vi, Vj).

Image simple

Graphique simple : dans la structure du graphe, s'il n'y a pas d'arête allant d'un sommet à lui-même et que la même arête n'apparaît pas à plusieurs reprises, alors un tel graphe est appelé un graphe simple.

Graphiques

représente le sommet

La première étape de la création d'une classe graphique consiste à créer une classe Vertex pour enregistrer les sommets et les arêtes. La fonction de cette classe est la même que celle de la classe Node de liste chaînée et d'arbre de recherche binaire. La classe Vertex comporte deux données membres : une qui identifie le sommet et une valeur booléenne qui indique s'il a été visité. Ils sont nommés respectivement label et wasVisited.

Copier le code Le code est le suivant :

fonction Sommet(étiquette){
This.label = label;
>

Nous sauvegardons tous les sommets dans un tableau, et dans la classe graph, ils peuvent être référencés par leur position dans le tableau

représente un avantage

Les informations réelles du graphique sont stockées sur les "bords" car ils 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 graphe est beaucoup plus flexible. Un sommet peut avoir une ou plusieurs arêtes qui lui sont connectées.

Nous appelons la méthode de représentation des bords d'un graphique une liste de contiguïté ou un tableau de listes de contiguïté. Il stockera un tableau composé d'une liste de sommets adjacents d'un sommet

Schéma de construction

Définissez une classe Graph comme suit :

Copier le code Le code est le suivant :

fonction Graphique(v){
This.vertices = v;//point le plus élevé des sommets
This.edges = 0;
This.adj = [];
pour(var je =0;Je This.adj[i] = [];
This.adj[i].push('');
>
This.addEdge = addEdge;
This.toString = toString;
>

Cette classe enregistre le nombre d'arêtes qu'un graphique représente et enregistre le nombre de sommets en utilisant une longueur et le nombre de sommets dans le graphique.

Copier le code Le code est le suivant :

fonction addEdge(){
This.adj[v].push(w);
This.adj[w].push(v);
Ceci.bords ;
>

Ici, nous utilisons une boucle for pour ajouter un sous-tableau à chaque élément du tableau afin de stocker tous les sommets adjacents et initialiser tous les éléments avec des chaînes vides.

Parcours du graphique

Traversée en profondeur d'abord

DepthFirstSearch, également connu sous le nom de recherche en profondeur d'abord, appelée DFS.

Par exemple, si vous recherchez une clé dans une chambre, vous pouvez partir de n'importe quelle pièce pour rechercher un par un les coins, les tables de chevet, les lits, les armoires, les meubles TV, etc. , pour n'en manquer aucun. Impasse, après avoir fouillé tous les tiroirs et armoires de rangement, cherchez ensuite la pièce suivante.

Première recherche en profondeur :

La recherche en profondeur consiste à visiter un sommet non visité, à le marquer comme visité, puis à accéder de manière récursive à d'autres sommets non visités dans la liste de contiguïté du sommet initial

Ajouter un tableau à la classe Graph :

Copier le code Le code est le suivant :

this.marked = [];//Enregistrer les sommets visités
pour(var i=0;i This.marked[i] = false;//Initialisé à false
>

Fonction de recherche en profondeur :

Copier le code Le code est le suivant :

fonction dfs(v){
This.marked[v] = true;
//L'instruction if n'est pas nécessaire ici
Si(this.adj[v] != non défini){
​​​​print("Sommet visité : " v );
pour chacun(var w dans this.adj[v]){
Si(!this.marked[w]){
This.dfs(w);
            }
>
>
>

Recherche en largeur d'abord

La recherche en largeur d'abord (BFS) est une méthode de recherche aveugle qui vise à développer et à examiner systématiquement tous les nœuds du graphique pour trouver des résultats. En d’autres termes, il ne prend pas en compte les emplacements possibles des résultats et effectue une recherche approfondie sur l’ensemble du graphique jusqu’à ce que les résultats soient trouvés.

La recherche en largeur commence à partir du premier sommet et tente de visiter les sommets aussi proches que possible de celui-ci, comme indiqué ci-dessous :

Son principe de fonctionnement est le suivant :

1. Recherchez d'abord les sommets non visités adjacents au sommet actuel et ajoutez-les à la liste des sommets visités et à la file d'attente
; 2. Prenez ensuite le prochain sommet v du graphique et ajoutez-le à la liste des sommets visités
3. Enfin, ajoutez tous les sommets non visités adjacents à v à la file d'attente
Voici la définition de la fonction de recherche en largeur d'abord :

Copier le code Le code est le suivant :

fonction bfs(s){
var file d'attente = [];
This.marked = true;
Queue.push(s);//Ajouter à la fin de la file d'attente
Tandis que(queue.length>0){
          var v = queue.shift();//Supprimer de la tête de la file d'attente
Si(v == non défini){
                                      print("Sommet visité : " v);
>
pour chacun(var w dans this.adj[v]){
Si(!this.marked[w]){
This.edgeTo[w] = v;
This.marked[w] = true;
queue.push(w);
            }
>
>
>

Chemin le plus court

Lors d'une recherche en 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, vous devez modifier l'algorithme de recherche en largeur pour enregistrer le chemin d'un sommet à un autre sommet. Nous avons besoin d'un tableau pour enregistrer toutes les arêtes d'un sommet au sommet suivant. tableau edgeTo

Copier le code Le code est le suivant :

this.edgeTo = [];//Ajouter cette ligne à la classe Graph

//fonction bfs
fonction bfs(s){
var file d'attente = [];
This.marked = true;
Queue.push(s);//Ajouter à la fin de la file d'attente
Tandis que(queue.length>0){
          var v = queue.shift();//Supprimer de la tête de la file d'attente
Si(v == non défini){
                                      print("Sommet visité : " v);
>
pour chacun(var w dans this.adj[v]){
Si(!this.marked[w]){
This.edgeTo[w] = v;
This.marked[w] = true;
queue.push(w);
            }
>
>
>

Algorithme de tri topologique

Le tri topologique triera tous les sommets du graphe orienté de sorte que les arêtes dirigées pointent des sommets précédents vers les sommets ultérieurs.
L'algorithme de tri topologique est similaire à BFS. La différence est que l'algorithme de tri topologique ne génère pas immédiatement les sommets visités, mais visite tous les sommets adjacents dans la liste de contiguïté du sommet actuel. Le sommet actuel ne sera inséré que lorsque. la liste est épuisée dans la pile.

L'algorithme de tri topologique est divisé en deux fonctions. La première fonction est topSort(), qui est utilisée pour configurer le processus de tri et appeler une fonction auxiliaire topSortHelper(), puis afficher la liste de sommets triés

Le travail principal de l'algorithme de tri topologique est effectué dans la fonction récursive topSortHelper(). Cette fonction marquera le sommet actuel comme visité, puis accédera de manière récursive à chaque sommet de la liste de contiguïté des sommets actuelle pour marquer ces sommets comme visités. Enfin, le sommet actuel est poussé sur la pile.

Copier le code Le code est le suivant :

//Fonction topSort()
fonction topSort(){
var pile = [];
var visité = [];
pour(var je =0;i         visité[i] = false;
>
pour(var je = 0;i Si(visité[i] == faux){
This.topSortHelper(i,visited,stack);
>
>
pour(var i = 0;i Si(stack[i] !=undéfini && stack[i] != false){
                   print(this.vertexList[stack[i]]);
>
>
>

//fonction topSortHelper()
fonction topSortHelper(v,visité,pile){
visité[v] = vrai;
pour chacun(var w dans this.adj[v]){
Si(!visité[w]){
This.topSortHelper(visité[w],visité,pile);
>
>
​ stack.push(v);
>