Grafos
Un grafo (graph) es una estructura de datos que sirve para representar relaciones o conexiones entre diferentes elementos. Está formado por:
- Nodos o vértices → los elementos o entidades.
- Aristas o enlaces → las relaciones entre ellos.
Un grafo es una herramienta para modelar y analizar relaciones entre objetos. Gracias a ellos podemos resolver problemas de rutas, conexiones, optimización y análisis de redes.
Se utilizan principalmente para modelar problemas donde los objetos están conectados de alguna forma, como en mapas de carreteras, redes sociales, internet, sistemas de transporte o redes eléctricas.
Características principales
- Dirigido o no dirigido
- Dirigido (directed): las conexiones tienen un sentido (A → B).
- No dirigido (undirected): las conexiones son bidireccionales (A — B).
- Ponderado o no ponderado
- Ponderado (weighted): las aristas tienen un valor (ej. distancia, coste).
- No ponderado: solo indican la existencia de la relación.
- Ciclos
- Puede contener ciclos (camino que empieza y termina en el mismo nodo).
- Conectividad
- Conexo: todos los nodos están comunicados.
- No conexo: existen nodos o grupos aislados.
Operaciones básicas
- Agregar o eliminar nodos.
- Agregar o eliminar aristas.
- Recorrer el grafo (visitar nodos en cierto orden):
- BFS (Breadth-First Search) → anchura.
- DFS (Depth-First Search) → profundidad.
- Buscar caminos (por ejemplo, el más corto entre dos nodos).