Graph
AvanzadoNo Prioritaria
Estructura no lineal compuesta por vértices y aristas.
¿Qué es un Grafo?
Un grafo es una colección de nodos conectados por aristas. Puede ser dirigido o no dirigido, y también puede tener ciclos o ser acíclico. Los grafos se utilizan para representar relaciones complejas entre entidades.
Analogía del Mundo Real
Imagina un mapa de una ciudad:
- Cada punto (ciudad o cruce) es un nodo.
- Cada calle o camino es una conexión (arista).
- Puedes tener caminos de doble sentido (grafo no dirigido) o calles de un solo sentido (grafo dirigido).
Cómo Funciona Internamente un Grafo
- Lista de Adyacencia: Se usa un objeto o arreglo donde cada nodo tiene una lista de sus vecinos.
- Matriz de Adyacencia: Una matriz booleana donde cada celda indica si hay una conexión entre dos nodos.
- Para recorrer el grafo, se pueden usar algoritmos como DFS (búsqueda en profundidad) o BFS (búsqueda en anchura).
Ejemplos de Código
// Graph implementation using adjacency list
class Graph {
constructor() {
this.adjacencyList = {};
}
addVertex(vertex) {
if (!this.adjacencyList[vertex]) {
this.adjacencyList[vertex] = [];
}
}
addEdge(vertex1, vertex2) {
this.adjacencyList[vertex1].push(vertex2);
this.adjacencyList[vertex2].push(vertex1);
}
removeEdge(vertex1, vertex2) {
this.adjacencyList[vertex1] = this.adjacencyList[vertex1].filter(
v => v !== vertex2
);
this.adjacencyList[vertex2] = this.adjacencyList[vertex2].filter(
v => v !== vertex1
);
}
removeVertex(vertex) {
while (this.adjacencyList[vertex].length) {
const adjacentVertex = this.adjacencyList[vertex].pop();
this.removeEdge(vertex, adjacentVertex);
}
delete this.adjacencyList[vertex];
}
}Explicación Visual (🚧 En progreso)
Pronto disponible
Estamos trabajando en un video para explicar esta estructura de datos
Complejidad en Tiempo y Espacio
| Operación | Promedio | Peor Escenario |
|---|---|---|
| Acceso | O(1) | O(1) |
| Búsqueda | O(V+E) | O(V+E) |
| Inserción | O(1) | O(1) |
| Eliminación | O(V+E) | O(V+E) |
V es el número de vértices (nodos) y E es el número de aristas (conexiones).
La complejidad puede variar dependiendo de la representación (lista de adyacencia o matriz de adyacencia).
Operaciones Comunes
- addVertex(v)Agrega un nuevo nodo al grafo
- addEdge(v1, v2)Conecta dos nodos con una arista
- removeEdge(v1, v2)Elimina la conexión entre dos nodos
- removeVertex(v)Elimina un nodo y sus conexiones
Practica
Aplica lo que has aprendido