Un grafo es un conjunto de vértices unidos por aristas, y casi cualquier cosa con conexiones se puede modelar como uno: carreteras, redes, dependencias, amistades, moléculas. La teoría de grafos estudia su estructura y los algoritmos sobre ellos. Un grafo bien elegido suele convertir una pregunta enredada en un problema estándar con solución conocida.
Conceptos clave
- Representaciones: las listas de adyacencia convienen a los grafos dispersos, las matrices de adyacencia a los densos.
- Recorridos: la búsqueda en anchura halla caminos con menos aristas; la búsqueda en profundidad da órdenes, ciclos y componentes.
- Caminos mínimos: el algoritmo de Dijkstra para pesos no negativos, Bellman-Ford cuando los pesos pueden ser negativos.
- Árboles generadores: los algoritmos de Kruskal y Prim conectan todos los vértices con el menor peso total.
- Flujos y emparejamientos: el flujo máximo es igual al corte mínimo; un emparejamiento une vértices sin repetir ninguno.
Vocabulario
- Dirigido y no dirigido: si las aristas tienen sentido o no.
- DAG: grafo dirigido acíclico, la forma de las dependencias, que se puede ordenar topológicamente.
- Componente conexa: un conjunto maximal de vértices alcanzables entre sí.
- Grafo planar: el que se puede dibujar sin que se crucen las aristas.
Qué estudiar, en orden
- Construye una clase de grafo con listas de adyacencia y lee un grafo desde un archivo.
- Implementa BFS y DFS y úsalas para hallar componentes conexas y detectar ciclos.
- Implementa Dijkstra con una cola de prioridad y contrástalo con una búsqueda por fuerza bruta.
- Añade la ordenación topológica, el árbol generador mínimo y las componentes fuertemente conexas.
- Modela un problema real como un flujo o un emparejamiento y resuélvelo.
Etiquetas relacionadas
#algorithms #combinatorics #discrete-math #data-structures #knowledge-graphs