Algoritmos de Grafos

Representaciones:
- Lista de Adyacencia: $O(V+E)$ espacio. Bueno para grafos dispersos.
- Matriz de Adyacencia: $O(V^2)$ espacio. Bueno para grafos densos.
Recorridos:
- BFS (Búsqueda en Amplitud):
  - Encuentra el camino más corto en grafos no ponderados.
  - Tiempo: $O(V+E)$.
- DFS (Búsqueda en Profundidad):
  - Clasificación topológica, componentes fuertemente conectados.
  - Tiempo: $O(V+E)$.
Árbol de Expansión Mínima (MST):
- Kruskal:
  - Ordena aristas por peso. Usa Union-Find para evitar ciclos.
  - Tiempo: $O(E \log E)$ o $O(E \log V)$.
- Prim:
  - Crece un MST desde un vértice inicial usando una cola de prioridad.
  - Tiempo: $O(E \log V)$ con un montículo binario; $O(E + V \log V)$ con un montículo de Fibonacci.
Caminos Más Cortos:
- Una Sola Fuente:
  - Bellman-Ford: Grafos con pesos negativos. Detecta ciclos negativos. $O(VE)$.
  - Dijkstra: Grafos con pesos no negativos. $O(E \log V)$ con montículo binario; $O(E + V \log V)$ con montículo de Fibonacci.
  - DAG (Grafos Acíclicos Dirigidos): Ordenamiento topológico + relajación. $O(V+E)$.
- Todos los Pares:
  - Floyd-Warshall: $O(V^3)$. Permite pesos negativos pero no ciclos negativos.
  - Johnson: Para grafos dispersos con pesos negativos (reponderación). $O(VE + V^2 \log V)$.
Flujo Máximo:
- Ford-Fulkerson: Algoritmo genérico. Depende de cómo se elijan los caminos de aumento.
- Edmonds-Karp: Caso especial de Ford-Fulkerson usando BFS para encontrar caminos de aumento. $O(VE^2)$.

Algoritmos de Cadenas

Algoritmo de Rabin-Karp:
- Búsqueda de patrones usando hashing.
- Tiempo promedio: $O(n+m)$. Peor caso: $O(nm)$.
Algoritmo Knuth-Morris-Pratt (KMP):
- Búsqueda de patrones lineales. Usa una función de prefijo para evitar retrocesos.
- Tiempo: $O(n+m)$.

Conceptos Avanzados

NP-Completitud:
- Clase P: Problemas resolubles en tiempo polinomial.
- Clase NP: Problemas cuyas soluciones pueden verificarse en tiempo polinomial.
- NP-Completo (NPC): Problemas en NP tal que cualquier problema en NP puede reducirse a él en tiempo polinomial.
- NP-Hard: Problemas al menos tan difíciles como los problemas NPC.
Algoritmos de Aproximación:
- Para problemas NP-Hard. Garantizan una solución dentro de un factor de la óptima.
Algoritmos Probabilísticos y Aleatorizados:
- Utilizan la aleatoriedad para mejorar el rendimiento o simplificar el algoritmo.
- Ej: Quicksort (promedio $O(n \log n)$), Prueba de primalidad de Miller-Rabin.