Implémentation de graphiques en JavaScript

Un graphe est une structure de données non linéaire qui représente un ensemble de sommets (également appelés nœuds) et les relations (ou arêtes) entre eux. Les sommets représentent des entités ou des objets, tandis que les edges représentent des relations ou des connexions entre les sommets. Les graphiques peuvent être utilisés pour modéliser de nombreux types de relations, tels que les réseaux sociaux, les systèmes de transport ou les flux d'informations.

Il existe deux principaux types de graphiques : les graphes orientés (également appelés graphes orientés) et les graphes non orientés. Dans un graphe orienté, les arêtes ont une direction et ne peuvent être parcourues que dans une seule direction, c'est-à-dire du sommet de départ au sommet de fin. Dans un graphe non orienté, les arêtes n’ont pas de direction et peuvent être parcourues dans les deux sens.

Implémentation d'images en JavaScript

Les graphiques peuvent être implémentés à l'aide de matrices de contiguïté ou de listes de contiguïté. Ici, nous allons implémenter des graphiques en JavaScript en utilisant des listes de contiguïté.

Créer une classe de graphiques

Ici, nous créons un plan de la classe graphique.

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

Ajouter des sommets

Cette fonction ajoute un nouveau sommet (ou nœud) au graphique en créant une nouvelle clé dans l'objet adjacencyList et en donnant un tableau vide comme valeur. Le nouveau sommet servira de clé et le tableau vide sera utilisé pour stocker ses voisins.

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

Ajouter des bords

Cette fonction ajoute une nouvelle arête entre deux sommets. Il accepte deux paramètres : sommet1 et sommet2, et ajoute le sommet2 au tableau des voisins du sommet1 et vice versa. Cela crée une connexion entre les deux sommets.

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

Imprimer le graphique

Cette fonction enregistre le graphique sur la console. Il parcourt chaque sommet de l'objet adjacencyList et enregistre le sommet et ses voisins.

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

Exemple

Dans l'exemple ci-dessous, nous définissons un graphique et ajoutons des sommets et des arêtes au graphique. Imprimez enfin le tableau.

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();

Sortie

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

Supprimer le bord

Cette fonction supprime le bord entre deux sommets. Il prend deux paramètres : vertex1 et vertex2, et filtre le vertex2 du tableau voisin de vertex1 et vice versa.

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

Supprimer des sommets

Cette fonction supprime un sommet du graphique. Il prend un argument de sommet et supprime d'abord toutes les arêtes connectées à ce sommet. Ensuite, il supprime la clé de l’objet adjacencyList.

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

Exemple

Dans l'exemple ci-dessous, nous définissons un graphique et ajoutons des sommets et des arêtes, puis imprimons le graphique. Nous supprimons une arête AC du graphique et imprimons enfin le graphique résultant.

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();

Sortie

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

Méthode de parcours graphique

Le parcours de graphique fait référence au processus de visite de tous les sommets (ou nœuds) d'un graphique et de traitement des informations qui leur sont associées. Le parcours graphique est une opération importante dans les algorithmes graphiques et est utilisé pour des tâches telles que la recherche du chemin le plus court entre deux nœuds, la détection de cycles et la recherche de composants connectés.

Il existe deux méthodes principales pour le parcours graphique : la recherche en largeur d'abord (BFS) et la recherche en profondeur en premier (DFS)

A. Recherche en largeur d'abord (BFS)

Il est implémenté à l'aide de la fonction widthFirstSearch(). Cette fonction implémente l'algorithme de recherche en largeur d'abord et prend le paramètre de départ, qui est le sommet de départ. Il utilise une file d'attente pour garder une trace des sommets à visiter, un tableau de résultats pour stocker les sommets visités et un objet de visite pour garder une trace des sommets déjà visités. La fonction ajoute d'abord le sommet de départ à la file d'attente et le marque comme visité. Ensuite, lorsque la file d'attente n'est pas vide, il prend le premier sommet de la file d'attente, l'ajoute au tableau de résultats et le marque comme visité. Il ajoute ensuite tous les voisins non visités à la file d'attente. Ce processus se poursuit jusqu'à ce que tous les sommets aient été visités et que le tableau résultant soit renvoyé comme résultat du BFS.

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. Recherche en profondeur d'abord

La méthode de recherche en profondeur d'abord implémente l'algorithme DFS en utilisant la fonction interne récursive dfs qui prend les sommets comme paramètres. La fonction utilise l'objet visité pour garder une trace des sommets visités et ajoute chaque sommet visité au tableau de résultats. La fonction marque d'abord le sommet actuel comme visité et l'ajoute au tableau de résultats. Il parcourt ensuite tous les voisins du sommet actuel et appelle récursivement la fonction dfs pour chaque voisin non visité. Ce processus se poursuit jusqu'à ce que tous les sommets aient été visités et que le tableau résultant soit renvoyé comme résultat de DFS.

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;
}

Exemple

Dans l'exemple ci-dessous, nous démontrons la recherche en largeur d'abord (BFS) et la recherche en profondeur en premier (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'));

Sortie

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

Conclusion

Un graphique est une structure de données utile qui peut être utilisée pour représenter les relations et les connexions entre des objets. L'implémentation de graphiques en JavaScript peut être effectuée à l'aide de diverses techniques, notamment l'utilisation de listes de contiguïté ou de matrices de contiguïté. La classe Graph présentée dans cette réponse utilise une représentation de liste de contiguïté, où chaque sommet est stocké en tant que clé dans un objet et son arête correspondante est stockée en tant que valeur de cette clé dans un tableau.

La classe Graph implémente des méthodes pour ajouter des sommets et des arêtes à un graphique, imprimer le graphique et effectuer des traversées de recherche en profondeur et en largeur.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!