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

Curso de Estructuras de Datos con JavaScript

Contenido del curso

Introducción a las estructuras de datos

Arrays y strings

Hash Table

Linked List

Stacks

Queues

Trees

20
Estructuras de Datos: Árboles Binarios y Búsqueda en JavaScript
06:15 min
21
Construcción y validación de un Árbol de Búsqueda Binaria en JavaScript
19:36 min

Graphs

Cierre

25
Estructuras de Datos con JavaScript: Práctica y Aplicación
03:14 min

Tomar examen

Cursos Empresas Blog Live Conf Eventos Precios

0:0015:35

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

Curso de Estructuras de Datos con JavaScript

Clase 24 de 25

Clase 24 / 25

Recursos

Construir un grafo no dirigido en JavaScript es más simple de lo que parece: con una representación tipo JSON List (objeto con arrays), un constructor claro y dos métodos (addVertex y addEdge), obtienes una estructura sólida para practicar lógica y conexiones entre datos. Aquí verás los pasos exactos, el código mínimo y cómo validar las relaciones entre nodos.

¿Cómo modelar un grafo no dirigido con adjacent list en JavaScript?

Un grafo se compone de vértices (nodos) y bordes (conexiones o edges). La clase inicia sin valor y usa un objeto para mapear cada nodo a un array con sus vecinos. Además, mantiene un contador de nodos para ubicar por índice.

¿Qué hace el constructor y cómo se representa con JSON List?

Crea la instancia del grafo sin valor inicial.
Define dis.nodos para el conteo de vértices.
Define dis.jsonList como objeto: cada clave es un nodo y su valor es un array de conexiones.

class Grafo {
  constructor() {
    this.nodos = 0;
    this.jsonList = {}; // representación tipo *JSON List*: objeto de arrays
  }

  addVertex(nodo) {
    this.jsonList[nodo] = []; // cada vértice inicia con un array vacío
    this.nodos++;
  }

  addEdge(n1, n2) {
    // grafo no dirigido: se agregan ambas conexiones con *push*
    this.jsonList[n1].push(n2);
    this.jsonList[n2].push(n1);
  }
}

¿Qué implica usar índices y arrays en la estructura?

Cada nodo es una clave del objeto: índice legible y directo.
Cada array lista a qué nodos conecta ese vértice.
Con push agregas vecinos sin duplicar estructura.

¿Cómo agregar vértices y bordes (edges) paso a paso?

Primero se crean los vértices; luego se conectan con bordes. La verificación final confirma que la adjacent list refleja exactamente las conexiones esperadas.

const g = new Grafo();

// 1) Agregar vértices (vértices: 1, 3, 4, 5, 6, 8)
[1, 3, 4, 5, 6, 8].forEach(v => g.addVertex(v));

// 2) Agregar bordes para un grafo no dirigido
// conexiones validadas posteriormente en la *adjacent list*
g.addEdge(1, 6);
g.addEdge(1, 3);
g.addEdge(1, 4);

g.addEdge(3, 5);
g.addEdge(3, 6);

g.addEdge(4, 5);
g.addEdge(4, 8);

console.log(g.jsonList);
/*
{
  1: [6, 3, 4],
  3: [5, 6, 1],
  4: [1, 5, 8],
  5: [3, 4],
  6: [3, 1],
  8: [4]
}
*/

¿Cómo validar la adjacent list final por índice?

1 conecta con 6, 3, 4.
3 conecta con 5, 6, 1.
4 conecta con 1, 5, 8.
5 conecta con 3, 4.
6 conecta con 3, 1.
8 conecta con 4.

En un grafo no dirigido, cada borde aparece en ambos sentidos: la lógica de addEdge asegura la simetría agregando con push en los dos arrays involucrados.

¿Qué habilidades y conceptos refuerzas con este ejercicio?

Este ejercicio potencia tu comprensión práctica de estructuras de datos y su implementación en código sencillo pero preciso. Se trabaja desde la instanciación de clases y el constructor, hasta la representación con índices y arrays.

¿Qué habilidades técnicas aplicas en JavaScript?

Diseño de una clase con estado interno: nodos y JSON List.
Modelado de grafos con objeto de arrays: representación tipo adjacent list.
Implementación de métodos: addVertex para crear vértices y addEdge para conectar nodos.
Mutación controlada de colecciones con push.
Verificación manual de conexiones por índice: lectura y comparación rápida.

¿Qué conceptos clave quedan claros?

Grafo no dirigido: cada conexión es bidireccional por definición de edge.
Vértices vs. bordes: primero agregas nodos, luego conectas relaciones.
Lógica incremental: construir, probar, validar y ajustar con pocas líneas.
Simplicidad efectiva: la claridad de la representación facilita depuración y expansión.

¿Te animas a probar una variante? puedes intentar un grafo dirigido o crear nuevas conexiones y comentar cómo cambió tu adjacent list. ¡Comparte tus resultados y dudas!

Ciro Villafraz

Hace 6 años

Hace ya un buen tiempo hice un curso de estructuras de datos en Python, y en unos de los ejercicios nos daban un grafo, en el cual nos pedían crear tres funciones las cuales retornaran un edge list, un adjacency list y un adjacency matrix. Me tomé el tiempo de pasar el código de Python a JS, aquí lo dejo

class Node{
    constructor(value){
        this.value = value
        this.edges = []
    }
}
        
class Edge{
    constructor(nodeFrom, nodeTo){
        this.nodeFrom = nodeFrom
        this.nodeTo = nodeTo
    }
}

class Graph{
    constructor(nodes = [], edges = []){
        this.nodes = nodes
        this.edges = edges
    }
    insertNode(value){
        this.nodes.push(new Node(value))
    }
    insertEdge(fromValue, toValue){
        let fromFound = null
        let toFound = null

        this.nodes.forEach(node=>{
            if(fromValue === node.value){
                fromFound = node
            }
            if(toValue === node.value){
                toFound = node
            }
        })

        if(!fromFound){
            fromFound = new Node(fromValue)
            this.nodes.push(fromFound)
        }
        if(!toFound){
            toFound = new Node(toValue)
            this.nodes.push(toFound)
        }
        const newEdge = new Edge(fromFound, toFound)
        fromFound.edges.push(newEdge)
        toFound.edges.push(newEdge)
        this.edges.push(newEdge)
    }
    getEdgeList(){
        const edgeList = []
        for(let edge of this.edges){
            edgeList.push([edge.nodeFrom.value, edge.nodeTo.value])
        }
        return edgeList
    }
    getAdjacencyList(){
        const maxIndex = this.edges.length
        // Create a list with maxIndex +1 elements, all null
        const adjacencyList = Array.from(new Array(maxIndex+1), x => null)

        for(let edge of this.edges){
            if(adjacencyList[edge.nodeFrom.value]){
                adjacencyList[edge.nodeFrom.value].push(edge.nodeTo.value)
            }
            else{
                adjacencyList[edge.nodeFrom.value] = [edge.nodeTo.value]
            }
        }
        return adjacencyList
    }
    getAdjacencyMatrix(){
        const len = this.nodes.length + 1
        //Create a matrix of dimensions len x len, filled with zeros 
        const adjacencyMatrix = Array.from(new Array(len), x => new Array(len).fill(0))
        for(let edge of this.edges){
            adjacencyMatrix[edge.nodeFrom.value][edge.nodeTo.value] = 1
        }
        return adjacencyMatrix
    }
}
const graph = new Graph()
graph.insertEdge(1,2)
graph.insertEdge(1,3)
graph.insertEdge(1,4)
graph.insertEdge(3,4)

// Should be [[1, 2], [1, 3], [1, 4], [3, 4]]
console.log(graph.getEdgeList())
// Should be [ null, [ 2, 3, 4 ], null, [ 4 ], null ]
console.log(graph.getAdjacencyList())
// Should be [[0,0,0,0,0],[0,0,1,1,1],[0,0,0,0,0],[0,0,0,0,1],[0,0,0,0,0]]
console.log(graph.getAdjacencyMatrix())

Kyb3r Cipher

Hace 2 años

Buena info

Comentarios (48)48 comentarios

Carlos Eduardo Gomez García

Christian Velázquez

Christian Latorre

Angel Arevalo

Hace 5 años

Max Andy Diaz Neyra

Erick Fernando Guzmán Valerio

Juan Esteban Galvis

Melsar Otoniel Andrade Castillo

Juan David Sánchez

alberto ayala rodriguez

Jimmy Buriticá Londoño

Jhean Pacheco

Pablo Nicolás Alonso

Giuseppe Ramirez

Adrián Castillo

Mauricio Forero Acosta

Diego Rivera

Leonardo Buezo

Steve Anthony Luzquiños Agama

Danelia Sanchez Sanchez

Luis Blas

Bobionwa .

CRISTIAN BARBERO PÉREZ

Julio Manuel Nieto

Hace 9 meses

Johan Sebastian

Hace un año

Introducción a las estructuras de datos

Estructuras de Datos en JavaScript para Desarrolladores

Estructuras de Datos: Conceptos Básicos y Aplicaciones Prácticas

Almacenamiento de Datos en Memoria con JavaScript

Arrays y strings

Cómo funcionan arrays en memoria de JavaScript

Construcción de Arrays con Clases en JavaScript

Métodos pop y delete en arrays

Inmutabilidad de Strings y Almacenamiento en Memoria

Hash Table

Conceptos y Construcción de Hash Tables en JavaScript

Implementación de Hash Table en JavaScript: Método Set

Implementación del método get en hash table JavaScript

Linked List

Estructuras de Datos: Listas Enlazadas en JavaScript

Estructura y Creación de una Lista Enlazada Simple en JavaScript

Métodos para Manipular Nodos en Listas Enlazadas

Inserta nodos intermedios sin romper enlaces en JavaScript

Doubly Linked List con punteros bidireccionales

Stacks

Stacks: Concepto y Operaciones Básicas en JavaScript

Implementación de Stacks en JavaScript: Métodos Push y Peek

Queues

Qué es queue y cómo funciona FIFO

Implementación del método enqueue en JavaScript

Trees

Estructuras de Datos: Árboles Binarios y Búsqueda en JavaScript

Construcción y validación de un Árbol de Búsqueda Binaria en JavaScript

Graphs

Conceptos básicos de grafos: tipos y aplicaciones prácticas

Representación visual de grafos en JavaScript

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

Cierre

Estructuras de Datos con JavaScript: Práctica y Aplicación

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