Grafos

Estructura de datos de grafos

Un grafo consiste en vértices (nodos) y aristas (conexiones). Los grafos pueden ser dirigidos/no dirigidos, ponderados/no ponderados y cíclicos/acíclicos.

Representación de grafos

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

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

  addEdge(v1, v2) {
    this.adjacencyList[v1].push(v2);
    this.adjacencyList[v2].push(v1); // For undirected
  }
}

// BFS - Breadth First Search
function bfs(graph, start) {
  const visited = new Set();
  const queue = [start];
  const result = [];
  
  visited.add(start);
  
  while (queue.length) {
    const vertex = queue.shift();
    result.push(vertex);
    
    for (const neighbor of graph.adjacencyList[vertex]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }

  

    
Aprende más
    

      
        
GeeksforGeeks: Graph
        
Guía completa de grafos y algoritmos.
      
      
        
LeetCode: Graph
        
Practica recorridos y caminos mínimos en grafos.
      
    
  

  return result;
}

// DFS - Depth First Search
function dfs(graph, start, visited = new Set(), result = []) {
  visited.add(start);
  result.push(start);
  
  for (const neighbor of graph.adjacencyList[start]) {
    if (!visited.has(neighbor)) {
      dfs(graph, neighbor, visited, result);
    }
  }
  return result;
}