No tienes acceso a esta clase

隆Contin煤a aprendiendo! 脷nete y comienza a potenciar tu carrera

脷ltima oportunidad para asegurar tu aprendizaje por 1 a帽o a precio especial

Antes: $249

Currency
$189/a帽o

Paga en 4 cuotas sin intereses

Paga en 4 cuotas sin intereses
Suscr铆bete

Termina en:

0D
0H
32M
25S

Construyendo un grafo

28/29
Recursos

Aportes 39

Preguntas 2

Ordenar por:

驴Quieres ver m谩s aportes, preguntas y respuestas de la comunidad?

o inicia sesi贸n.

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

El grafo de tipo adjancentList lo que haces es, como vimos, generar una lista de a qui茅nes conoce tal nodo.
.
Lo genial de este grafo es que si t煤 necesitas saber qu茅 otros nodos est谩n conectados a alg煤n nodo espec铆fico simplemente tienes que obtener el 铆ndice que contiene a dicho nodo y eso te devolver谩 a los nodos con los cuales este se conecta 馃憖

lo entend铆, pero no supe para que me sirve eso, toca seguir investigando los grafos, buen curso cositas avanzadas para m铆, pero no sabr铆a donde poner en practica

Incre铆ble la manera que tiene De Granda de explicar todo de una manera super entendible ^^

Dej贸 el c贸digo con las l铆neas para insertar datos:

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

    // Add V茅rtice/Nodo
    addVertice(valor){
        this.Adylist[valor] = [];
        this.nodos++;
    }

    // Add Conexi贸n/Edge
    addConex(nodo1, nodo2){
        // Conexi贸n entre gragos
        this.Adylist[nodo1].push(nodo2);
        this.Adylist[nodo2].push(nodo1);
    }
}

const Graph = new Grafo();

// V茅rtices
Graph.addVertice(1);
Graph.addVertice(3);
Graph.addVertice(4);
Graph.addVertice(5);
Graph.addVertice(6);
Graph.addVertice(8);

// Conexiones
Graph.addConex(8,4)
Graph.addConex(4,1)
Graph.addConex(1,3)
Graph.addConex(1,6)
Graph.addConex(3,6)
Graph.addConex(3,5)
Graph.addConex(5,4)

/**
    // RESULTADO:
    1: (3) [4, 3, 6]
    3: (3) [1, 6, 5]
    4: (3) [8, 1, 5]
    5: (2) [3, 4]
    6: (2) [1, 3]
    8: [4] 
 */

Para hacerlo dirigido imagino que es no hacer push en ambos sino solo en el camino ( 1 -> 2 solo hacer push a nodo1 )

Me encanto el tema, quisiera aprender a utilizarlos digamos en backend, por ejemplo si creo una mini red social c贸mo conectar a los usuarios que se agreguen (No Dirigido) y as铆. Me parece muy interesante de aplicar. Excelente curso 10/10

Parec铆a el mas dif铆cil de hacer y result贸 ser el mas sencillo jaja

Hice una clase de utilidad para crear un diccionario que cuando una propiedad se acceda y esta no exista, entonces cree autom谩ticamente la entrada con un array.

class DefaultArrayDict {
  constructor() {
    return new Proxy(
      {},
      {
        get: (target, name) => {
          if (!(name in target)) {
            target[name] = [];
          }

          return target[name];
        },
      }
    );
  }
}

class Graph {
  constructor() {
    this.nodes = 0;
    this.adjacentList = new DefaultArrayDict();
  }

  addEdge(node1, node2) {
    this.adjacentList[node1].push(node2);
    this.adjacentList[node2].push(node1);
  }
}

const myGraph = new Graph();

De esta forma me ahorro la funci贸n llamada addVertex.

Vaya fumada como gener贸 el grafo, de locos!!!

C贸digo del ejercicio
Incluye los v茅rtices y bordes.
.

class Graph {
  constructor() {
    this.nodes = 0;
    this.adjacentList = {};
  }

  /** Adicionar un Vertice */
  addVertex(node) {
    this.adjacentList[node] = [];
    this.nodes++;
  }

  /** Adicionar un Borde */
  addEdge(node1, node2) {
    this.adjacentList[node1].push(node2);
    this.adjacentList[node2].push(node1);
  }
}

const myGraph = new Graph();
// Vertices
myGraph.addVertex('1');
myGraph.addVertex('3');
myGraph.addVertex('4');
myGraph.addVertex('5');
myGraph.addVertex('6');
myGraph.addVertex('8');
// Bordes
myGraph.addEdge('1', '6');
myGraph.addEdge('1', '4');
myGraph.addEdge('1', '3');
myGraph.addEdge('3', '5');
myGraph.addEdge('3', '6');
myGraph.addEdge('4', '5');
myGraph.addEdge('4', '8');

C贸digo para la construcci贸n de un Grafo no direccionado utilizando una Matriz adyacente.

class Graph {
  constructor() {
    this.nodes = 0;
    this.adjacentMatrix = {};
  }
  addVertex(node) {
    if (this.adjacentMatrix[node]) {
      return new Error("Existing vertex"); 
    }
    this.adjacentMatrix[node] = [];
    const adjacentMatrixLength = Object.keys(this.adjacentMatrix).length;
    for (let key in this.adjacentMatrix){
      for (let i = 0; i < adjacentMatrixLength; i++) {
        if (this.adjacentMatrix[key].length !== adjacentMatrixLength) {
          this.adjacentMatrix[key].push("0");
        }
      }
    }
    this.nodes++;
    return this;
  }
  addEdge(node1, node2) {
    if (!this.adjacentMatrix[node1] || !this.adjacentMatrix[node2]) {
      return new Error("One of the vertices entered doesn't exist");
    }
    const adjacentMatrixKeys = Object.keys(this.adjacentMatrix);
    for (let i = 0; i < this.nodes; i++) {
      if (adjacentMatrixKeys[i] == node1) {
        this.adjacentMatrix[node2][i] = "1";
      }
      if (adjacentMatrixKeys[i] == node2) {
        this.adjacentMatrix[node1][i] = "1";
      }
    }
    return this;
  }
}

const myGraph = new Graph();

Les comparto mi implementaci贸n del c贸digo de la clase usando JSDocs:

/*
 * A graph can be represent in many ways, let suppose we have the following graph:
 * 2 - 0
 * | \
 * |  \
 * 1 - 3
 * 
 * we can represent it as:
 * 1. Edge list:
 *    const graph = [
 *      [0, 2],
 *      [1, 2],
 *      [1, 3],
 *      [2, 3]
 *    ]
 * 
 * 2. Adjacent list
 *    - with arrays:
 *       const graph = [[2], [2, 3], [0, 1, 3], [1, 2]]
 *   - with an object:
 *       const graph = {
 *         0: [2],
 *         1: [2, 3],
 *         2: [0, 1, 3],
 *         3: [1, 2]
 *       }
 * 
 * 3. Adjacent matrix:
 *   - with arrays:
 *       const graph = [
 *         [0, 0, 1, 0],
 *         [0, 0, 1, 1],
 *         [1, 1, 0, 1],
 *         [0, 1, 1, 0],
 *       ]
 *   - with an object:
 *       const graph = {
 *         0: [0, 0, 1, 0],
 *         1: [0, 0, 1, 1],
 *         2: [1, 1, 0, 1],
 *         3: [0, 1, 1, 0],
 *       }
 */

class Graph {
  constructor() {
    /**
     * @type {Number} number of nodes from the graph
     * @public
     */
    this.nodes = 0
    /**
     * @type {Object<number, [number]>} an object which every key is a node and each value is an array of nodes to which this node is connected
     * @public
     */
    this.adjacentList = {}
  }

  /**
   * @param {Number} value node of the Graph
   */
  addVertex(value) {
    this.adjacentList[value] = []
    this.nodes++
  }

  /**
   * @param {Number} node1 
   * @param {Number} node2 
   */
  addEdges(node1, node2) {
    this.adjacentList[node1].push(node2)
    this.adjacentList[node2].push(node1)
  }
}
馃ぉ Excelente clase, hace que se vea f谩cil y entendible.

Esta interesante esta forma de crear un grafo, pero aun no estoy muy seguro como se podr铆a recorrer. Seguir茅 estudiando el c贸digo, pero mientras aqu铆 dejo mi aporte:

class Graph{
  constructor(){
    this.nodes = 0;
    this.edgesAdjList = {};
  }
  addVertex(node) {
    this.edgesAdjList[node] = [];
    this.nodes++;
  }
  insert(node1, node2){
   //Si el node1 o node2 no existen, entonces se crean
    if (!this.edgesAdjList[node1]) this.addVertex(node1); 
    if (!this.edgesAdjList[node2]) this.addVertex(node2);

    this.edgesAdjList[node1].push(node2);
    this.edgesAdjList[node2].push(node1);
  }
}
const myGraph = new Graph();

Tengo un problema y es que quiero evitar que se creen nodos sin conexiones, pero no en encuentro una forma correcta de ocultar la funci贸n addVertex() . 驴Alg煤n consejo?

Es increible eel derrame cerebral que me da cada que acabo una clase

para hacer un dirijo podria ser igual al que tenemos de esta clase pero cambiando la clase del edge por algo asi

make_conection(from, to){
    this.adjacentList[from].push(to)
  }

A帽ad铆 la comprobaci贸n de si existen los nodos antes de a帽adir la conexi贸n entre ambos y en caso de que uno de ellos no exista se a帽ade autom谩ticamente.

addLink( node1, node2 ) {

    if( !(node1 in this.adjList) ) 
        this.addVertex( node1 )
    if( !(node2 in this.adjList) )
        this.addVertex( node2 )

    this.adjList[node1].push(node2)
    this.adjList[node2].push(node1)
    
    return this

}

"MyGraph"


class MyGraph {

    constructor() {

        this.node = 0;
        this.adjacentList = {};

    };

    addVertex(node) {

        this.adjacentList[node] = [];
        this.nodes++;
        return this;

    };

    addEdge(node1, node2) {

        this.adjacentList[node1].push(node2);
        this.adjacentList[node2].push(node1);
        return this;

    };
    
};

Wow! 隆Qu茅 excelente forma de explicar la que tiene Diego! Gran dominio del tema y genial la forma de construir el grafo. Yo hac铆a mis grafos en java usando LinkedList, pero se me hac铆a muy complicado y veo que con la matriz adyacente es mucho m谩s f谩cil. Lo repito: GENIAL!

Ac谩 dejo mi Grapho, basado en un objeto adjacentMatrix, con pesos ponderados, y con la opci贸n de indicar si un 鈥榚dge鈥 es bidireccional al agregarlo.

Este es el resultado:

Este es el c贸digo:

class MyGraph { // weigthed and optional directed, based on an object 'adjacentMatrix'
  constructor() {
    this.adjacentMatrix = { 'T':[], };
    this.nodes = 0;
  }

  addVertex(node) {
    if(node == 'T') return undefined;
    this.adjacentMatrix['T'].push(node);
    this.adjacentMatrix[node] = [];
    this.nodes++;
    return this;
  }

  addEdge(node1, node2, weight, isBidirected) {
    const keys = Object.keys(this.adjacentMatrix);
    for(let i=0; i<this.nodes; i++) {
      for(let j=0; j<this.nodes; j++) {
        // Fill weigth in first direction
        if(keys[i] == node1) {
          if(keys[j] == node2) {
            this.adjacentMatrix[node1][j] = weight;
          }
        }
        // Fill weight contra direction if apply
        if(isBidirected) {
          if(keys[i] == node2) {
            if(keys[j] == node1) {
              this.adjacentMatrix[node2][j] = weight;
            }
          }
        }
        // Fill identity elements using 0
        if(keys[i] == keys[j]) {
          this.adjacentMatrix[keys[i]][j] = '0';
        }
        // Fill empty (undefined) elements using '-'
        if(this.adjacentMatrix[keys[i]][j] == undefined) {
          this.adjacentMatrix[keys[i]][j] = '-';
        }
      }
    };
    return this;
  }
}

const myGraph = new MyGraph();
console.log('MyGraph', myGraph);
console.log('addVertex(1)', myGraph.addVertex('1'));
console.log('addVertex(3)', myGraph.addVertex('3'));
console.log('addVertex(4)', myGraph.addVertex('4'));
console.log('addVertex(5)', myGraph.addVertex('5'));
console.log('addVertex(6)', myGraph.addVertex('6'));
console.log('addVertex(8)', myGraph.addVertex('8'));
console.log('addEdge(1,3,1,true)', myGraph.addEdge('1','3',.1,false));
console.log('addEdge(1,6,3,true)', myGraph.addEdge('1','5',.2,true));
console.log('addEdge(3,5,4,true)', myGraph.addEdge('3','6',.3,true));
console.log('addEdge(3,6,5,true)', myGraph.addEdge('3','5',.4,true));
console.log('addEdge(1,4,2,true)', myGraph.addEdge('4','1',.5,false));
console.log('addEdge(4,5,6,true)', myGraph.addEdge('4','6',.6,true));
console.log('addEdge(4,8,7,true)', myGraph.addEdge('4','8',.7,true));

Existe un problema en el c贸digo, y es que no hay restricciones al momento de agregar un nuevo vertic茅 enlace, adem谩s, de que al momento de agregar un edge si colocas un node que no contiene el graph saldr谩 un error. Estuve haciendo tomando en cuentas tales dilemas en mi siguiente script, espero le den una chequeada 馃挌.

class Graph {
    constructor () {
        this.nodes = 0, //To count all the nodes the graph has
        this.adjacentList = {} //The way choseen to represent the graph is adjacentList
    }

    addVertexV2 (node) { //A vertex is a node
        if (!this.adjacentList[node]) {
            this.adjacentList[node] = [];
            this.nodes++;
            return {
                message: "New vertex was created successfully"
            };
        } else {
            return {
                message: "That vertex already existed"
            };
        }
    }

    addEdgeV2 (node1, node2) {
        const nodeAdjacents1 = this.adjacentList[node1];
        const nodeAdjacents2 = this.adjacentList[node2];

        if (nodeAdjacents1 && nodeAdjacents2) {
            const edge = nodeAdjacents1.find(node => node == node2);
            
            if (!edge) {
                this.adjacentList[node1].push(node2);
                this.adjacentList[node2].push(node1);
                return {
                    message: "New edge was created successfully"
                }
            } 
            return {
                message: "That edge already existed"
            };
        } else {
            return {
                message: "One of the nodes isn't in the graph"
            };
        }
    }
}

const graph = new Graph();

La programacion es jodidamente sexy

Qu茅 curioso鈥 Yo realic茅 las conexiones en diferente orden, de manera visual y una por una, en plan鈥 El 1 est谩 con el 3, 4 y 6, listo entonces (1,3) (1,4) (1,6) etc鈥 Hacerlo como yo lo hice tiene 2 desventajas: son m谩s l铆neas de c贸digo y es mayor el margen para el error humano.

La 煤nica ventaja de hacer esto es que quedan organizados, pero al ser un array, t煤 puedes simplemente usar el m茅todo Arr.sort(a,b => a-b) y ya te quedan ordenados de mayor a menor, entonces realmente no hay beneficio alguno al hacerlo como yo XD

M茅todo de eliminaci贸n de un nodo basado en el c贸digo del profesor:
.
.
.

removeVertex(node){
        if(this.adjacentList[node]){
            //if such node exists

            const maxKey = Object.keys(this.adjacentList).sort((a,b) => a - b).pop();
            //finding the max number that a key could have in the graph

            for(let i = 0; i <= maxKey; i++){
                //loop to resort trough the nodes in the graph

                if(this.adjacentList[i]){
                //if an specific node from the graph exists

                    let nodeIndex = this.adjacentList[i].findIndex(item => item == node)
                    //finding the index inside each connections array of that node

                    if(nodeIndex != -1){     
                        //only when findIndex methods results in success this code will trigger. Otherwise the findIndex methods return "-1" when there's no coincidence

                        this.adjacentList[i].splice(nodeIndex, 1);
                        //deleting that reference each connections array of that node we want to delete
                    }
                }
            }
            this.nodes--;
            //decreasing number of vertices

            delete this.adjacentList[node];
            //deleting also the node

            return this;
        }

He creado este metodo para agregar directamente nodos y bordes, espero les sirva de guia si es necesario

addAll(node1, node2){
      if(!this.adjacentList[node1]){
         this.adjacentList[node1] = [];
      }
      if(!this.adjacentList[node2]){
         this.adjacentList[node2] = [];
      }
      this.adjacentList[node1].push(node2);
      this.adjacentList[node2].push(node1);
      this.nodes = Object.keys(this.adjacentList).length;
   }

Este curso por poco quema mi procesador un par de veces (con while infiintos) pero ha valido la pena jaja鈥 Aqui dejo el reto con Adjacent Matrix:

class Graph {
	constructor() {
		this.adjacentList = {};
		this.nodes = 0;
	}

	addVertex(node) {
		if (!this.adjacentList[node]) {
			this.adjacentList[node] = [];
		}
		const keys = Object.keys(this.adjacentList);
		for (let i = 0; i <= this.nodes; i++) {
			this.adjacentList[keys[i]] = [];
			for (let j = 0; j <= this.nodes; j++) {
				this.adjacentList[keys[i]].push(0);
			}
		}

		this.nodes++;
		return this;
	}

	addEdge(node1, node2) {
		const keys = Object.keys(this.adjacentList);
		for (let i = 0; i < this.nodes; i++) {
			if (node2 == keys[i]) {
				this.adjacentList[node1][i] = 1;
				this.adjacentList[node2][keys.findIndex((index) => index == node1)] = 1;
			}
		}
		return this;
	}
}
const myGraph = new Graph();
myGraph.addVertex(8);
myGraph.addVertex(4);
myGraph.addVertex(1);
myGraph.addVertex(5);
myGraph.addVertex(3);
myGraph.addVertex(6);
myGraph.addEdge(8, 4);
myGraph.addEdge(4, 1);
myGraph.addEdge(4, 5);
myGraph.addEdge(1, 3);
myGraph.addEdge(5, 3);
myGraph.addEdge(1, 6);
myGraph.addEdge(3, 6);

PD: si agregas un nuevo v茅rtice a la matr铆z, los valores regresan a 0, en el futuro corregir茅 eso

esto de los grafos es todo un mundo

me gustaria que me dieran comentarios acerca de que mejorarle al codigo

class Node {
  constructor(value) {
    this.value = value;
    this.degree = 0;
    this.Edgedwith = [];
  }
}
class UndirectedUnweightedGraph {
  constructor() {
    this.nodes = {};
    this.edges = {};
    this.numberOfNodes = 0;
  }
  addNodo(number) {
    this.nodes[number] = new Node(number);
    this.edges[number] = [];
    this.numberOfNodes++;
  }
  addEdge(node1, node2) {
    if (this.check(node1) && this.check(node2)) {
      this.edges[node1].push(node2);
      this.edges[node2].push(node1);

      const nodeA = this.nodes[node1];
      const nodeB = this.nodes[node2];

      nodeA.degree++;
      nodeA.Edgedwith.push(node2);
      nodeB.degree++;
      nodeB.Edgedwith.push(node1);
    }
  }
  check(number) {
    const entry = number.toString();
    return Object.getOwnPropertyNames(this.edges).includes(entry);
    //it can be one liner sentence but it loses readable
    // return Object.getOwnPropertyNames(this.edges).includes(number.toString());
  }
  path(node1, node2) {
    return this.check(node1) && this.check(node2) ? this.FindPath(node1, node2) : console.log('cant do that');
  }
  FindPath(currentNode, nodeMeta, visited = [], path = []) {
    /*    debugger; */
    path.push(currentNode);
    const edgesOfCurrentNode = [...this.nodes[currentNode]['Edgedwith']];
    if (edgesOfCurrentNode.includes(nodeMeta)) {
      return path.push(nodeMeta);
    } else {
      visited.push(currentNode);
      const adjacentsNotVisited = edgesOfCurrentNode.filter((item) => !visited.includes(item));
      for (const node of adjacentsNotVisited) {
        this.FindPath(node, nodeMeta, visited, path);
        if (path[path.length - 1] == node) path.pop();
      }
    }
    if (path.length == 1) return 'theres no path';
    return path;
  }
}

const graph = new UndirectedUnweightedGraph();
graph.addNodo(1);
graph.addNodo(2);
graph.addNodo(4);
graph.addNodo(5);
graph.addNodo(30);
graph.addEdge(1, 2);
graph.addEdge(1, 4);
graph.addEdge(2, 5);
graph.addEdge(4, 30);
const path = graph.path(30, 1);

console.log(path);```

Mi implementacion:

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

    addConnection(node1, node2) {
        if (this.adjacentLists.hasOwnProperty(node1)) {
            this.adjacentLists[node1].push(node2);
        } else {
            this.adjacentLists[node1] = [node2];
        }

        if (this.adjacentLists.hasOwnProperty(node2)) {
            this.adjacentLists[node2].push(node1);
        } else {
            this.adjacentLists[node2] = [node1];
        }
    }
}

mi soluci贸n para 鈥渁djacentMatrix鈥

Desacople los metodos para retornar tanto la 鈥淓dge-list鈥 como la 鈥淎djacency-list鈥 a partir de los datos ingresados

class Graph {

    constructor() {
        this.nodes = [];
        this.edges = [];
        this.adjacencyList = {};
    }

    
    addNode(node) {
        this.nodes.push(node);
    }


    addEdge(node1, node2) {
        this.edges.push([node1, node2]);
       
    }


    getEdgeList() {
        return this.edges;
    }


    getAdjacencyList() {
        
        // make nodes as keys for the adjacency list
        this.nodes.map( node => {
            this.adjacencyList[node] = [];
        })
        
        // match nodes to edges
        this.edges.map( edge => {
            this.adjacencyList[edge[0]].push(edge[1]);
            this.adjacencyList[edge[1]].push(edge[0]);
        })

        return this.adjacencyList

    }


}

class Graph {
constructor(){
this.nodes = 0;
this.adjacentList = {};
}
//los grafos tiene dos particularidades, bordes y vertices
addVertex(node){
this.adjacentList[node] = [];
this.nodes++
}
//edge
addEdge(node1, node2){
this.adjacentList[node1].push(node2);
this.adjacentList[node2].push(node1);
}
}

const myGraph = new Graph()
myGraph.addVertex(鈥1鈥)
myGraph.addVertex(鈥3鈥)
myGraph.addVertex(鈥4鈥)
myGraph.addVertex(鈥5鈥)
myGraph.addVertex(鈥6鈥)
myGraph.addVertex(鈥8鈥)

myGraph
myGraph.addVertex(鈥1鈥)
myGraph.addVertex(鈥3鈥)
myGraph.addVertex(鈥4鈥)
myGraph.addVertex(鈥5鈥)
myGraph.addVertex(鈥6鈥)
myGraph.addVertex(鈥8鈥)

myGraph
myGraph.addEdge(鈥3鈥, 鈥5鈥)
myGraph.addEdge(鈥6鈥, 鈥3鈥)
myGraph.addEdge(鈥1鈥, 鈥6鈥)
myGraph.addEdge(鈥1鈥, 鈥3鈥)
myGraph.addEdge(鈥1鈥, 鈥4鈥)
myGraph.addEdge(鈥4鈥, 鈥5鈥)
myGraph.addEdge(鈥8鈥, 鈥4鈥)

myGraph

Dejo un ejemplo en typescript timado con gen茅ricos algo m谩s practico donde cada nodo tiene un id para las conexiones un value donde donde podemos a帽adir lo que queramos y un Set con las conexiones, uso un set para que no se repita nunca dos veces la misma.

Para la adjacent list uso un Map que es algo que nos ofrece JavaScript de serie y es muy util es como un objeto pero ya preparado con sus funciones.

Aparte a帽ado funciones para a帽adir nodos, eliminar nodos, a帽adir o eliminar conexiones, modificar el valor de un nodo.

Espero les sea de ayuda.

class Node<ID, T> {
  public connections = new Set<Node<ID, T>>();

  constructor(
    public id: ID,
    public value: T,
  ) {
  }

  addConnection(idNode: Node<ID, T>) {
    this.connections.add(idNode);
  }

  removeConnection(idNode: Node<ID, T>) {
    this.connections.delete(idNode);
  }
}

export class Graph<ID, T> {
  private nodes: number = 0;
  private adjacentList: Map<ID, Node<ID, T>> = new Map();

  constructor() {
  }

  addNode(id: ID, value: T): void {
    const newNode = new Node<ID, T>(id, value);
    this.adjacentList.set(id, newNode);
    this.nodes++;
  }

  addEdge(nodeId1: ID, nodeId2: ID): void {
    const node1 = this.adjacentList.get(nodeId1);
    const node2 = this.adjacentList.get(nodeId2);

    if (node1 && node2) {
      node1.addConnection(node2);
      node2.addConnection(node1);
    }
  }

  getNode(id: ID): T | undefined {
    return this.adjacentList.get(id)?.value;
  }

  getAllNodes(): T[] {
    return Array.from(this.adjacentList.values()).map(node => node.value);
  }

  getConnections(id: ID): T[] {
    const node = this.adjacentList.get(id);
    if (node) {
      return Array.from(node.connections).map(node => node.value);
    }
    return [];
  }

  deleteNode(id: ID): T | undefined {
    const nodeToRemove = this.adjacentList.get(id);
    if (nodeToRemove) {
      nodeToRemove.connections.forEach(node => node.removeConnection(nodeToRemove));
      this.adjacentList.delete(id);
      this.nodes--;
      return nodeToRemove.value;
    }
    return undefined;
  }

  removeConnection(nodeId1: ID, nodeId2: ID): void {
    const node1 = this.adjacentList.get(nodeId1);
    const node2 = this.adjacentList.get(nodeId2);

    if (node1 && node2) {
      node1.removeConnection(node2);
      node2.removeConnection(node1);
    }
  }

  editNodeValue(id: ID, value: T): void {
    const node = this.adjacentList.get(id);
    if (node) {
      node.value = value;
    }
  }

  get length(): number {
    return this.nodes;
  }
}

interface User {
  id: number;
  name: string;
  age: number;
}

const myGraph = new Graph<number, User>();
myGraph.addNode(1, { id: 1, name: 'John', age: 30 });
myGraph.addNode(3, { id: 3, name: 'Mike', age: 20 });
myGraph.addNode(4, { id: 4, name: 'Mary', age: 40 });
myGraph.addNode(5, { id: 5, name: 'Bob', age: 50 });
myGraph.addNode(6, { id: 6, name: 'Sam', age: 60 });
myGraph.addNode(8, { id: 8, name: 'Tom', age: 70 });

myGraph.addEdge(1, 3);
myGraph.addEdge(1, 4);
myGraph.addEdge(1, 6);
myGraph.addEdge(3, 4);
myGraph.addEdge(3, 5);
myGraph.addEdge(3, 6);
myGraph.addEdge(4, 1);
myGraph.addEdge(4, 5);
myGraph.addEdge(5, 4);
myGraph.addEdge(5, 3);
myGraph.addEdge(6, 1);
myGraph.addEdge(6, 3);
myGraph.addEdge(8, 4);

console.log(myGraph);
console.log('Get value node 1: ', myGraph.getNode(1));
console.log('Get Connections node 1: ', myGraph.getConnections(1));
console.log('Deleting node 3: ', myGraph.deleteNode(3));
console.log('Get Connections node 1: ', myGraph.getConnections(1));
console.log(myGraph);
console.log('Removing connection 1 - 6')
myGraph.removeConnection(1, 6);
console.log('Get Connections node 1: ', myGraph.getConnections(1));

console.log('Get all values: ', myGraph.getAllNodes());

console.log(myGraph.length);

Tengo una web donde subo algunos totorales de programaci贸n agradecer铆a se pasaran y me dieran feedback. https://blog.jcoder.es

Mi nueva version de grafos ipo AdjacentList con algunas mejoras para evitar redundancia de validaciones:
p.s. permite agragar edges individuales o multiples si se env铆a un array XD:

class AdjacentList {
  constructor() {
    this.graph = {}
    this.length = 0
  }
  addVertex(value) {
    if (!this.graph[value]) {
      this.graph[value] = []
      this.length++
    }
    return this
  }
  addEdge(vertex, edges) {
    if (this.graph[vertex]) {
      if (!Array.isArray(edges)) {
        edges = [edges]
      }
      edges.forEach(edge => {
        if (this.graph[edge]) {
          const existEdge = this.graph[vertex]
            .find(ele => ele == edge)
          if (existEdge == undefined) {
            this.graph[vertex].push(edge)
            this.graph[edge].push(vertex)
          }
        }
      })
    }
    return this
  }
}

const myGraph = new AdjacentList()
myGraph.addVertex(1)
myGraph.addVertex(3)
myGraph.addVertex(4)
myGraph.addVertex(5)
myGraph.addVertex(6)
myGraph.addVertex(8)
myGraph.addEdge(8,4)
myGraph.addEdge(4, [1,5,8])
myGraph.addEdge(1, [4,3,6])
myGraph.addEdge(6, [1,3])
myGraph.addEdge(5, [4,3])

Listo! ya termin茅 tanto el de la clase, como uno grafo dirigido ponderado que hice por mi cuenta c:

.
.


// const graph = {
//   1: [4, 3, 6],
//   3: [5, 1, 6],
//   4: [8, 1, 5],
//   5: [4, 3],
//   6: [1, 3],
//   8: [4]
// }

//----------------------------------------------------------------->>>
//GRAFO DE LA CLASE - NO DIRIGIDOS - NO PONDERADO

class graph {
  constructor() {
    this.nodes = 0;
    this.adjacentList = {};
  }
  addVertex(node) {
    this.adjacentList[node] = []
    this.nodes++
  }
  addEdge(node1, node2) {
    this.adjacentList[node1].push(node2);
    this.adjacentList[node2].push(node1); 
  }

}

const newGraph = new graph();

newGraph.addVertex(1);
newGraph.addVertex(3);
newGraph.addVertex(4);
newGraph.addVertex(5);
newGraph.addVertex(6);
newGraph.addVertex(8);
// newGraph.addVertex(7);
// newGraph.addVertex(8);
// newGraph.addVertex(9);
// newGraph.addVertex(10);

newGraph.addEdge(1,6)
newGraph.addEdge(6,3)
newGraph.addEdge(1,3)
newGraph.addEdge(1,4)
newGraph.addEdge(3,5)
newGraph.addEdge(4,5)
newGraph.addEdge(8,4)

//----------------------------------------------------------------->>>
//GRAFO - DIRIGIDOS - PONDERADO

class graphD {
  constructor() {
    this.nodes = 0;
    this.adjacentList = {};
  }
  addVertex(node) {
    this.adjacentList[node] = [];
    this.nodes++
  }

  // Cost es el ponderado, me pareci贸 mejor imaginarlo c贸mo el costo de un viaje
  // c贸mo dijo el profesor
  addEdge(from, to, Cost) {
    let algo
    if(from == Number || to == Number || from <= this.nodes || to <= this.nodes || from >= 0 || to >= 0) {
      this.adjacentList[from][0] = {'NameRoute':`${from} --> ${to}`,'Cost':Cost};
      
      this.adjacentList[from][0].Route = this.adjacentList[to];
      return this
    }

  } 
  
}

const graphd = new graphD();

graphd.addVertex(1);
graphd.addVertex(3);
graphd.addVertex(4);
graphd.addVertex(5);
graphd.addVertex(6);
graphd.addVertex(8);

graphd.addEdge(1,6,2)
graphd.addEdge(6,3,5)
graphd.addEdge(1,3,6)
graphd.addEdge(1,4,1)
graphd.addEdge(3,5,7)
graphd.addEdge(4,5,6)
graphd.addEdge(8,4,9)

Aqu铆 una peque帽a l贸gica para evitar conexiones repetidas en el grafo:

addEdge(node1, node2) {
    this.#checkAndAddEdge(this.adjacentList[node1],node2);
    this.#checkAndAddEdge(this.adjacentList[node2],node1);
    
    return this;
}
#checkAndAddEdge(list, node) {
    for (let i = 0; i < list.length; i++) {
        if (list[i] == node) {
            return false;
        }
    }
    list.push(node);
    return true;
}
```java import java.util.*; public class GraphLA{ private int nodes; private Map<String,List<String>> adjacentList; public GraphLA(){ this.nodes=0; this.adjacentList=new HashMap<>(); } public void addVertex(String vertice){ if(!adjacentList.containsKey(vertice)){ this.adjacentList.put(vertice, new LinkedList<>()); this.nodes++; } } public void addEdge(String verticeo, String verticed){ if(adjacentList.containsKey(verticeo)&& adjacentList.containsKey(verticed)){ if(!isAdyacente(verticeo, verticed)){ adjacentList.get(verticeo).add(verticed); adjacentList.get(verticed).add(verticeo); } else{ System.out.println("Ya existe una conexi贸n"); } } else{ System.out.println("Al menos uno de los dos vertices no existe"); } } public boolean isAdyacente(String verticeo, String verticed){ return adjacentList.get(verticeo).contains(verticed); } public void ShowGrafo(){ for (String Allkeys : adjacentList.keySet()) { List<String>listValue=adjacentList.get(Allkeys); System.out.println(Allkeys+": "+listValue); } } public static void main(String[] args) { GraphLA grafo=new GraphLA(); grafo.addVertex("1"); grafo.addVertex("3"); grafo.addVertex("4"); grafo.addVertex("5"); grafo.addVertex("6"); grafo.addVertex("8"); grafo.addEdge("3", "5"); grafo.addEdge("6", "3"); grafo.addEdge("1", "6"); grafo.addEdge("1", "3"); grafo.addEdge("1", "4"); grafo.addEdge("4", "5"); grafo.addEdge("8", "4"); grafo.ShowGrafo(); } } ```import java.util.\*; /\*\* \* \* @author MAX VIDARTE \*/ public class GraphLA{ private int nodes; private Map\<String,List\<String>> adjacentList; public GraphLA(){ this.nodes=0; this.adjacentList=new HashMap<>(); } public void addVertex(String vertice){ if(!adjacentList.containsKey(vertice)){ this.adjacentList.put(vertice, new LinkedList<>()); this.nodes++; } } public void addEdge(String verticeo, String verticed){ if(adjacentList.containsKey(verticeo)&& adjacentList.containsKey(verticed)){ if(!isAdyacente(verticeo, verticed)){ adjacentList.get(verticeo).add(verticed); adjacentList.get(verticed).add(verticeo); } else{ System.out.println("Ya existe una conexi贸n"); } } else{ System.out.println("Al menos uno de los dos vertices no existe"); } } public boolean isAdyacente(String verticeo, String verticed){ return adjacentList.get(verticeo).contains(verticed); } public void ShowGrafo(){ for (String Allkeys : adjacentList.keySet()) { List\<String>listValue=adjacentList.get(Allkeys); System.out.println(Allkeys+": "+listValue); } } public static void main(String\[] args) { GraphLA grafo=new GraphLA(); grafo.addVertex("1"); grafo.addVertex("3"); grafo.addVertex("4"); grafo.addVertex("5"); grafo.addVertex("6"); grafo.addVertex("8"); grafo.addEdge("3", "5"); grafo.addEdge("6", "3"); grafo.addEdge("1", "6"); grafo.addEdge("1", "3"); grafo.addEdge("1", "4"); grafo.addEdge("4", "5"); grafo.addEdge("8", "4"); grafo.ShowGrafo(); } }

hice el ejercicio con adjacent matrix, dejo mi peque帽o aporte

addVertex(node) {
        this.adjacentList[node] = [];
        this.keys.push(node);
        this.adjacentMatrix[node] = [];
        for (let i = 0; i < this.keys.length; i++) {
            this.adjacentMatrix[this.keys[i]] = new Array((this.nodes + 1)).fill('0');
        }
        this.nodes++;
    }
    addMatrix(node1, node2) {
        const index1 = this.keys.indexOf(node1);
        const index2 = this.keys.indexOf(node2);
        this.adjacentMatrix[node1][index1] = '1';
        this.adjacentMatrix[node1][index2] = '1';
        this.adjacentMatrix[node2][index1] = '1';
        this.adjacentMatrix[node2][index2] = '1';
    }

馃憣