Construcción de Grafos: Método Lista de Adyacencia en JavaScript

¿Cómo crear un grafo en JavaScript utilizando listas de adyacencia?

Comenzar con la lógica básica de un grafo puede parecer intimidante, pero con un enfoque claro y una guía paso a paso, podrás dominarlo en poco tiempo. En esta sesión, exploraremos cómo representar un grafo no dirigido en JavaScript utilizando listas de adyacencia. Te mostraré cómo puedes construir un grafo desde cero y cómo añadirle nodos y bordes. ¡Vamos a sumergirnos!

¿Cómo se estructura la clase de grafo?

El primer paso para crear nuestro grafo es estructurar una clase que nos permita manipular nodos y sus conexiones. A continuación, definiremos la clase Grafo y su constructor para manejar los nodos de manera adecuada.

class Grafo {
    constructor() {
        this.nodos = 0;
        this.adjList = {};
    }
}

¿Cómo agregar nodos (vértices) al grafo?

Agregar nodos es una tarea esencial para la creación de un grafo. Observa cómo el método agregarNodo toma un valor y lo incorpora al grafo mediante un array vacío, indicando que aún no tiene conexiones.

agregarNodo(nodo) {
    this.adjList[nodo] = [];
    this.nodos++;
}

¿Cómo representamos las conexiones entre nodos?

Los bordes del grafo representan las conexiones entre nodos. Utilizaremos un método sencillo para gestionar estas conexiones en ambas direcciones, ya que nuestro ejemplo es un grafo no dirigido.

agregarBorde(nodo1, nodo2) {
    this.adjList[nodo1].push(nodo2);
    this.adjList[nodo2].push(nodo1);
}

¿Cómo implementamos y validamos el grafo?

Con los métodos en su lugar, es hora de implementar y validar el grafo. Aquí te muestro el código para crear nodos y sus conexiones:

let miGrafo = new Grafo();

miGrafo.agregarNodo(1);
miGrafo.agregarNodo(3);
miGrafo.agregarNodo(4);
miGrafo.agregarNodo(5);
miGrafo.agregarNodo(6);
miGrafo.agregarNodo(8);

miGrafo.agregarBorde(1, 3);
miGrafo.agregarBorde(1, 5);
miGrafo.agregarBorde(3, 6);
miGrafo.agregarBorde(1, 4);
miGrafo.agregarBorde(4, 5);
miGrafo.agregarBorde(8, 4);

¿Cómo verificamos la estructura del grafo?

Vamos a verificar si nuestro grafo está estructurado correctamente al revisar la lista de adyacencia generada:

console.log(miGrafo.adjList);

¿Qué sigue?

¡Felicidades por construir tu primer grafo! Ahora que dominas la estructura básica, te recomiendo experimentar con variaciones:

• Crea un grafo dirigido.
• Implementa grafos ponderados agregando pesos a los bordes.
• Intenta con otras representaciones como matrices de adyacencia.

Trabajar en distintos tipos de grafos no solo fortalecerá tus habilidades de programación, sino que también mejorará tu lógica para resolver problemas complejos. ¡Continúa practicando y explorando las fascinantes posibilidades de los grafos!