Structures de données et algorithmes : graphiques

Introduction

Un graphe est une structure de données avec un certain nombre de sommets (nœuds) et d'arêtes (connexions) entre eux.

Un arbre est un exemple de graphique. Chaque arbre est un graphique, mais tous les graphiques ne sont pas un arbre. Par exemple, les graphiques comportant des cycles ne sont pas des arbres. Un arbre aura une racine et un chemin unique entre deux nœuds tandis qu'un graphe peut avoir plusieurs racines et plusieurs chemins entre les sommets.

Terminologie de base

Vertex : Un nœud dans un graphe.

Edge : La connexion entre deux sommets.

Dirigé : Lorsque la connexion entre deux sommets a une direction. Cela implique qu’il n’y a qu’une seule façon de passer d’un sommet à un autre. Un exemple pourrait être un graphique montrant les villes (sommets) et les routes (bords) entre elles.

Non orienté : Lorsque la connexion entre deux sommets sur un graphe va dans les deux sens. Un exemple pourrait être un graphique montrant des personnes (sommets) liées par leurs amitiés.

Degré : Le nombre d'arêtes connectées à un sommet. Les sommets d'un graphe orienté peuvent avoir un degré entrant ou sortant, qui est le nombre d'arêtes pointant respectivement vers et loin du sommet.

Pondéré : Un graphique dans lequel les arêtes ont des valeurs comme poids. Un exemple pourrait être une feuille de route, où les distances entre les nœuds sont représentées sous forme de poids.

Cyclique : Un graphe qui a un chemin allant d'au moins un sommet à lui-même.

Acyclique : Un graphe qui n'a pas de cycles, c'est-à-dire qu'aucun nœud n'a de chemin vers lui-même. Un Graphique acyclique dirigé est un type de graphique qui peut être utilisé pour afficher les flux de traitement des données.

Dense : Lorsqu'un graphe a proche du nombre maximum possible d'arêtes

Sparse : Lorsqu'un graphe a un nombre proche du minimum possible d'arêtes.

Auto-boucle : Lorsqu'une arête a un sommet relié à lui-même.

Multi-arêtes : Lorsqu'un graphe a plusieurs arêtes entre deux sommets.

Simple :Quand un graphe n'a pas d'auto-boucles ni de multi-arêtes.

Pour obtenir le nombre maximum d'arêtes dans un graphe orienté simple : n*(n-1) où n est le nombre de nœuds.

Pour obtenir le nombre maximum d'arêtes dans un graphe simple non orienté : n*(n-1)/2 où n est le nombre de nœuds.

Implémentation de graphiques en JavaScript

Pour implémenter un graphe, nous pouvons commencer par spécifier les sommets et les arêtes d'un graphe, vous trouverez ci-dessous un exemple de la façon de procéder étant donné le graphe suivant :

const vertices = ["A", "B", "C", "D", "E"];

const edges = [
  ["A", "B"],
  ["A", "D"],
  ["B", "D"],
  ["B", "E"],
  ["C", "D"],
  ["D", "E"],
];

Ensuite on peut créer une fonction pour trouver ce qui est adjacent à un sommet donné :

const findAdjacentNodes = function (node) {
  const adjacentNodes = [];
  for (let edge of edges) {
    const nodeIndex = edge.indexOf(node);
    if (nodeIndex > -1) {
      let adjacentNode = nodeIndex === 0 ? edge[1] : edge[0];
      adjacentNodes.push(adjacentNode);
    }
  }
  return adjacentNodes;
};

Et une autre fonction pour vérifier si deux sommets sont connectés :

const isConnected = function (node1, node2) {
  const adjacentNodes = new Set(findAdjacentNodes(node1));
  return adjacentNodes.has(node2);
};

Liste de contiguïté

Une liste de contiguïté est une représentation d'un graphique où tous les sommets connectés à un nœud sont stockés sous forme de liste. Vous trouverez ci-dessous un graphique et une représentation visuelle de la liste de contiguïté correspondante.

Une liste de contiguïté peut être implémentée en JavaScript en créant deux classes, une classe Node et une classe Graph. La classe Node sera composée d'un constructeur et d'une méthode connect() pour joindre deux sommets. Il aura également les méthodes isConnected() et getAdjacentNodes() qui fonctionnent exactement de la même manière que celui indiqué ci-dessus.

class Node {
  constructor(value) {
    this.value = value;
    this.edgesList = [];
  }
  connect(node) {
    this.edgesList.push(node);
    node.edgesList.push(this);
  }
  getAdjNodes() {
    return this.edgesList.map((edge) => edge.value);
  }
  isConnected(node) {
    return this.edgesList.map((edge) => 
    edge.value).indexOf(node.value) > -1;
  }
}

La classe Graph se compose d'un constructeur et de la méthode addToGraph() qui ajoute un nouveau sommet au graphique.

class Graph {
  constructor(nodes) {
    this.nodes = [...nodes];
  }
  addToGraph(node) {
    this.nodes.push(node);
  }
}

Adjacency Matrix

A 2-D array where each array represents a vertex and each index represents a possible connection between vertices. An adjacency matrix is filled with 0s and 1s, with 1 representing a connection. The value at adjacencyMatrix[node1][node2] will show whether or not there is a connection between the two specified vertices. Below is is a graph and its visual representation as an adjacency matrix.

To implement this adjacency matrix in JavaScript, we start by creating two classes, the first being the Node class:

class Node {
  constructor(value) {
    this.value = value;
  }
}

We then create the Graph class which will contain the constructor for creating the 2-D array initialized with zeros.

class Graph {
  constructor(nodes) {
    this.nodes = [...nodes];
    this.adjacencyMatrix = Array.from({ length: nodes.length },   
    () => Array(nodes.length).fill(0));
   }
}

We will then add the addNode() method which will be used to add new vertices to the graph.

  addNode(node) {
    this.nodes.push(node);
    this.adjacencyMatrix.forEach((row) => row.push(0));
    this.adjacencyMatrix.push(new Array(this.nodes.length).fill(0));
  }

Next is the connect() method which will add an edge between two vertices.

  connect(node1, node2) {
    const index1 = this.nodes.indexOf(node1);
    const index2 = this.nodes.indexOf(node2);

    if (index1 > -1 && index2 > -1) {
      this.adjacencyMatrix[index1][index2] = 1;
      this.adjacencyMatrix[index2][index1] = 1; 
    }
  }

We will also create the isConnected() method which can be used to check if two vertices are connected.

  isConnected(node1, node2) {
    const index1 = this.nodes.indexOf(node1);
    const index2 = this.nodes.indexOf(node2);

    if (index1 > -1 && index2 > -1) {
      return this.adjacencyMatrix[index1][index2] === 1;
    }
    return false;
  }

Lastly we will add the printAdjacencyMatrix() method to the Graph class.

  printAdjacencyMatrix() {
    console.log(this.adjacencyMatrix);
  }

Breadth First Search

Similar to a Breadth First Search in a tree, the vertices adjacent to the current vertex are visited before visiting any subsequent children. A queue is the data structure of choice when performing a Breadth First Search on a graph.

Below is a graph of international airports and their connections and we will use a Breadth First Search to find the shortest route(path) between two airports(vertices).

In order to implement this search algorithm in JavaScript, we will use the same Node and Graph classes we implemented the adjacency list above. We will create a breadthFirstTraversal() method and add it to the Graph class in order to traverse between two given vertices. This method will have the visitedNodes object, which will be used to store the visited vertices and their predecessors. It is initiated as null to show that the first vertex in our search has no predecessors.

breathFirstTraversal(start, end) {
    const queue = [start];
    const visitedNodes = {};
    visitedNodes[start.value] = null;

    while (queue.length > 0) {
      const node = queue.shift();

      if (node.value === end.value) {
        return this.reconstructedPath(visitedNodes, end);
      }
      for (const adjacency of node.edgesList) {
        if (!visitedNodes.hasOwnProperty(adjacency.value)) {
          visitedNodes[adjacency.value] = node;
          queue.push(adjacency);
        }
      }
    }
  }

Once the end vertex is found, we will use the reconstructedPath() method in the Graph class in order to return the shortest path between two vertices. Each vertex is added iteratively to the shortestPath array, which in turn must be reversed in order to come up with the correct order for the shortest path.

reconstructedPath(visitedNodes, endNode) {
    let currNode = endNode;

    const shortestPath = [];

    while (currNode !== null) {
      shortestPath.push(currNode.value);
      currNode = visitedNodes[currNode.value];
    }
    return shortestPath.reverse();
  }

In the case of the graph of international airports, breathFirstTraversal(JHB, LOS) will return JHB -> LUA -> LOS as the shortest path. In the case of a weighted graph, we would use Dijkstra's algorithm to find the shortest path.

Depth First Search

Similar to a depth first search in a tree, this algorithm will fully explore every descendant of a vertex, before backtracking to the root. A stack is the data structure of choice for depth first traversals in a graph.

A depth first search can be used to detect a cycle in a graph. We will use the same graph of international airports to illustrate this in JavaScript.

Similar to the Breadth First Search algorithm above, this implementation of a Depth First Search algorithm in JavaScript will use the previously created Node and Graph classes. We will create a helper function called depthFirstTraversal() and add it to the Graph class.

  depthFirstTraversal(start, visitedNodes = {}, parent = null) {
    visitedNodes[start.value] = true;

    for (const adjacency of start.edgesList) {
      if (!visitedNodes[adjacency.value]) {
        if (this.depthFirstTraversal(adjacency, visitedNodes, start)) {
          return true;
        }
      } else if (adjacency !== parent) {
        return true;
      }
    }

    return false;
  }

This will perform the Depth First Traversal of the graph, using the parent parameter to keep track of the previous vertex and prevent the detection of a cycle when revisiting the parent vertex. Visited vertices will be marked as true in the visitedNodes object. This method will then use recursion to visit previously unvisited vertices. If the vertex has already been visited, we check it against the parent parameter. A cycle has been found if the vertex has already been visited and it is not the parent.

We will also create the wrapper function hasCycle() in the Graph class. This function is used to detect a cycle in a disconnected graph. It will initialize the visitedNodes object and loop through all of the vertices in the graph.

hasCycle() {
    const visitedNodes = {};

    for (const node of this.nodes) {
      if (!visitedNodes[node.value]) {
        if (this.depthFirstTraversal(node, visitedNodes)) {
          return true;
        }
      }
    }
    return false;
  }

In the case of the graph of international airports, the code will return true.

Depth First Traversal of a graph is also useful for pathfinding(not necessarily shortest path) and for solving mazes.

Abschluss

Ein fundiertes Verständnis von Graphen als Datenstruktur und den damit verbundenen Algorithmen ist unbedingt erforderlich, wenn man sein Studium von Datenstrukturen und Algorithmen vertieft. Obwohl dieser Leitfaden nicht so anfängerfreundlich ist wie die vorherigen Beiträge dieser Reihe, sollte er sich als nützlich erweisen, um Ihr Verständnis von Datenstrukturen und Algorithmen zu vertiefen.

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!